Theoretical Computer Science

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:

  1. What does $C_n(x)$ do when $f(x)$ diverges?
  2. If $|x| = |y|$, but $|f(x)| < |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.




Solution

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.





Comments (5)

  • +0 – I think I lost you when you said that the circuit family still exists. What if the Turing machine that generates the circuit doesn't halt when computing $t$ for all possible input lengths ? — Nov 06, 2010 at 04:57  
  • +5 – If the circuit family isn't uniform, then there doesn't have to be a Turing machine that generates the circuits. If you require the circuit family to be uniform (i.e., that there is some Turing machine that generates the circuit family), then finding a uniform family of circuits that simulates a given Turing machine would indeed require you to solve the halting problem. — Nov 06, 2010 at 13:09  
  • +0 – @Peter Shor nice comment. That's kinda what my intuition was trying to say but I didn't have enough background to say it that way. Thanks. — Nov 06, 2010 at 13:29  
  • +0 – Nice. I like your idea regarding obstacle (1). I have thought of something similar for obstacle (2), but there is always a problem: Suppose $w$ is of length $k$ and $x$ is of length $n$. Suppose further that the maximum output length $m$ for inputs of length $k$ is the same as that of $n$. Then there is a possibiliy that $C_k(w) = C_n(x)$ but $f(w) \ne f(x)$. Example: $f(w) = 01$, $f(x) = 01 \ 01$, and $C_k(w) = C_n(x) = 01 \ 01 \ 01 \ 01 \ 01$. — Nov 06, 2010 at 13:51  
  • +0 – More on uniform families of circuits: cse.ohio-state.edu/~gurari/theory-bk/… . — Nov 06, 2010 at 14:05