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是输入磁带
-
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])
谁有人解释一下？
1 回答
在图灵机中，在任何给定状态下，写头指向磁带上的特定位置 . 头部左侧会有符号，头部会有符号 .
看第一个主谓词：
它将通过调用
perform/5来"run the machine" .perform(Q0, Ls0, Ls, Rs0, Rs)的参数表示：最初，头部没有符号 .
Tape0最初包含头部右侧的所有符号 . 要"run the machine"，主谓词调用：它从初始状态
Q0开始，头部没有符号（[]），并且头部右侧的符号在Tape0中开始 . 在查询完成时，期望Ls实例化头部左边的最后一组符号，并且Rs是头部右边的最后一组符号 .其他所有东西现在都支持
perform/5.这定义了符号列表
[Sym|Rs]与该列表中的第一个符号（Sym）和列表的其余部分（Rs）之间的关系 .perform/5使用此谓词来读取当前位于头部右侧的下一个符号 .为了使其在使用的上下文中正常工作，
perform/5谓词维护Rs0变量，使其正确顺序，其中列表的头部是右边的第一个符号，列表的第二个元素是以下符号在右边，等等 . 请注意，这不是左侧符号列表的情况 . 左侧列表的维护顺序与符号在磁带上的显示方式相反 . 原因是它们可以按当前头部位置的剩余距离来考虑 . 稍后更多关于这一点 .这就是行动的所在 . :)在采取一个动作之后，新头部位置的左右两侧's role is to perform the given action and provide the correctly updated lists of what' . 在执行操作之前，
Ls0和Rs0分别是头部左侧和右侧的符号列表 . 并且Ls和Rs分别是执行动作后头部左右的符号 .这个动作说当我留下时，头部左侧和右侧的符号不会改变 .
这个动作表示当我将头部向右移动一个符号位置时，右边的符号（自右边符号集为
[Sym|Rs]后为Sym）成为左边的符号 . 左边的符号集最初为Ls0，变为[Sym|Ls0]. 右边的符号列表最初为[Sym|Rs]，变为Rs.left动作比stay或right稍微复杂一点，因为当左侧没有更多符号并且指示向左移动时，头部仍向左移动并且右侧出现空白 . 所以left它被分解成一个单独的小谓词：这里，如果左边的一组符号是空的（
[]），那么向左移动意味着左边的符号保持为空（[]），并且在头部右边出现一个新的空白（b），位于原始右边符号集的头部（右侧列表从Rs0变为[b|Rs0]） .这里左边有一些符号，动作是向左移动 . 左边的初始符号集是
[L|Ls]（L是头部左侧的符号），头部右边的初始符号集是Rs. 当头向左移动时，左边的第一个符号成为右边的第一个符号 . 因此更新的左符号集是Ls，更新的右符号集是[L|Rs].action(left, ...)谓词可能是在没有辅助谓词的情况下编写的，left/4，这样：返回左侧列表和原始
turing/2谓词：在turing/2调用perform(q0, [], Ls, Tape0, Rs)之后，它在右侧（Rs）有一组最终符号，这些符号的顺序是从左到右 . 但是，左边的最后一组符号（Ls）从右到左列出（因为它们与当前头部位置的接近程度） . 因此，为了以正确的顺序显示整个磁带，左侧列表必须反转符号，然后将其添加到正确的符号集之前 . 因此，电话：分解
perform/5谓词：这表示如果我们处于最终状态
qf，那么左符号的最终列表Ls将成为我们当前的左符号集 . 同样适用于正确的符号 .