4
$\begingroup$

Is there a simple example of a Turing machine $M$, such that whether $M$ halts or not on the empty input cannot be proved within the current mathematical system?

Specifically, I'm curious whether there exists an example simple enough that the state transition of the Turing machine can be drawn as a reasonably-sized diagram.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ look at the answers of this thread: cstheory.stackexchange.com/questions/20978/… $\endgroup$
    – Denis
    Commented Jan 23, 2015 at 0:53
  • $\begingroup$ one can take any halting problem with arbitrary input and encode that into the start/ initialization states of the TM to write the input to the tape. so Turings classic problem applies here with simple adjustment. it is known from some research on "small TMs" the halting problem is encodable in some fairly small TMs. $\endgroup$
    – vzn
    Commented Jan 23, 2015 at 18:34

1 Answer 1

Reset to default
3
$\begingroup$

Take the "current mathematical system" $S$ and an undecidable sentence $P$ for $S$. Consider the Turing machine $T$ which enumerates all theorems of $S$ and halts if it ever enumerates either $P$ or $\lnot P$. System $S$ cannot decide whether $T$ halts.

Note that such a $T$ does not halt.

Improve this answer
$\endgroup$
1
  • $\begingroup$ See here, here and here for discussion of some specific $2$-symbol Turing machines with ZFC-independent halting problem, recently created in essentially the manner you describe. It appears that the number of states required for such a machine is now at $1919$, and quite sure to decrease further. $\endgroup$
    – r.e.s.
    Commented Jun 29, 2016 at 22:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.