构建一个执行两个一元数乘法的图灵机

算法

步骤 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}

• δ ⇒ 由上述状态转换图给出。

Bhanu Priya

更新于： 2021 年 6 月 15 日

7K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习