我的简单图灵机

Question

我正在努力理解和实施最简单的图灵机,如果我有意义的话,我想要反馈.

我们有一个无限的磁带(假设一个名为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进行READ/WRITE.

例如:

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

从步骤1开始,如果Read为0,则{Write 1,Move Right> else {Write 0,Move Right>,然后转到步骤2 - 不存在停止程序.

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

Answer 1

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

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