The paper A universal cellular automaton in the hyperbolic plane says:

Our simulation consists in simulating the execution of a register machine. It is known that two registers are enough to simulate a Turing machine, see [10], and so, by such a simulation, we shall obtain a universal computation.

It links to [10] which is Computation: Finite and Infinite Machines, a $200 book from Minsky with no reasonable/free version seemingly available on the web, so no easy access.

How are two registers enough to simulate a Turing machine? How do we know that? What is the sketch laid out in the Minsky book that explains how this works?


The reduction is sketched on Wikipedia.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.