设计用于乘法的图灵机

图灵机是一个七元组

(Q, Σ, Γ, δ, q0, qacc, qrej)

其中，

• Q 是一个有限的状态集；

• Σ 是输入字母表，不包含空格符号 t；

• Γ 是带字母表，其中 t ∈ Γ 且 Σ ⊆ Γ；

• δ: (Q × Γ) → (Q × Γ × {L, R}) 是转移函数；

• q0 ∈ Q 是起始状态；

• qacc ∈ Q 是接受状态；

• qrej ∈ Q 是拒绝状态，其中 qrej ≠ qacc。

问题

构建用于两个一元整数相乘的图灵机 (TM)。

解决方案

Multiplication of two unary integers
3*2=6
In Turing Machine 3 represents − 111
                  2 represents − 11

令 ‘M’ 为用于分隔两个整数的符号

这里 B= 空格

M= 用于分隔两个整数的符号

⇑= 磁头

执行乘法后，输出如下：

乘法的 TM 如下所示：

解释

• q0 - 查找输入中的第一个未使用的符号。

• q0 - 查找输入中的第一个未使用的符号。

• q1 - 在第一个因子中找到一个 1；跳到 x 符号

• q2 - 找到 x

• q4 - 在第二个因子中找到一个 1；将其更改为 Y；跳到 =

• q3 - 使用了第二个因子中的所有 1；将 Y 转换回 1

• q5 - 跳到磁带末尾

• q6 - 跳回 =

• q7 - 跳回第二个因子

• q8 - 找到 Y，标记第二个因子中先前使用的 1

• q9 - 跳回第一个因子中的 1

• q12 - 消耗了整个第一个因子；将 x 转换回 1

• q11 - 找到 ⊔

Bhanu Priya

更新于： 2021年6月14日

10K+ 次观看

启动您的 职业生涯

通过完成课程获得认证

开始学习