4 ms·
Turing machines, with their infinitely long tape, break human imagination. Surely there is some Turing machine that only halts if the Collatz conjecture is fal
by mikewarot 3y ago
Turing machines, with their infinitely long tape, break human imagination.
Surely there is some Turing machine that only halts if the Collatz conjecture is false. That could be thrown into this incredibly uncomputable mix.
- nodogoto 3y agoThe Collatz conjecture is undecidable, so no Turing machine like you describe exists.
- CaptainNegative 3y agoThe Collatz conjecture isn't a decision problem. The natural corresponding decision problem (given an x, does the conjecture hold when starting at all positive integers k less than x) is decidable in constant time. We don't know what specifically the deciding machine is, but it is either the one that always returns Yes or the one that returns whether or not x is below some finite value. Either case can be solved by only reading a bounded number of bits from the input. With some work, one can eventually generalize Collatz to make an undecidable problem; this is more or less the basis for FRACTRAN. https://en.wikipedia.org/wiki/FRACTRAN https://en.wikipedia.org/wiki/FRACTRAN