如何实现一台将二进制转换为一元的图灵机？

核心逻辑 #

输入是无符号二进制字符串（比如101），输出是对应十进制数值的一元表示——也就是数值有多大，就输出多少个1（比如101对应5，输出11111）。图灵机的核心是逐位解析二进制，通过翻倍+累加的方式生成对应的一元串：

• 遇到二进制的0：当前一元串翻倍（因为二进制的0代表权重乘2）
• 遇到二进制的1：当前一元串翻倍后再加1（权重乘2加1）

基础定义 #

符号集 #

• 输入符号：0、1（二进制数字）
• 辅助符号：#（空白符，用于标记纸带边界、已处理的二进制位）
• 输出符号：1（一元表示的唯一符号）

状态集合 #

• q0：初始状态，定位到二进制输入的有效起始位
• q1：处理当前二进制位的状态
• q2：执行一元串翻倍操作的状态
• q3：给一元串追加1个1的状态
• q4：切换到下一个二进制位的状态
• q5：清理纸带残留标记的状态
• q_accept：转换完成的接受状态

转移规则（状态转换表） #

以下是图灵机的核心转移规则，格式为 (当前状态, 当前读取符号) → (新状态, 写入符号, 移动方向)，其中方向用L（左移）、R（右移）、N（不动）表示：

# 初始定位：跳过前导空白和0，找到第一个有效1
(q0, 1) → (q1, 1, R)
(q0, 0) → (q0, 0, R)
(q0, #) → (q_accept, #, N)  # 空输入直接结束

# 标记当前二进制位为已处理，开始执行翻倍
(q1, 1) → (q2, #, L)
(q1, 0) → (q2, #, L)
(q1, #) → (q5, #, L)  # 所有二进制位处理完毕，进入清理阶段

# 翻倍操作：遍历现有一元串，在末尾复制一份相同数量的1
(q2, 1) → (q2, 1, L)    # 移动到一元串的左端
(q2, #) → (q3, #, R)    # 到达左端，开始向右遍历复制
(q3, 1) → (q3, 1, R)    # 遍历一元串
(q3, #) → (q3, 1, L)    # 在末尾写一个1，返回左端
(q3, 1) → (q3, 1, L)    # 返回至一元串左端
(q3, #) → (q4, #, R)    # 翻倍完成，准备处理下一位

# 处理二进制1的额外操作：追加一个1；或切换到下一位
(q4, #) → (q3, 1, L)    # 若当前处理的是1，翻倍后追加1个1
(q4, 1) → (q1, 1, R)    # 移动到下一个未处理的二进制位
(q4, 0) → (q1, 0, R)
(q4, #) → (q5, #, L)

# 清理纸带：移除所有#标记，只保留一元的1
(q5, #) → (q5, #, L)    # 移动到纸带最左端
(q5, 1) → (q5, 1, R)    # 向右遍历，保留所有1
(q5, #) → (q_accept, #, N)  # 清理完成，结束转换

示例运行（输入101） #

初始纸带：# 1 0 1 #（#代表空白区域）

1. 从q0启动，定位到第一个1，进入q1后右移到0
2. 处理0：标记为#，进入q2执行翻倍（初始一元串为空，翻倍后仍为空）
3. 翻倍完成进入q4，右移到下一个1，进入q1
4. 处理1：标记为#，进入q2翻倍空串，再进入q3追加1个1，此时纸带变为# # # 1 #
5. 返回q4后右移到末尾#，进入q5清理
6. 清理所有#标记，最终纸带为# 1 1 1 1 1 #，即输出11111

内容的提问来源于stack exchange，提问作者user20989422