解釋一個圖靈機的計算

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）。