Cómo crear una máquina de turing que sirva como calculadora de funciones para x ^ y

Question

Estoy estudiando para una prueba en máquinas de Turing, y me encuentro con un problema en el que tengo que crear una máquina de Turing que sirva como calculadora de funciones para:

f(x,y) = x ^ y 

Entiendo que mi entrada de cinta se separaría así:

1's of base 0 1's of exponent 

Con mi salida de cinta como

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

¿Cómo haría para colocar X e Y en la (s) cinta (s)? (Puede ser una máquina de cintas múltiples) ¿Cómo sería el diagrama de estado?

Nota: estoy usando unary con 1 usado para representar 0 y 0 usado no como valor sino como delimitador.

Entonces:

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

Answer 1

Supongo un poco aquí, ha pasado un tiempo desde que jugué con los simuladores de máquinas Turing. En primer lugar, me gustaría dividir la tarea en varios pasos conceptuales:

1. incrementa un número en la cinta por el valor de otro número en la cinta
2. multiplique un número en la cinta por el valor de otro número en la cinta; esto puede hacerse realizando el paso 1 repetidamente
3. cuadra un número en la cinta: x ^ 2 se resuelve colocando x en la cinta y luego multiplicándolo por sí mismo
4. (el paso final) eleva un número en la cinta a la potencia del valor de otro número en la cinta; esto puede hacerse realizando el paso 2 repetidamente

Para realizar una tarea repetidamente N veces, coloque N en la cinta, realice la tarea una vez, luego reste 1 del final del número N. Repita hasta que el número N desaparezca de la cinta.

Espero que esto sea suficiente para comenzar de todos modos. La máquina de estados se puede construir de manera más o menos mecánica de esta manera.

Answer 2

En mi propio pseudocódigo de Turing:

1. copie la entrada A0B a la cinta 2
2. escriba 000010000 en la cinta 3
   • multiplique el número en la Cinta 3 por A de la Cinta 2 por
     1. comenzando al principio de A
     2. escribir 0 en la cinta 4
        • número de copia 3 = > 4
        • avanzar una vez en Tape 3 (3 ++)
        • ir al paso 3 a menos que A termine
        • moviendo la respuesta de la Cinta 4 a la cinta 3
   • disminuir el número B en la cinta 2
3. Si B en la Cinta 2 no es 0, vaya al paso 2
4. Copie la respuesta de la Cinta 3 a la Cinta 1

Aquí está el código de Turing que debería funcionar (las cintas son como punteros, letras minúsculas, la cinta de entrada es 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
#                          ^

Compruebe si hay errores :)