Skip to main content
1 of 1
Post Made Community Wiki
LowerBounds
  • 663
  • 8
  • 22

Undecidability, Church Turing Thesis, and P/poly

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.

LowerBounds
  • 663
  • 8
  • 22