How to create a turing machine that serves as function calculator for x^y

Question

I'm studying for a test on turing machines, and I'm stuck with a problem in which I have to create a Turing Machine that serves as a function calculator for:

f(x,y) = x ^ y

I understand my tape input would come separated like this:

1's of base 0 1's of exponent

With my tape output being like

1's of base 0 1's of exponent 0 1's of the computated result

How would I go about placing X's and Y's on the tape(s)? (It can be a multitape machine) How would the state diagram look like?

Note: I'm using unary with 1 used to represent 0 and 0 used not as value but as a delimiter.

So:

   0 = delimiter
   1 =    0
   11 =   1
   111 =  2
   1111=  3
   11111= 4 
   etc.

Answer 1

I'm guessing a bit here, it's been a little while since I played with Turing machine simulators. First of all, I would want to divide the task up into several conceptual steps:

1. increment a number on the tape by the value of another number on the tape
2. multiply a number on the tape by the value of another number on the tape - this can be done by performing step 1 repeatedly
3. square a number on the tape - x ^ 2 is worked out by putting x on the tape then multiplying it by itself
4. (the final step) raise a number on the tape to the power of the value of another number on the tape - this can be done by performing step 2 repeatedly

To perform a task repeatedly N times, put N onto the tape, perform the task once, then subtract 1 from the end of the number N. Repeat until the number N is gone from the tape.

Hopefully this is sufficient to get you started anyway. The state machine can be constructed more or less mechanically in this fashion.

Answer 2

In my own Turing pseudocode:

1. copy input A0B to Tape 2
2. write 000010000 to Tape 3
   • multiply the number on Tape 3 by A from Tape 2 by
     1. starting at the beginning of A
     2. writing 0 to Tape 4
     3. copying number 3 => 4
     4. moving forward once on Tape 3 (3++)
     5. going to step 3 unless A ends
     6. moving answer from Tape 4 to tape 3
   • decrement the number B on Tape 2
3. If B on Tape 2 isn't 0, go to step 2
4. Copy the answer from Tape 3 to Tape 1

Here's the turing code that should work (tapes are like pointers, lowercase letters, input tape is i):

# At the start for 2^3
# i: 000111011110000
#       ^

_start_ -> *a = 0, start2
start2 [*i==0] -> i++, *a++ = 0, *b++ = 0, start4
start2 [*i==1] -> i++, *a++ = 1, start2
start4 [*i==0] -> *b-- = 0, b--, initc
start4 [*i==1] -> i++, *b++ = 1, start4
initc -> *c++ = 0, *c++ = 1, *c++ = 1, *c-- = 0, mult

# example
# i: 00011101111000
#              ^
# a: 001110000
#        ^
# b: 001111000
#         ^
# c: 00011000
#        ^

mult[*b==0]: lastcpy
mult[*b==1]: b--, *d++ = 0, *d++ = 1, rewa
rewa[*a==0]: a++, a++, multcpy
rewa[*a==1]: a--, rewa

multcpy[*c==1]: c++, multcpy2
multcpy[*c==0]: multcpy3
multcpy2[*a==0]: multcpy
multcpy2[*a==1]: *d++ = 1, multcpy2
multcpy3: *d-- = 0, *c = 0, cpydtoc

cpydtoc[*d==1]: d--, *c++ = 1, cpydtoc
cpydtoc[*d==0]: *c-- = 0, mult

lastcpy[*c==1]: *i++ = 1, c--, lastcpy
lastcpy[*c==0]: *i = 0, _finish_

# Should end with
# i: 00011101111011111111100
#                          ^

Please check for errors :)