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.
Surely there is some Turing machine that only halts if the Collatz conjecture is false. That could be thrown into this incredibly uncomputable mix.
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