TITLE: Halting problem on 2 registers
QUESTION [2 upvotes]: How can we show that the halting problem on register machines equipped with only two registers
is unsolvable.
My intuition stems from assuming it is unsolvable on $n$ registers, but if we take a finite tuple of $n$ entries/registers, how do we get it to simplify to the two registers?

REPLY [4 votes]: There is a proof sketch of this on the Wikipedia article Counter Machine with a reference to Minsky's 1967 textbook on computability.
The interesting thing is that a two-register machine is only Turing complete if the correct input/output encoding is used. There is no two-register machine that computes $f(n) = 2^n$ when the input is given by placing $n$ in one register and $0$ in the other. But if the input is encoded as $2^n$ in one register and $0$ in the other, there is a two-register machine program that will compute $2^{(2^n)}$ in the first register. So the input has to be encoded in a special way (place $2^n$ in the register), and the output has to be decoded in the corresponding way (the register will end up with the value $2^{f(n)}$).  
A three register machine is able to compute $2^n$ given $n$ in a register, so it does not require this unconventional input encoding.
{"set_name": "stack_exchange", "score": 2, "question_id": 304705}