Problem 1. Prove that allowing a Turing machine to leave its head stationary during some transitions does not increase its computational power.

A Turing machine that can not leave its head stationary during some transitions can simulate a Turing machine that can leave its head stationary during some transitions. Replace the stationary Transition with two transitions, one that moves the head one place left the second moves the head one right (back to the place it would have stayed), These two transitions write the same symbol read. QED

I hope you wont take off if I am wrong about these (since you did not ask) but I think that the above would be a worst case time hit of:

(2)(N)(Q)

Problem 2. Prove that for each Turing machine that halts under all inputs, there is an equivalent Turing machine (that computes the same function) that never moves it head more than one character to the left of its starting position.

Any Turing machine that can move its head any number of places to the left of the starting position can be simulated by a Turing machine that can not move its head more than one character to the left of its starting position. Any writing that would have been done to the left of the starting position will be done to the right of any input that was on the tape at start time. As this writing takes place (it might occur right to left) everything to the right of it will be pushed down further to the right, just as the register simulation did. Special characters will be needed as seperators.

Time hit:

Quadratic increase.

Problem 3. Verify that a RAM need not have an unbounded number of registers. Use prime encoding to show that a three-register RAM can simulate a k-register RAM for any fixed k>3.

Encode the contents of all the registers from the unbounded RAM into the first register (R1) of the three-register RAM using prime encoding. Prime encoding works like this, if the unbounded RAM had k states use k primes. Take these primes to power n: p^n1 , p^n2,p^n3….p^nk where n1, n2 …nk are the values that would have been in the individual registers. To restore the numbers you repeatedly factor out each prime until only the prime representing the register you want to decode is left. The number of times this prime divides the remaining number is the value in that register. The second register (R2) will be "working space" The third (R3) is the zero for the branch_on_zero instruction. The 3 register RAM must be able to perform the instructions increment and decrement on the encoded registers, and perform a branch_on_zero operation. The 3-register RAM can obviously perform the branch_on_zero instruction using R3. To increment an encoded register (all these are represented by primes R2 R3 R5 R7 etc) multiply the contents of R1 by the number of the register that needs to be incremented. For example to increment register 3 (encoded) multiply the contents of R1 by 3. To do this (multiplication is primitive recursive) increment the contents of R2 three times for each decrement of R1, repeat this until R1 is zero. Then copy the contents of R2 into R1. The above operations are routines in the RAM machine. This is possible because we know how many registers the old machine had when we build this one so we build a routine for each of the encoded registers. To decrement an encoded register divide the contents of R1 by the number of the register that needs to be decremented. For example to decrement the contents of register 7 divide R1 by 7. Do this by using a routine that decrements R1 7 times for each increment of R2 (as long as R1 will still be >0 after the decrement) then copy R2 into R1. If R1 ends up greater than zero then reverse the operation as the content of the register you wanted to decrement was zero to start with.