Re:Turing machines that should run forever
by Jtsummers on Wednesday May 11, 2016 @01:51PM
(#11677553)
Really the only thing preventing the construction of a true Turing machine is the inability to have an infinitely long tape. Fortunately, that limitation isn't a problem in practice for most things you'd wish to compute.
At it's simplest a Turing machine consists of an infinite tape of memory cells, a read/write head, a state register, and a state transition table (functions). Read the current cell and look up the pair (current state, cell value) to get the effect (new cell value, direction to move head [left, right, stay], new state).
Nothing in real computers can't be translated to a Turing machine description. It just won't be efficient :P. And anything written for a Turing machine will run on a real computer, modulo memory available.
These particular Turing machines that were built, have special properties that allow them to test mathematical axioms/theorems, so for example, if the Z machine halts, then it means that the ZFC axioms are wrong. In the article, this is stated in the negative form ("Z will run forever if ZFC is right").
Disclaimer: it's been a long time since I last read the formal definitions of turing machines, and my explanation may be sloppy -- but I aimed for a more general thing to give you an idea.