Como criar uma máquina de Turing que serve como calculadora função para x ^ y

Question

Eu estou estudando para um teste em máquinas de Turing, e eu estou preso com um problema em que eu tenho que criar uma máquina de Turing que serve como uma calculadora de função para:

f(x,y) = x ^ y 

Eu entendo a minha entrada fita viria separados assim:

1's of base 0 1's of exponent 

Com a minha saída de fita ser como

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

Como eu iria sobre a colocação de X do Y na fita (s)? (Pode ser uma máquina multi-fita) Qual seria o diagrama olhar estado como?

Nota:. Estou usando unário com 1 usado para representar 0 e 0 usado não como valor, mas como um delimitador

Assim:

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

Answer 1

Eu estou supondo um pouco aqui, tem sido um pouco desde que eu joguei com simuladores de máquina de Turing. Primeiro de tudo, eu gostaria de dividir a tarefa-se em várias etapas conceituais:

1. incrementar um número na fita pelo valor do outro número na fita
2. multiplicar um número na fita pelo valor do outro número na fita - isso pode ser feito através da realização de etapa 1 repetidamente
3. quadrado um número na fita - x ^ 2 é trabalhada por colocar x na fita, em seguida, multiplicando-o por si só
4. (a etapa final) levantam uma série sobre a fita para o poder do valor de outro número na fita - isso pode ser feito através da realização de etapa 2 repetidamente

Para executar uma tarefa repetidamente N vezes, colocar N na fita, executar a tarefa uma vez, em seguida, subtrair 1 a partir do final do número N. Repita até que o número N está desaparecido desde a fita.

Esperamos que isso é suficiente para você começar de qualquer maneira. A máquina de estado pode ser construído mais ou menos mecanicamente desta forma.

Answer 2

Na minha própria pseudocódigo Turing:

1. copiar a0b entrada Tape 2
2. gravar 000010000 para fita 3
   • multiplicar o número on Tape 3 por A de Tape 2 por
     1. começando no início de A
     2. escrita 0 a Tape 4
        • Número de copiar 3 => 4
        • avançar uma vez on Tape 3 (3 ++)
        • indo para a etapa 3 a menos que um extremidades
        • movendo resposta da fita 4 a fita de 3
   • diminuir o número B on Tape 2
3. Se B on Tape 2 não é 0, vá para o passo 2
4. Copie a resposta da fita 3 a fita 1

Aqui está o código turing que deve funcionar (fitas são como ponteiros, letras minúsculas, fita de entrada é 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
#                          ^

Por favor, verifique se há erros:)