Nella macchina di Turing, in qualsiasi stato, la testina di scrittura punta verso un punto particolare del nastro. Ci saranno simboli a sinistra della testa e simboli a destra della testa.
Guardando al primo, predicato principale:
turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
E 'intenzione di "far funzionare la macchina" chiamando perform/5. Gli argomenti per perform(Q0, Ls0, Ls, Rs0, Rs) rappresentano:
Q0 - the current state (or initial state before the "perform")
Ls0 - the current set of symbols that are LEFT of the head
Ls - the FINAL set of symbols that WILL BE left of the head after perform
Rs0 - the current set of symbols that are RIGHT of the head
Rs - the FINAL set of symbols that WILL BE right of the head after perform
Inizialmente, non ci sono simboli sinistra della testa. Tape0 inizialmente contiene tutti i simboli a destra della testa. Per "far funzionare la macchina", il predicato principale chiama:
perform(Q0, [], Ls, Tape0, Rs)
Si inizia con lo stato iniziale, Q0, non ha simboli di sinistra della testa per iniziare con ([]) e ha i simboli in Tape0 destra del testa per iniziare.Si prevede che, al completamento della query, sia necessario creare Ls con il set finale di simboli a sinistra della testa e Rs l'insieme finale di simboli a destra della testa.
Tutto il resto ora supporta perform/5.
symbol([Sym|Rs], Sym, Rs)
Questo definisce una relazione tra l'elenco dei simboli [Sym|Rs], e il primo simbolo in detto elenco (Sym) e il resto della lista (Rs). perform/5 utilizza questo predicato per leggere il simbolo successivo che si trova attualmente a destra della testa.
Per farlo funzionare correttamente nel contesto viene utilizzato, il predicato perform/5 mantiene la variabile Rs0 tale che è correttamente al fine dove la testa della lista è il primo simbolo a destra, il secondo elemento di la lista è il seguente simbolo a destra, e così via. Si noti che questo non è il caso dell'elenco di simboli a sinistra. L'elenco di sinistra viene mantenuto in in ordine inverso ordine di visualizzazione dei simboli sul nastro. Il motivo è che possono essere considerati in ordine di quanto restano a sinistra dell'attuale posizione della testa. Maggiori informazioni su questo un po 'più tardi.
action(left/stay/right, Ls0, Ls, Rs0, Rs)
Questo è dove l'azione è. :) Il ruolo è quello di eseguire l'azione data e fornire gli elenchi correttamente aggiornati di ciò che è a sinistra e destra della nuova posizione della testa dopo che è stata intrapresa un'azione. Ls0 e Rs0 sono gli elenchi dei simboli lasciato e destra della testa, rispettivamente prima viene eseguita l'azione. E Ls e Rs sono i simboli lasciato e destra della testa, rispettivamente dopo viene eseguita l'azione.
action(stay, Ls, Ls, Rs, Rs).
L'operazione dice che quando ho rimango, i simboli a sinistra ea destra della testa non cambiano.
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
L'operazione dice che quando mi muovo la testa destra posizione un simbolo, il simbolo immediatamente a destra (che è Sym in quanto il set destra dei simboli è [Sym|Rs]) diventa immediatamente il simbolo a sinistra. La serie di simboli a sinistra era originariamente, Ls0 e diventa [Sym|Ls0]. L'elenco di simboli a destra era originariamente [Sym|Rs] e diventa Rs.
Il left azione diventa un po 'più complicato di stay o right perché quando non ci sono più simboli sulla sinistra e un movimento di sinistra è indicato, la testa si muove ancora a sinistra e sulla destra viene visualizzato un vuoto.Quindi left è scoppiata in un separato, piccolo predicato:
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
left([], [], Rs0, [b|Rs0]).
Qui, se la sinistra insieme di simboli è vuota ([]) poi si spostano sinistra significa simboli sinistra rimane vuoto ([]) e nuovo spazio (b) appare sulla destra della testa, all'inizio del set originale di simboli di destra (la lista a destra cambia da Rs0 a [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).
Qui ci sono alcuni simboli a sinistra e l'azione è di spostarsi a sinistra. Il set iniziale di simboli a sinistra è [L|Ls] (L è il simbolo immediatamente a sinistra della testa) e il set iniziale di simboli a destra della testa è Rs. Quando la testa si muove a sinistra, il primo simbolo a sinistra diventa il primo simbolo a destra. Quindi il set di simboli sinistro aggiornato è Ls e il set di simboli corretto aggiornato è [L|Rs].
Il action(left, ...) predicato avrebbe potuto essere scritto senza il predicato ausiliario, left/4, in questo modo:
action(left, [], [], Rs0, [b|Rs0]).
action(left, [L|Ls], Ls, Rs, [L|Rs]).
Torna alla lista di sinistra e l'originale turing/2 predicato: dopo turing/2 chiamate perform(q0, [], Ls, Tape0, Rs), ha un set finale di simboli su destra (Rs) che sono nell'ordine corretto, da sinistra a destra. Tuttavia, la serie finale di simboli a sinistra (Ls) è elencata da destra a sinistra (poiché in ordine di quanto sono vicini alla posizione attuale della testa). Pertanto, al fine di mostrare l'intero nastro nell'ordine corretto, l'elenco di simboli a sinistra deve essere invertito e quindi inserito nella giusta serie di simboli. Così, le chiamate:
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
Abbattere la perform/5 predicato:
perform(qf, Ls, Ls, Rs, Rs) :- !.
Questo dice che se siamo allo stato finale qf, poi la finale elenco di simboli sinistra, Ls, diventa il nostro corrente set di left simboli. Allo stesso modo per i simboli giusti.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
% Read the symbol to the right of the head (Sym)
%
symbol(Rs0, Sym, RsRest),
% Apply first found matching rule to the current state (Q0)
% and the current symbol on the right (Sym), resulting in
% a new symbol (NewSym) and an action (Action)
%
once(rule(Q0, Sym, Q1, NewSym, Action)),
% Perform the action using the current list of symbols on the left (Ls0)
% and the updates list of symbols on the right (old right symbol (Sym)
% replaced by the new right symbol (NewSym), which is [NewSym|RsRest]
% with the action resulting in new left Ls1 and new right Ls2
% sets of symbols
%
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
% Recursively perform the Turing engine on the new state, left,
% and right sets of symbols until we hit the final state (qf)
% with final result being left symbols, Ls, and right symbols, Rs
%
perform(Q1, Ls1, Ls, Rs1, Rs).
Grazie mille. –