Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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