turing-machines - 解释图灵机的计算

Question

我在解释这台图灵机的实际功能时遇到了一些麻烦（即，我不确定如何用简单的英语解释它）。

我相信我已经使用给定的转换表正确地创建了状态图（尽管也不是 100%）。

据我所知，(q2)只要输入的形式为，这个 TM 就会停止在接受状态

(a || b || B)*Ba*c(a || b || c || B)*,

即任意数量的a's、b's 和空白（但没有c's），后跟至少一个空白、任意数量的a's 和恰好一个c。任何事情都可能发生，因为我们在找到 first 时就离开了c。

我想我的问题是

a) 到目前为止我的工作是否正确？和

b) 对这个图灵机是否有更有意义的解释（即比我写的输入停止的更丰富的描述(q2)）。

Answer 1

一些观察：

1. q0 从左到右读取，不更换磁带，并在碰到 c 时停止。
2. q1 从左到右读取，交换 a 和 b，当它看到 B 时停止，当它碰到 a 时转身。
3. TM 停止的唯一方法是
   • 在磁带初始位置右侧的某处有交流电
   • 在 q1 中，从右到左的最后一次通过只看到 b，并且只在第一个 c 和 c 左侧最右边的 B 之间留下 a。
4. q1 最终将第一个 c 和该 c 左侧最右边的 b 之间的所有内容更改为 ab

给定初始磁带配置 >BxBycz，机器将始终在配置 >BxB(a^|y|)cz 中停止。它接受任何包含 c 的字符串。

您的状态图与表格不一致，因为表格定义了转换函数，因此 f(q1, a) = (q0, b, L) 和 f(q1, b) = (q1, a, L)，但是您的图表显示 f(q1, a) = (q1, a, L) 和 f(q1, b) = (q0, b, L)。