我正在尝试理解和实现最简单的图灵机，并且如果我有道理的话，希望获得反馈。
我们有一个无限的磁带(让我们说一个名为T的数组，其开头的指针为0)和指令表:
( S , R , W , D , N )
S->STEP (Start at step 1)
R->READ (0 or 1)
W->WRITE (0 or 1)
D->DIRECTION (0=LEFT 1=RIGHT)
N->NEXTSTEP (Non existing step is HALT)
我的理解是3状态2符号是最简单的机器。我不明白的三态。 2个符号，因为我们对读/写使用0和1。
例如:
(1,0,1,1,2)
(1,1,0,1,2)
从步骤1开始，如果Read为0，则{写入1，向右移动)，否则{写入0，向右移动)，然后转到步骤2-不存在，该程序会暂停。
三态是什么意思？该机器是否作为图灵机通过？我们可以简化更多吗？
最佳答案
我认为混淆可能来自您使用“步骤”而不是“状态”。您可以将一台机器的状态视为其内存中的值(尽管正如先前的海报所指出的那样，有些人也将一台机器的状态包含在磁带的内容中，但是，我认为定义并不重要对您的问题)。术语的这种变化可能是您困惑的核心。让我解释一下我在想什么。 :)
您列出了五个数字，例如(1,0,1,1,2)。正确说明状态后，应将其解释为(从左到右读取)“如果机器处于状态1，并且当前方块包含0，则打印1，向右移动，然后更改为状态2。”但是，您使用的“步骤”一词似乎暗示“步骤2”之后必须是“步骤3”，依此类推，实际上，图灵机可以在状态之间来回移动(当然，在那里只能是有限的许多可能状态)。
因此，回答您的问题:
编辑:语法，格式，并删除了对Turing机器的不必要描述。
对评论的回复:
如果我对您的评论有误解，请纠正我，但我并不是要暗示图灵机一次可能处于一种以上的状态，只是可能的状态数可以是任意有限的数。例如，对于三态计算机，您可以标记可能的状态A，B和C。(在您提供的示例中，您将两个可能的状态标记为“1”和“2”)在任何给定时间，这些值(状态)中的一个恰好位于机器的内存中。我们会说“机器处于状态A”或“机器处于状态B”，等等。(您的机器以状态“1”开始，进入状态“2”后终止)。
另外，对于我来说，“一台最简单/最便宜”的机器对我的含义已经不再清楚。已知的最小的通用图灵机(即在给定适当的磁带的情况下可以模拟另一台图灵机的图灵机)需要2个状态和5个符号(请参见the relevant Wikipedia article)。
另一方面，如果您正在寻找比具有相同计算能力的图灵机更简单的东西，那么Post-Turing machines可能会引起您的兴趣。