Source: cirosantilli/turing-machine-that-halts-if-and-only-if-collatz-conjecture-is-false

= Turing machine that halts if and only if Collatz conjecture is false
{c}
{tag=Collatz conjecture}

https://mathoverflow.net/questions/309044/is-there-a-known-turing-machine-which-halts-if-and-only-if-the-collatz-conjectur suggests one does not exist. Amazing.

Intuitively we see that the situation is fundamentally different from the <Turing machine that halts if and only if the Goldbach conjecture is false> because for Collatz the counter example must go off into infinity, while in Goldbach conjecture we can finitely check any failures.

Amazing.

Back to article page