Wie eine Turing-Maschine zu schaffen, die für x ^ y als Funktion Rechner dient

Question

Ich studiere für einen Test auf Turing-Maschinen, und ich bin fest mit einem Problem, bei dem ich eine Turing-Maschine zu schaffen, die als Funktionsrechner dient:

f(x,y) = x ^ y 

Ich verstehe mein Tape-Eingang wie folgt getrennt kommen würde:

1's of base 0 1's of exponent 

Mit meiner Band Ausgabe wie

sein

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

Wie würde ich mich über X und Y die auf dem Band (s) platzieren? (Es kann eine Multi-Band-Maschine sein) Wie würde das Zustandsdiagramm wie?

. Hinweis: Ich verwende einstellige mit 1 verwendet 0 darstellen und 0 verwendete nicht als Wert, sondern als Begrenzer

So:

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

Answer 1

Ich vermute, ein bisschen hier, es ist schon eine Weile, da ich mit Turing-Maschine Simulatoren gespielt. Zunächst einmal würde ich mag in mehr konzeptionellen Schritte, um die Aufgabe zu unterteilen:

1. durch den Wert einer anderen Nummer auf dem Band eine Nummer auf dem Band erhöhen
2. eine Nummer auf dem Band von dem Wert einer anderen Nummer auf dem Band multiplizieren - dies kann durch Ausführen von Schritt 1 wiederholt durchgeführt wird
3. Quadrat eine Zahl auf dem Band - x ^ 2 ausgearbeitet von x auf dem Band setzt sich dann von selbst multipliziert
4. (der letzte Schritt) an die Kraft des Wertes einer anderen Nummer auf dem Band eine Nummer auf das Band erhöhen - dies kann durch Ausführen von Schritt 2 wiederholt durchgeführt wird

eine Aufgabe wiederholt N-mal ausführen zu können, setzen N auf das Band, führen Sie die Aufgabe einmal, dann 1 subtrahiert vom Ende der Nummer N. Wiederholen, bis die Anzahl N von dem Band weg ist.

Hoffentlich ist dies ausreichend, um Ihnen den Einstieg sowieso. Die Zustandsmaschine konstruiert, mehr oder weniger mechanisch auf diese Weise werden kann.

Answer 2

In meinem eigenen Turing Pseudo-Code:

1. Kopieren Eingang A0B auf Band 2
2. schreiben 000010000 auf Band 3
   • multiplizieren Sie die Anzahl auf Band 3 von A von Band 2 durch
     1. am Anfang ab A
     2. Schreiben 0 auf Band 4
        • Kopieren Nummer 3 => 4
        • vorwärts einmal auf Band 3 (3 ++)
        • gehen 3, wenn nicht ein Ende zu Schritt
        • Antwort von Band 4 auf Band zu bewegen 3
   • verringert die Anzahl B auf Band 2
3. Wenn B auf Band 2 nicht 0 ist, geht 2
zu Schritt
4. Kopieren Sie die Antwort von Band 3 auf Band 1

Hier ist der Turing-Code, (sind Bänder wie Zeiger, Kleinbuchstaben, Eingabeband ist i) funktionieren sollte:

# 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
#                          ^

Bitte überprüfen Sie die Fehler:)