# Automata and Computability Recall

Recall that we may consider circuits that output strings over {0,1} by designating several output gates. Let addn: {0,1}2n{0,1}n+1 take the sum of two n bit binary integers and produce the n + 1 bit result. Show that we can compute the addn function with 0(n) size circuits.

See attached file for full problem description.

© SolutionLibrary Inc. solutionlibary.com 9836dcf9d7 https://solutionlibrary.com/computer-science/data/automata-and-computability-recall-3et3