建立一个确定性的磁带图灵机

Question

我正在尝试制作一个确定性图灵机来执行以下操作：找到任何单词的中间字母。它需要将一个仅包含 a 和 b 的单词作为输入，一旦找到中间字符，它就需要停止并接受。机器需要拒绝任何具有偶数个字母的单词，只接受奇数长度的单词。 Left/right/stay招式都可以在这台机器上使用。

将使用以下符号：STATE, SYMBOL -> STATE, SYMBOL, DIRECTION

(_) = 空白 space

(l) = 左移

(r) = 右移

(s) = 停留

我完全无法想象这台机器，需要帮助启动。我曾尝试自己构建机器，但它对所有输入都不起作用，而且我只能让它对特定单词起作用。如果你能帮助我，我将不胜感激。谢谢

Answer 1

我不清楚你是否需要简单地识别有一个中间符号（即输入大小是奇数），你需要识别这个并结束对中间符号的处理，或者你需要识别这个，擦除输入，将中间符号写到磁带的开头，然后接受。我们将假设其中的第二个，然后讨论如何实现第三个。

解决这个问题的一个简单方法是从输入的开头和结尾划掉成对的符号。如果你运行在划掉整数对后没有符号，那么你停止拒绝；否则，如果您无法为最后一对找到匹配项，那么您将停止接受。这是一个执行此操作的 TM：

Q    T     Q'    T'    D
q0   a,b   q1    A,B   right    // if we have a symbol, begin crossing off
q0   #,A,B hR    #,A,B same     // otherwise, |w| is even so halt reject

q1   a,b   q1    a,b   right    // go to the first blank or marked-off symbol
q1   #,A,B q2    #,A,B left     // then, go one to the left

q2   a,b   q3    A,B   left     // if we have a symbol, mark off the pair
q2   A,B   hA    a,b   same     // otherwise, |w| is odd so halt accept

q3   a,b   q3    a,b   left     // find the last marked-off symbol from the front
q3   A,B   q0    A,B   right    // move one to the right and repeat the whole thing

此 TM 会将 aababab 之类的字符串转换为 AABaBAB，读头位于 a。从这个表格中，我们可以添加一些更多的处理，将磁带变成 a、aababab 等，并将读取磁头留在任何你喜欢的地方。

建立一个确定性的磁带图灵机

Building a deterministic one tape turing machine

diagram

turing-machines

deterministic