Come creare una macchina turing che funge da calcolatrice di funzioni per x ^ y
-
06-07-2019 - |
Domanda
Sto studiando per un test su macchine Turing e sono bloccato con un problema in cui devo creare una macchina Turing che funge da calcolatrice di funzioni per:
f(x,y) = x ^ y
Capisco che il mio input per il nastro verrebbe separato in questo modo:
1's of base 0 1's of exponent
Con l'output del mio nastro simile a
1's of base 0 1's of exponent 0 1's of the computed result
Come farei per posizionare X e Y sul nastro (i)? (Può essere una macchina multi-nastro) Come sarebbe il diagramma di stato?
Nota: sto usando unario con 1 usato per rappresentare 0 e 0 usato non come valore ma come delimitatore.
Quindi:
0 = delimiter
1 = 0
11 = 1
111 = 2
1111= 3
11111= 4
etc.
Soluzione
Sto indovinando un po 'qui, è passato un po' di tempo da quando ho giocato con i simulatori di macchine Turing. Prima di tutto, vorrei suddividere l'attività in diversi passaggi concettuali:
- incrementa un numero sul nastro del valore di un altro numero sul nastro
- moltiplica un numero sul nastro per il valore di un altro numero sul nastro - questo può essere fatto eseguendo ripetutamente il passaggio 1
- quadrare un numero sul nastro - x ^ 2 viene elaborato mettendo x sul nastro e moltiplicandolo per sé
- (il passaggio finale) aumenta un numero sul nastro alla potenza del valore di un altro numero sul nastro - questo può essere fatto eseguendo ripetutamente il passaggio 2
Per eseguire un'attività ripetutamente N volte, inserire N sul nastro, eseguire l'attività una volta, quindi sottrarre 1 dalla fine del numero N. Ripetere fino a quando il numero N non viene rimosso dal nastro.
Speriamo che questo sia sufficiente per iniziare comunque. La macchina a stati può essere costruita più o meno meccanicamente in questo modo.
Altri suggerimenti
Nel mio pseudocodice di Turing:
- copia input A0B su Tape 2
- scrivi 000010000 su Tape 3
- moltiplica il numero sul nastro 3 per A dal nastro 2 per
- a partire dall'inizio di A
- scrivendo 0 su Tape 4
- copia numero 3 = > 4
- andare avanti una volta su Tape 3 (3 ++)
- andare al passaggio 3 a meno che A non finisca
- spostare la risposta dal nastro 4 al nastro 3
- decrementa il numero B sul nastro 2
- moltiplica il numero sul nastro 3 per A dal nastro 2 per
- Se B su Tape 2 non è 0, andare al passaggio 2
- Copia la risposta dal nastro 3 al nastro 1
Ecco il codice di turing che dovrebbe funzionare (i nastri sono come puntatori, lettere minuscole, il nastro di input è 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
# ^
Controlla gli errori :)