5

我正在尝试理解和实现最简单的图灵机，如果我说得通，我希望得到反馈。

我们有一个无限的磁带（假设有一个名为 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 符号，因为我们使用 0 和 1 进行读/写。

例如：

(1,0,1,1,2)
(1,1,0,1,2)

从第 1 步开始，如果 Read 为 0，则 { Write 1, Move Right) else {Write 0, Move Right) 然后转到第 2 步 - 这不存在会停止程序。

三态是什么意思？这台机器可以作为图灵机吗？我们可以简化更多吗？

4

3 回答 3

2

我认为混淆可能来自您使用“步骤”而不是“状态”。您可以将机器的状态视为它在其内存中的值（尽管正如之前的海报所指出的，有些人也将机器的状态包含在磁带的内容中——但是，我认为这个定义并不相关你的问题）。术语的这种变化可能是您困惑的核心。让我解释一下我认为你在想什么。:)

你给出了五个数字的列表——例如，(1,0,1,1,2)。正如您正确陈述的那样，这应该被解释为（从左到右阅读）“如果机器处于状态 1 并且当前方块包含 0，则打印 1，向右移动，然后更改为状态 2。” 但是，您对“步骤”一词的使用似乎表明“步骤 2”之后必须跟随“步骤 3”等，而实际上图灵机可以在状态之间来回切换（当然，还有只能是有限多个可能的状态）。

所以回答你的问题：

  • 图灵机跟踪的是“状态”而不是“步骤”；
  • 您所描述的是合法的图灵机；
  • 一个更简单（尽管其他方面无趣）的图灵机将是一个以 HALT 状态启动的图灵机。

编辑：语法、格式化，并删除了对图灵机的不必要描述。

对评论的回应：如果我误解了您的评论，请纠正我，但我并不是说图灵机一次可以处于多个状态，只是可能的状态数可以是任何有限数。例如，对于三态机器，您可能会标记可能的状态 A、B 和 C。（在您提供的示例中，您将两种可能的状态标记为“1”和“2”）在任何给定时间，这些值（状态）中的一个恰好在机器的内存中。我们会说，“机器处于状态 A”或“机器处于状态 B”等（你的机器从状态 '1' 开始，进入状态 '2' 后终止）。

此外，我不再清楚您所说的“更简单/最简单”的机器是什么意思。已知最小的通用图灵机（即，在给定适当磁带的情况下，可以模拟另一台图灵机的图灵机）需要 2 个状态和 5 个符号（参见相关的 Wikipedia 文章）。

另一方面，如果您正在寻找比具有相同计算能力的图灵机更简单的东西，那么后图灵机可能会感兴趣。

于 2010-09-23T03:30:27.873 回答
1

我相信状态的概念与有限状态机中的基本相同。如果我记得，您需要一个单独的终止状态，图灵机在完成程序运行后可以转换到该状态。至于为什么 3 个状态，我猜其他两个状态分别用于初始化和执行。

不幸的是，这些都不能保证是正确的，但我想我还是会发表我的想法，因为这个问题有 5 个小时没有得到回答。我怀疑如果您在 cstheory.stackexchange.com 上重新提出这个问题，您可能会得到一个更好/更明确的答案。

于 2010-09-22T14:02:06.720 回答
0

图灵机上下文中的“状态”应明确说明正在描述的是：（i）当前指令，或（ii）磁带上的符号列表以及当前指令，或（iii）磁带上的符号与当前指令一起放置在已扫描符号的左侧或已扫描符号的右侧。参考

于 2010-09-23T02:38:29.367 回答