Timeline for Undecidability, Church Turing Thesis, and P/poly
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2011 at 5:57 | comment | added | Mohammad Al-Turkistany | @Phil, Nice answer. You should convert your comment to an answer. | |
| Mar 27, 2011 at 23:47 | comment | added | Phil Ellison | The important issue here is uniformity. You can trivially code any set you like into a family of circuits. However, if you require that there exists a single Turing machine which enumerates the family of circuits for you then this family can no longer compute the halting set. So yes, there exists a family of circuits that can solve the halting problem. And no, we can't compute it. However, there exists no uniform family of circuits that solves the halting problem. | |
| Mar 27, 2011 at 23:21 | history | asked | LowerBounds | CC BY-SA 2.5 |