请解释这个用 Prolog 编写的图灵机模拟器
Please explain this Turing Machine simulator written in Prolog
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] ;
我理解rules/facts中部分变量名的含义：
turing(Tape0, Tape)
- tape0 是输入磁带
- 磁带是输出磁带
rule(Q0, Sym, Q1, NewSym, Action)
- Q0：开始状态
- 符号：符号读取
- Q1：结束状态
- NewSym：要写入的符号
- 动作：如何移动头部
我不明白这些变量的含义 rules/facts:
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])
谁能解释一下？
在图灵机中，在任何给定状态下，写入磁头都指向磁带上的特定位置。头的左边会有符号，头的右边会有符号。
查看第一个主谓词：
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分别是头部符号left和right的列表，在 之前执行操作。而Ls和Rs分别是头部的符号left和right，after 操作已执行。
action(stay, Ls, Ls, Rs, Rs).
这个动作说的是当我停留的时候，头部左右的符号没有变化。
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
这个动作表示当我把头右移动一个符号位置时，符号立即向右移动（也就是Sym 因为 right 符号集是 [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]).
这里，如果左边的一组符号是空（[]）那么移动left意味着左边的符号仍然存在空的 ([]) 和一个新的空白 (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)之后，它在右边[=]有最后一组符号128=] (Rs) 顺序正确，从左到右。但是，左侧的最后一组符号 (Ls) 是从右到左列出的（因为它们的顺序是它们与当前头部位置的接近程度）。因此，为了以正确的顺序显示整个磁带，必须颠倒左侧的符号列表，然后将其添加到右侧的符号集之前。因此，调用：
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
分解 perform/5 谓词：
perform(qf, Ls, Ls, Rs, Rs) :- !.
这表示如果我们处于最终状态 qf，则 最终 左符号列表 Ls 将成为我们的 current 组 left 符号。同样适用于正确的符号。
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).
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] ;
我理解rules/facts中部分变量名的含义：
turing(Tape0, Tape)
- tape0 是输入磁带
- 磁带是输出磁带
rule(Q0, Sym, Q1, NewSym, Action)
- Q0：开始状态
- 符号：符号读取
- Q1：结束状态
- NewSym：要写入的符号
- 动作：如何移动头部
我不明白这些变量的含义 rules/facts:
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])
谁能解释一下？
在图灵机中，在任何给定状态下，写入磁头都指向磁带上的特定位置。头的左边会有符号，头的右边会有符号。
查看第一个主谓词：
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分别是头部符号left和right的列表，在 之前执行操作。而Ls和Rs分别是头部的符号left和right，after 操作已执行。
action(stay, Ls, Ls, Rs, Rs).
这个动作说的是当我停留的时候，头部左右的符号没有变化。
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
这个动作表示当我把头右移动一个符号位置时，符号立即向右移动（也就是Sym 因为 right 符号集是 [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]).
这里，如果左边的一组符号是空（[]）那么移动left意味着左边的符号仍然存在空的 ([]) 和一个新的空白 (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)之后，它在右边[=]有最后一组符号128=] (Rs) 顺序正确，从左到右。但是，左侧的最后一组符号 (Ls) 是从右到左列出的（因为它们的顺序是它们与当前头部位置的接近程度）。因此，为了以正确的顺序显示整个磁带，必须颠倒左侧的符号列表，然后将其添加到右侧的符号集之前。因此，调用：
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
分解 perform/5 谓词：
perform(qf, Ls, Ls, Rs, Rs) :- !.
这表示如果我们处于最终状态 qf，则 最终 左符号列表 Ls 将成为我们的 current 组 left 符号。同样适用于正确的符号。
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).