# Halting problem on 2 registers

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?

-
I don't have a concrete proof handy, but couldn't you save the data of n registers in the first register by using some tuple encoding, and use the second register for decoding? –  Johannes Kloos Feb 15 '13 at 9:51
Can you please elaborate on how the Turing machine encodes and decodes? I thought of incorporating a counter somewhere –  mary Feb 15 '13 at 10:01
Aaah, now I remember how to do this. You use the first register as "tape to the left of the head position" and the second as "tape to the right of the head position", and the symbol at the head position is stored in the state. Building the operations should then be straightforward. –  Johannes Kloos Feb 15 '13 at 10:12
How do you build the operations? Can you also please describe the setting which you started with? I don't quite understand that. Thanks –  mary Feb 20 '13 at 10:25

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.