<p>Yes, as long as we allow encoding the the result of $f$ in a basically trivial way, rather than outputting exactly $f(x)$.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-06T04:57:13.487Z
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 ?
Mohammad Alaggan
CC BY-SA 2.5
2010-11-06T13:09:55.700Z
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.
Peter Shor 
CC BY-SA 2.5
2010-11-06T13:29:20.540Z
@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.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-06T13:51:49.750Z
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$.
echoone
CC BY-SA 2.5
2010-11-06T14:05:57.743Z
More on uniform families of circuits: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-sevense4.html#Q1-80004-10 .
Mohammad Alaggan
CC BY-SA 2.5
2010-11-06T14:10:05.793Z
@echoone: no, the output bits are duplicated. $C_k(w)=00\ 11\ 01\ 01 ...$ and $C_n(x)=00\ 11\ 00\ 11\ 01\ 01 ...$
Mohammad Alaggan
CC BY-SA 2.5
2010-11-07T04:08:46.037Z
@Alaggan: Oh, you're right! My mistake.
echoone
CC BY-SA 2.5
2010-11-06T04:31:06.117Z
2010-11-06T04:31:06.117Z
Joshua Grochow
<p>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. </p>

<p>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).</p>

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

<ol>
<li>What does $C_n(x)$ do when $f(x)$ diverges?</li>
<li>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?</li>
</ol>

<p>I personally don't see any method of overcoming these obstacles. </p>

CC BY-SA 2.5
2010-11-06T03:35:11.950Z
The function the Turing machine computes might not be decidable. Also the corresponding circuit might not be computable. This question seems too broad unless you put certain restrictions on the family of functions you are considering.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-06T10:37:40.383Z
There is no need to mention that the function is computed by a  Turing machines if you do not put some restriction on circuits (size, depth, ...) since any boolean function has an exponential size circuit, you have a partial function and you want to find a circuit for it. And then it becomes a question on output encoding for possible values/diverging.
Kaveh
CC BY-SA 2.5
2010-11-06T13:11:03.967Z
@Kaveh true, but he is talking about a family of boolean functions for different input lengths, not a fixed function...
Mohammad Alaggan
CC BY-SA 2.5
2010-11-06T13:43:09.950Z
@Kaveh consider the Boolean function taking a bit string encoding a Turing machine M and its input X, and outputs 1 if M(X) halts and 0 otherwise. Such Boolean function is not computable for arbitrary Turing machines and thus your claim that "any boolean function has an exponential size circuit" seems doubtful.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-06T19:39:44.320Z
@M. Alaggan: when I say an exponential size circuit, I mean a sequence of circuits, one for each input lenght. It is also very easy to see that any function on inputs of size $n$ has a circuit of size $O(2^n)$.
Kaveh
CC BY-SA 2.5
2010-11-06T23:24:04.880Z
@Kaveh: I meant to argue that it might not be computable, I am sorry if my appeal to the "has" verb was confusing in that regards, I should have said that instead. Thanks for the clarification.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-07T05:27:46.403Z
@M. Alaggan: You are welcome if my comment helped in anyway, but I don't understand what you are saying. It is obvious that a function computed by a circuit can be uncomputable. Requiring the circuits to be uniformly computable is a restriction on circuits which is not mentioned in the question, and as I said, if there are no restrictions on circuits, there is no need to say that the function is computed by a TM. Also the 2 obstacles mentioned by OP are for a circuit of fixed input size, so we don't even need to talk about a sequence of circuits.
Kaveh
<cc.complexity-theory><circuit-complexity><turing-machines><circuit-families>
Simulating Turing machines (output included) with circuits
echoone
# Simulating Turing machines (output included) with circuits

(Asked by: username_0 on 2010-11-06)

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.

**Tags:** cc.complexity-theory, circuit-complexity, turing-machines, circuit-families

> **Comments:**
> **username_1**: The function the Turing machine computes might not be decidable. Also the corresponding circuit might not be computable. This question seems too broad unless you put certain restrictions on the family of functions you are considering.  
> **username_2**: There is no need to mention that the function is computed by a  Turing machines if you do not put some restriction on circuits (size, depth, ...) since any boolean function has an exponential size circuit, you have a partial function and you want to find a circuit for it. And then it becomes a question on output encoding for possible values/diverging.  
> **username_1**: @username_2 true, but he is talking about a family of boolean functions for different input lengths, not a fixed function...  
> **username_1**: @username_2 consider the Boolean function taking a bit string encoding a Turing machine M and its input X, and outputs 1 if M(X) halts and 0 otherwise. Such Boolean function is not computable for arbitrary Turing machines and thus your claim that "any boolean function has an exponential size circuit" seems doubtful.  
> **username_2**: @M. Alaggan: when I say an exponential size circuit, I mean a sequence of circuits, one for each input lenght. It is also very easy to see that any function on inputs of size $n$ has a circuit of size $O(2^n)$.  
> **username_1**: @username_2: I meant to argue that it might not be computable, I am sorry if my appeal to the "has" verb was confusing in that regards, I should have said that instead. Thanks for the clarification.  
> **username_2**: @M. Alaggan: You are welcome if my comment helped in anyway, but I don't understand what you are saying. It is obvious that a function computed by a circuit can be uncomputable. Requiring the circuits to be uniformly computable is a restriction on circuits which is not mentioned in the question, and as I said, if there are no restrictions on circuits, there is no need to say that the function is computed by a TM. Also the 2 obstacles mentioned by OP are for a circuit of fixed input size, so we don't even need to talk about a sequence of circuits.  

---

## 1 answers

### Answer by username_3 on 2010-11-06. Score: 8 | Accepted answer

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:**
> **username_1**: 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 ?  
> **username_4**: 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.  
> **username_1**: @username_4nice comment. That's kinda what my intuition was trying to say but I didn't have enough background to say it that way. Thanks.  
> **username_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$.  
> **username_1**: More on uniform families of circuits: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-sevense4.html#Q1-80004-10 .  
> **username_1**: @username_0: no, the output bits are duplicated. $C_k(w)=00\ 11\ 01\ 01 ...$ and $C_n(x)=00\ 11\ 00\ 11\ 01\ 01 ...$  
> **username_0**: @Alaggan: Oh, you're right! My mistake.  

---

