Timeline for Simulating Turing machines (output included) with circuits
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2010 at 22:48 | vote | accept | echoone | ||
| Nov 7, 2010 at 4:08 | comment | added | echoone | @Alaggan: Oh, you're right! My mistake. | |
| Nov 6, 2010 at 14:10 | comment | added | Mohammad Alaggan | @echoone: no, the output bits are duplicated. $C_k(w)=00\ 11\ 01\ 01 ...$ and $C_n(x)=00\ 11\ 00\ 11\ 01\ 01 ...$ | |
| Nov 6, 2010 at 14:05 | comment | added | Mohammad Alaggan | More on uniform families of circuits: cse.ohio-state.edu/~gurari/theory-bk/… . | |
| Nov 6, 2010 at 13:51 | comment | added | echoone | 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 6, 2010 at 13:29 | comment | added | Mohammad Alaggan | @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 6, 2010 at 13:09 | comment | added | Peter Shor | 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 6, 2010 at 4:57 | comment | added | Mohammad Alaggan | 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 6, 2010 at 4:31 | history | answered | Joshua Grochow | CC BY-SA 2.5 |