我的简单图灵机
我正在尝试理解和实现最简单的图灵机，如果我说得通，我希望得到反馈。
我们有一个无限的磁带（假设一个名为 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 开始，如果读取为 0，则 { 写入 1，向右移动) else {写入 0，向右移动)，然后转到步骤 2 - 该步骤不存在，从而暂停程序。
3态是什么意思？这台机器可以作为图灵机吗？我们可以进一步简化吗？
I'm trying to understand and implement the simplest turing machine and would like feedback if I'm making sense.
We have a infinite tape (lets say an array called T with pointer at 0 at the start) and instruction table:
( 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)
My understanding is that a 3-state 2-symbol is the simplest machine. 3-state i don't understand. 2-symbol because we use 0 and 1 for READ/WRITE.
For example:
(1,0,1,1,2)
(1,1,0,1,2)
Starting at step 1, if Read is 0 then { Write 1, Move Right) else {Write 0, Move Right) and then go to step 2 - which does not exist which halts program.
What does 3-state mean? Does this machine pass as turing machine? Can we simplify more?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为混乱可能来自于您使用“步骤”而不是“状态”。您可以将机器的状态视为其内存中的值（尽管正如之前的海报所指出的，有些人也将机器的状态包含在磁带的内容中 - 但是，我认为该定义不相关）对你的问题）。术语的这种变化可能是您困惑的核心。让我解释一下我认为你在想什么。 :)
您给出了五个数字的列表 - 例如，(1,0,1,1,2)。正如您正确陈述的那样，这应该被解释为（从左到右阅读）：“如果机器处于状态 1 并且当前方块包含 0，则打印 1，向右移动，然后更改为状态 2。”然而，您对“步骤”一词的使用似乎表明“步骤 2”后面必须跟着“步骤 3”等，而实际上图灵机可以在状态之间来回移动（当然，有只能是有限多种可能的状态）。
所以回答你的问题：
编辑：语法、格式，并删除了对图灵机的不必要的描述。
评论回复：
如果我误解了您的评论，请纠正我，但我并不是说图灵机一次可以处于多个状态，只是可能的状态数量可以是任何有限的数量。例如，对于三状态机，您可以标记可能的状态 A、B 和 C。（在您提供的示例中，您将两种可能的状态标记为“1”和“2”）在任何给定时间，这些值（状态）之一将位于机器的内存中。我们会说，“机器处于状态 A”或“机器处于状态 B”等（您的机器以状态“1”启动，并在进入状态“2”后终止）。
另外，我不再清楚你所说的“更简单/最”机器是什么意思。已知最小的通用图灵机（即，可以模拟另一台图灵机的图灵机，给定适当的磁带）需要 2 个状态和 5 个符号（请参阅 相关维基百科文章）。
另一方面，如果您正在寻找具有相同计算能力的比图灵机更简单的东西，后图灵机可能会令人感兴趣。
I think the confusion might come from your use of "steps" instead of "states". You can think of a machine's state as the value it has in its memory (although as a previous poster noted, some people also take a machine's state to include the contents of the tape -- however, I don't think that definition is relevant to your question). It's possible that this change in terminology might be at the heart of your confusion. Let me explain what I think it is you're thinking. :)
You gave lists of five numbers -- for example, (1,0,1,1,2). As you correctly state, this should be interpreted (reading from left to right) as "If the machine is in state 1 AND the current square contains a 0, print a 1, move right, and change to state 2." However, your use of the word "step" seems to suggest that that "step 2" must be followed by "step 3", etc., when in reality a Turing machine can go back and forth between states (and of course, there can only be finitely many possible states).
So to answer your questions:
Edits: Grammar, Formatting, and removed a needless description of Turing machines.
Response to comment:
Correct me if I'm misinterpreting your comment, but I did not mean to suggest a Turing machine could be in more than one state at a time, only that the number of possible states can be any finite number. For example, for a 3-state machine, you might label the possible states A, B, and C. (In the example you provided, you labeled the two possible states as '1' and '2') At any given time, exactly one of those values (states) would be in the machine's memory. We would say, "the machine is in state A" or "the machine is in state B", etc. (Your machine starts in state '1' and terminates after it enters state '2').
Also, it's no longer clear to me what you mean by a "simpler/est" machine. The smallest known Universal Turing machine (i.e., a Turing machine that can simulate another Turing machine, given an appropriate tape) requires 2 states and 5 symbols (see the relevant Wikipedia article).
On the other hand, if you're looking for something simpler than a Turing machine with the same computation power, Post-Turing machines might be of interest.
我相信状态的概念与有限状态机中的概念基本相同。如果我记得的话，您需要一个单独的终止状态，图灵机可以在完成运行程序后转换到该状态。至于为什么有3个状态我猜其他两个状态分别是初始化和执行。
不幸的是，这些都不能保证是正确的，但我想无论如何我都会发表我的想法，因为这个问题已经有 5 个小时没有得到解答了。我怀疑如果您在 cstheory.stackexchange.com 上重新提出这个问题，您可能会得到更好/更明确的答案。
I believe that the concept of state is basically the same as in Finite State Machines. If I recall, you need a separate termination state, to which the turing machine can transition after it has finished running the program. As for why 3 states I'd guess that the other two states are for intialisation and execution respectively.
Unfortunately none of that is guaranteed to be correct, but I thought I'd post my thoughts anyway since the question was unanswered for 5 hours. I suspect if you were to re-ask this question on cstheory.stackexchange.com you might get a better/more definative answer.
图灵机上下文中的“状态”应明确描述的是：（i）当前指令，或（ii）磁带上的符号列表以及当前指令，或（iii）磁带上的符号与当前指令一起放置在扫描符号的左侧或扫描符号的右侧。 参考
"State" in the context of Turing machines should be clarified as to which is being described: (i) the current instruction, or (ii) the list of symbols on the tape together with the current instruction, or (iii) the list of symbols on the tape together with the current instruction placed to the left of the scanned symbol or to the right of the scanned symbol. Reference