请解释这个用Prolog编写的图灵机模拟器

Question

在维基百科文章的Prolog包括该图灵机模拟器:

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是输入磁带
• tape是输出磁带

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

• Q0:开始状态
• Sym:符号读取
• 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的符号列表。和和分别是动作执行后头部左侧和右侧的符号。LsRs

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

这个动作表示当我停留时，头部左侧和右侧的符号不会改变。

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

这个动作表示，当我将头部向右移动一个符号位置时，紧邻右侧的符号（这是Sym因为右侧的符号集是[Sym|Rs]）变成紧邻左侧的符号。左边的一组符号原来是 ，Ls0变成[Sym|Ls0]。右侧的符号列表最初是[Sym|Rs]，现在变为Rs。

动作比orleft稍微复杂一些，因为当左侧没有更多符号并且指示向左移动时，头部仍然向左移动，并且右侧出现空白。所以它被分解成一个单独的小谓词：stayrightleft

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)有最后一组符号( )，这些符号的顺序正确，从左到右。然而，左侧 ( ) 的最后一组符号是从右到左列出的（因为它们是按照它们与当前头部位置的接近程度排列的）。因此，为了以正确的顺序显示整个磁带，必须反转左侧的符号列表，然后将其添加到右侧的符号集之前。因此，调用：RsLs

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