Comment créer une machine qui sert de calculateur de fonctions pour x ^ y

Question

J'étudie un test sur les machines de Turing et je suis confronté à un problème dans lequel je dois créer une machine de Turing qui sert de calculateur de fonctions pour:

f(x,y) = x ^ y 

Je comprends que mon entrée de bande viendrait séparée de la manière suivante:

1's of base 0 1's of exponent 

Avec ma sortie sur bande ressemblant à

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

Comment pourrais-je placer les X et les Y sur la (les) cassette (s)? (Cela peut être une machine multi-bandes) À quoi ressemblerait le diagramme d'état?

Remarque: j’utilise unary avec 1 pour représenter 0 et 0 n’est pas utilisé comme valeur, mais comme séparateur.

Donc:

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

Answer 1

Je suppose un peu ici, cela fait un petit moment que je ne joue pas avec les simulateurs de machines de Turing. Tout d’abord, je voudrais diviser la tâche en plusieurs étapes conceptuelles:

1. incrémente un nombre sur la bande de la valeur d'un autre numéro sur la bande
2. multipliez un nombre sur la bande par la valeur d'un autre nombre sur la bande - vous pouvez le faire en effectuant l'étape 1 à plusieurs reprises
3. place un numéro sur la bande - x ^ 2 est obtenu en plaçant x sur la bande, puis en le multipliant par lui-même
4. (dernière étape) élève un nombre sur la bande jusqu'à la puissance de la valeur d'un autre numéro sur la bande. Pour ce faire, répétez l'étape 2 de manière répétée

Pour exécuter une tâche plusieurs fois N, placez N sur la bande, effectuez-la une fois, puis soustrayez 1 de la fin du numéro N. Répétez l'opération jusqu'à ce que le numéro N disparaisse de la bande.

Espérons que cela suffira pour vous lancer de toute façon. La machine à états peut être construite de manière plus ou moins mécanique de cette manière.

Answer 2

Dans mon propre pseudocode de Turing:

1. copiez l'entrée A0B sur la bande 2
2. écrivez 000010000 sur la bande 3
   • multipliez le nombre sur la bande 3 par A à partir de la bande 2 par
     1. commençant au début de A
     2. écriture de 0 sur la bande 4
        • numéro de copie 3 = > 4
        • avancer une fois sur la bande 3 (3 ++)
        • aller à l'étape 3 sauf si A se termine
        • déplacer la réponse de la bande 4 à la bande 3
   • décrémentez le nombre B sur la bande 2
3. Si B sur la bande 2 n'est pas 0, passez à l'étape 2
4. Copiez la réponse de la bande 3 à la bande 1

Voici le code de turing qui devrait fonctionner (les bandes sont comme des pointeurs, les lettres minuscules, la bande d'entrée est 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
#                          ^

Vérifiez les erreurs:)