Simulating Turing machines (output included) with circuits A Turing machine with input alphabet {0,1} computes a partial or total function $f \colon \{0,1\}^* \to \{0,1\}^*$. Is it possible to construct a circuit family $\{C_n\}$ such that for an input $x$ of length $n$, $C_n(x) = f(x)$? I have not seen this kind of circuit family in any of the standard texts, nor have I encountered it after lots of googling. 

I understand that for decision problems, it is unnecessary to consider such circuit families (which is probably why nobody has bothered to consider them). Or maybe it is just a trivial modification and so is relegated as an exercise to the reader (although I haven't seen such an exercise mentioned anywhere).

There are two immediate obstacles, which I see, that such a circuit family would need to overcome:


What does $C_n(x)$ do when $f(x)$ diverges?
If $|x| = |y|$, but $|f(x)| &lt; |f(y)|$, the output of $C_n(x)$ will contain less bits than $C_n(y)$. How would this work?


I personally don't see any method of overcoming these obstacles.
Yes, as long as we allow encoding the the result of $f$ in a basically trivial way, rather than outputting exactly $f(x)$.

To get over obstacle (2) (different output lengths for the same input length): for any given input length $n$, there is a maximum output length $m$.  $C_n$ will output $2m$ bits.  The first $2|f(x)|$ bits output by $C_n(x)$ will be the bits of $f(x)$ doubled, and the remaining $2(m-|f(x)|)$ bits will be the string 01 repeated over and over.  For example, if $m = 6$ and for some $x$ of length 10, $f(x)=0010$, then $C_{10}(x) = 00\ 00\ 11\ 00\ 01\ 01$ (spaces added for ease of reading).

To get over obstacle (1) ($f(x)$ may not halt): for any given input length $n$, there is a time $t$ such that, for all $x$ of length $n$, either $f(x)$ halts within $t$ steps, or $f(x)$ does not halt ever.  If $f(x)$ does not halt, then we make the output of the circuit be a string of 10 repeated over and over again.  Of course, such a circuit family can not in general be uniform, since deciding that halting time is in general uncomputable, but the circuit family still exists.