構建一個執行兩個一元數乘法的圖靈機

演算法

步驟 1 - 讀取最左邊的“0”，將其替換為“x”，然後向右移動以處理“#”之後的下一個符號。

步驟 2 - 將符號“0”替換為 x，並向右移動，到達“#”之後的第一個“B”。

步驟 3 - 將 B 替換為“0”，並向左移動，直到到達最近的“x”。

步驟 4 - 將“x”替換為 0，並向右移動以處理被乘數的下一個符號。

步驟 5 - 重複步驟 2、3 和 4，直到處理完被乘數的所有符號。

步驟 6 - 向左移動，將乘數的符號“x”替換為“0”。

步驟 7 - 重複步驟 1 到 6，直到處理完乘數的所有符號。

圖靈機

圖靈機 (TM) 如下所示

圖靈機 M 由以下給出

M = (Q, Σ, Γ, δ, q0, B, F)

其中，

  • Q = {q0, q1, q2, q3, q4, q5, q6}

  • Σ = {0, #}

  • Γ = {0, #, x, B}

  • q0 = {q0}

  • B = {B}

  • F = {q6}

  • δ ⇒ 由上述狀態轉換圖給出。

更新於： 2021 年 6 月 15 日

7K+ 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告