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

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:要写的符号

Action :如何移动头部

我不明白这些规则/事实中变量的含义:

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)

这就是行动的地方。 :) 它的作用是执行给定的 Action ，并在执行该 Action 后提供正确更新的新头部位置左侧和右侧的列表。 Ls0和 Rs0分别是执行 Action 之前头部左侧和右侧的符号列表。和 Ls和 Rs分别是 Action 完成后头部左侧和右侧的符号。

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

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

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

此操作表示，当我将头部向右移动一个符号位置时，紧靠右侧的符号(即 Sym，因为右侧的一组符号是 [Sym|Rs])立即变为左侧的符号。左边的一组符号最初是， Ls0并变成 [Sym|Ls0] .右侧的符号列表最初是 [Sym|Rs]并变成 Rs .
left action 比 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]).

这里左边有一些符号， Action 是向左移动。左边的初始符号集是 [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).