請解釋寫在序言本圖靈機模擬器

Question

的Wikipedia Prolog article包括該圖靈機模擬器：

turing(Tape0, Tape) :- 
    perform(q0, [], Ls, Tape0, Rs), 
    reverse(Ls, Ls1), 
    append(Ls1, Rs, Tape). 

perform(qf, Ls, Ls, Rs, Rs) :- !. 
perform(Q0, Ls0, Ls, Rs0, Rs) :- 
    symbol(Rs0, Sym, RsRest), 
    once(rule(Q0, Sym, Q1, NewSym, Action)), 
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1), 
    perform(Q1, Ls1, Ls, Rs1, Rs). 

symbol([], b, []). 
symbol([Sym|Rs], Sym, Rs). 

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). 
action(stay, Ls, Ls, Rs, Rs). 
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs). 

left([], [], Rs0, [b|Rs0]). 
left([L|Ls], Ls, Rs, [L|Rs]). 

它給出了一個示例程序：

• 在讀「1」移動頭對。
• 閱讀空白時，寫入一個並進入最終狀態。

計劃：

rule(q0, 1, q0, 1, right). 
rule(q0, b, qf, 1, stay). 

程序運行如圖所示：

?- turing([1,1,1], Ts). 
Ts = [1, 1, 1, 1] ; 

我瞭解的一些規則/事實變量名的含義是：

turing(Tape0, Tape)

• TAPE0是輸入帶
• 膠帶是輸出磁帶

rule(Q0, Sym, Q1, NewSym, Action)

• Q0：啓動狀態
• 符號：符號讀
• Q1：端狀態
• NewSym ：寫符號
• 行動：如何莫已經頭

我不明白的變量的含義在這些規則/事實：

perform(Q0, Ls0, Ls, Rs0, Rs) 

symbol([Sym|Rs], Sym, Rs) 

action(left/stay/right, Ls0, Ls, Rs0, Rs) 

left([L|Ls], Ls, Rs, [L|Rs]) 

任何人都可以解釋一下嗎？

Answer 1

在圖靈機中，在任何給定的狀態下，寫頭指向磁帶上的特定位置。頭上會有符號，頭上還有符號。

縱觀第一，主謂：

turing(Tape0, Tape) :- 
    perform(q0, [], Ls, Tape0, Rs), 
    reverse(Ls, Ls1), 
    append(Ls1, Rs, Tape). 

這將通過調用perform/5「本機運行」。 perform(Q0, Ls0, Ls, Rs0, Rs)的參數代表：

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 

最初，頭部沒有符號。 Tape0最初包含頭部右側的所有符號。以「本機運行」，在主謂稱：

perform(Q0, [], Ls, Tape0, Rs) 

它開始的初始狀態，Q0，已經離開了頭，開始用（[]）無符號和有符號的Tape0權頭開始。期望在完成查詢後，使Ls例示爲頭部左側的最後一組符號，並且Rs頭部右側的最後一組符號。

其他現在支持perform/5。

symbol([Sym|Rs], Sym, Rs) 

這定義符號[Sym|Rs]的列表，並在該列表中（Sym）和列表（Rs）的其餘部分的第一個符號之間的關係。 perform/5使用此謂詞讀取當前位於頭部右側的下一個符號。

爲了做到這在它被使用的上下文正常工作，perform/5謂詞維持Rs0可變的，使得它是正確爲了其中所述列表的頭部是在右邊的第一符號，第二元件該列表是右側的以下符號，依此類推。請注意，這不是左側符號列表的情況。左側列表保留在反向符號如何在磁帶上出現的順序。原因是這樣，他們可以按照他們離目前頭部位置多遠的順序來考慮。稍後再說。

action(left/stay/right, Ls0, Ls, Rs0, Rs) 

這就是行動是。 :)它的作用是執行給定的操作，並提供正確更新的列表，在採取一個操作後，新頭部位置的左側和右側是什麼。 Ls0和Rs0分別是左邊和右邊的頭部，分別是之前的動作執行。並且Ls和Rs分別是左邊的和右邊的的頭部，分別是之後的的動作被執行。

action(stay, Ls, Ls, Rs, Rs). 

這個動作說，當我留，符號的左邊和頭部右側沒有改變。

action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs). 

這個動作說，當我立即移動磁頭右一個符號位置，符號到右（這是Sym由於右組符號是[Sym|Rs]）立即成爲符號往左邊。左邊的一組符號最初是Ls0，並且變成[Sym|Ls0]。右邊的符號列表最初爲[Sym|Rs]，並且變成了Rs。

left的動作比stay或right稍微複雜一些，因爲當左側沒有更多符號且指示左移時，頭仍然向左移動，右側出現空白。所以left它分解成一個單獨的，小謂：

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). 

left([], [], Rs0, [b|Rs0]). 

這裏，如果左邊的符號集是空（[]），然後移動離開表示左符號保留爲空（[]）和新的空白（b）出現在頭部右側，原始右側符號組的右側（右側列表從Rs0更改爲[b|Rs0]）。

left([L|Ls], Ls, Rs, [L|Rs]). 

這裏左邊有一些符號，動作是左移。左邊的一組初始符號是[L|Ls]（L是緊靠頭部左側的符號），並且頭部右側的初始符號集合是Rs。當頭移動離開時，左邊的第一個符號成爲右邊的第一個符號。所以更新後的左邊符號集是Ls，更新的右邊符號集是[L|Rs]。

的action(left, ...)謂詞可能已被寫入沒有輔助謂詞，left/4，這種方式：

action(left, [], [], Rs0, [b|Rs0]). 
action(left, [L|Ls], Ls, Rs, [L|Rs]). 

回到左邊的列表和原turing/2斷言：後turing/2電話perform(q0, [], Ls, Tape0, Rs)，它有一個最後一組右邊的符號（Rs），它們按正確的順序從左到右。但是，左邊的最後一組符號（Ls）從右到左列出（因爲它們按照與當前頭位置的接近程度排列）。因此，爲了以正確的順序顯示整個磁帶，必須顛倒左側的符號列表，然後將其前置到正確的符號集。因此，電話：

reverse(Ls, Ls1), 
append(Ls1, Rs, Tape). 

打破perform/5斷言：

perform(qf, Ls, Ls, Rs, Rs) :- !. 

這是說，如果我們在最後的狀態qf，那麼最後留下的符號，Ls的名單，成爲我們的當前一套左符號。類似的正確的符號。

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).