2
$\begingroup$

I find the following three facts individually acceptable, but together deeply unsettling:

1) P/poly can decide the unary language $\{ 1^n | M_n(n) \quad \text{halts} \}$ via advice string.

2) Church Turing Thesis: any physical machine can be simulated by a turing machine

3) No turing machine can solve $\{ n | M_n (n) \quad \text{halts} \}$

So what does this mean? There's exists a family of circuit that can solve the halting problem, but we can not compute it?

Question: (A) Am I misunderstanding the technical definition of (1), (2), or (3) ? (B) Suggested reading that expounds on this / provides a frame of view, where this is intuitive?

This question is a bit soft/philosophical, so marked as community wiki.

$\endgroup$
2
  • 8
    $\begingroup$ 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. $\endgroup$ Mar 27, 2011 at 23:47
  • $\begingroup$ @Phil, Nice answer. You should convert your comment to an answer. $\endgroup$ Apr 3, 2011 at 5:57

0

Your Answer

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

Browse other questions tagged or ask your own question.