4 ms·

A turing machine is a mathematical abstraction that is the simplest machine that can compute things. Due to it's nature of "mathematical abstraction", it's actu

A turing machine is a mathematical abstraction that is the simplest machine that can compute things. Due to it's nature of "mathematical abstraction", it's actually impossible to build one, though you can restrict it and build one of course. In particular, we have real computers (more complex than Turing machines, and with other restrictions). 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.

Jtsummers 10y ago
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.