5
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Mohammad Alaggan
    Commented Nov 6, 2010 at 3:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Nov 6, 2010 at 10:37
  • 1
    $\begingroup$ @Kaveh true, but he is talking about a family of boolean functions for different input lengths, not a fixed function... $\endgroup$
    – Mohammad Alaggan
    Commented Nov 6, 2010 at 13:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mohammad Alaggan
    Commented Nov 6, 2010 at 13:43
  • $\begingroup$ @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)$. $\endgroup$
    – Kaveh
    Commented Nov 6, 2010 at 19:39

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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 ? $\endgroup$
    – Mohammad Alaggan
    Commented Nov 6, 2010 at 4:57
  • 5
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Nov 6, 2010 at 13:09
  • $\begingroup$ @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. $\endgroup$
    – Mohammad Alaggan
    Commented Nov 6, 2010 at 13:29
  • $\begingroup$ 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$. $\endgroup$
    – echoone
    Commented Nov 6, 2010 at 13:51
  • $\begingroup$ More on uniform families of circuits: cse.ohio-state.edu/~gurari/theory-bk/… . $\endgroup$
    – Mohammad Alaggan
    Commented Nov 6, 2010 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.