解释一个图灵机的计算

Question

我在解释这个图灵机实际上做什么时遇到了一些麻烦（即，我不确定如何用简单的英文来解释它）。

相信我已创建使用I给出（虽然不是100％在此任一）中的过渡表正确的状态图。

从我可以看到这个TM将在接受状态(q2)停止每当输入是形式

(a || b || B)*Ba*c(a || b || c || B)*的，

即是a的，b的，和空白的任何量（但不是c's），后面至少有一个空格，任何数量的a's，以及正好一个c。自从我们第一次找到c后，任何事情都可能发生。

我想我的问题是

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

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

Answer 1

一些观察：

1. Q0读取左到右，不改变磁带，并停止当它击中℃。
2. q1从左到右读取，交换a和b，当它看到B时暂停，并在它碰到a时转向。
3. 为TM停止的唯一方法是，如果
   • 有交流电的地方磁带到初始磁带位置的右侧上
   • 2010年第一季度，在最后一关从右到左看到仅有B并且在c的左边留下第一个c和最右边的B之间的一个a。
4. Q1改变所述第一c和最右边的B之间的一切是c至AB的左侧最终

给定的初始磁带配置> BxBycz，机器将总是在配置暂停> BXB（一^ | Y |）CZ。它接受任何包含c的字符串。 （q1，a）=（q0，b，L）和f（q1，b）=（q1，a，L）定义的转换函数，表中的状态图不一致。 ），但是你的图表显示了f（q1，a）=（q1，a，L）和f（q1，b）=（q0，b，L）。