finite-automata - 图灵机

Question

我正在读一本关于语言和自动机的书，但我不了解图灵机。我已经自学了 DFA 的 NFA 和 Pushdown Automata，没有任何问题。有人可以解释这是在做什么吗？

B = {w#w|w ∈ {0, 1}*}

下图包含 Ml 的磁带在输入 011000#011000 开始时在阶段 2 和 3 中计算时的几个快照。

非常感谢！

Answer 1

“想象一排无穷无尽的酒店房间，每个房间都包含一个灯泡和一个控制它的开关。最初，所有房间都是黑暗的。机器人从其中一个房间开始，并具有操作开关并移动到相邻房间的能力房间。

机器人有几种可以处于的状态，每种状态都根据当前房间是亮还是暗来决定它应该做什么。例如，机器人的规则可能包括以下状态：

“害怕”状态：

如果房间很暗，请打开灯并移动到左侧的房间。

如果房间很亮，什么也不做，进入“正常”状态。“正常”状态：

如果房间很亮，请关掉灯并移动到右侧的房间。

否则，进入“害怕”状态。

一种特殊状态是“停止”状态。当机器人发现自己处于这种状态时，该过程就完成了。

假设一个机器人有 n 个状态（不包括“停止”状态），它停止了。此时灯室的最大数量是多少？

该系统直接与图灵机相提并论。旅馆是磁带，机器人是图灵机，暗室和亮室是 0 单元和 1 单元。”

它来自googology wiki。我提出了一个想法，但是，当然，从我开始，这篇文章就得到了改进。

Answer 2

图灵机是一种带有存储符号的磁带的假设机器。它可以有多个磁头，可以从磁带读取符号或将符号写入磁带。

现在你的语法说 B = {w#w|w ∈ {0, 1}*}，即任何形式为“w#w”的字符串，其中 w 是 0 和 1 的任意组合，或者根本没有。因此，对于这个特定示例，假设 w = 011000。结果字符串将为 011000#011000 并且您的图灵机将验证它是否遵循此语法。

在这种情况下，您的图灵机只有一个头。它从字符串的开头开始。读取第一个字符，即 0。将其标记为“x”：表示我已阅读此内容。然后在 # 之后立即检查它刚刚读取的内容是否匹配。在这种情况下，它也为 0，因此将其标记为匹配“x”。然后它回到之前的位置并对下一个字符做同样的事情。它一直这样做，直到达到#。当它读取 hash 或 # 时，它检查字符串的结尾，如果它是字符串的结尾，它接受这个字符串，说是的，这遵循给定的语法。