MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Phil Ellison Mar 27 '11 at 23:47
@Phil, Nice answer. You should convert your comment to an answer. – Mohammad Al-Turkistany Apr 3 '11 at 5:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.