图灵机实现 2 的指数运算 2^n (n≥0)

TM 设计思想: 设计一个图灵机来计算 2 的指数运算 2^n，其中 n 是非负整数。可以使用一个计数器来记录当前的指数值，并使用循环来进行迭代计算。

TM 定义: 状态集 Q = {q0, q1, q2, q3, q4} 输入字母表 Σ = {1} 工作字母表 Γ = {1, 2, '#'}

初始状态 q0 终止状态 F = {q4}

转移函数 δ 定义如下:

δ(q0, 1) = (q1, 2, R) // 将输入的 1 替换为 2，并将状态切换到 q1
δ(q1, 1) = (q1, 1, R) // 保持计数器不变，继续读取输入
δ(q1, '#') = (q2, '#', L) // 当读取到空格时，将状态切换到 q2，并将头指针移动到最左边
δ(q2, 1) = (q3, '#', L) // 将计数器减 1，并将头指针移动到最左边
δ(q3, 2) = (q0, 2, R) // 将计数器加倍，并将头指针移动到最右边
δ(q3, 1) = (q3, 1, L) // 保持计数器不变，继续将头指针向左移动
δ(q3, '#') = (q4, '#', R) // 当计数器减到 0 时，将状态切换到 q4，并将头指针移动到最右边

一实例的识别过程: 假设输入为 111，即要计算 2^3: