图灵机无法正确重复给定序列：输出含#符号问题求助

问题背景 #

需求是实现一台图灵机，能重复给定的大写字母序列（磁带字母表限定为{A, B, _}），例如输入ABB需输出ABBABB。使用在线图灵机模拟器开发时，现有代码输出结果为ABB#ABB，移除#符号后程序无法正常运行。

原代码如下：

; Repeats a given sequence of capital letters
; Alphabet: {A, B, _}
; States: {0, 1, 2, 3, 4, 5, 6, HALT}

; State 0: Move to the first blank (_)
0 A A r 0
0 B B r 0
0 _ # l 1

; State 1: Move left to the start of the input sequence
1 A A l 1
1 B B l 1
1 _ _ r 2

; State 2: Mark and copy each character to the end
2 A X r 3
2 B Y r 4
2 # # l HALT

; State 3: Find end and copy 'A'
3 A A r 3
3 B B r 3
3 # # r 3
3 _ A l 5

; State 4: Find end and copy 'B'
4 A A r 4
4 B B r 4
4 # # r 4
4 _ B l 6

; State 5: Move back to the start after copying 'A'
5 A A l 5
5 B B l 5
5 # # l 5
5 X A r 2

; State 6: Move back to the start after copying 'B'
6 A A l 6
6 B B l 6
6 # # l 6
6 Y B r 2

问题分析与修复 #

原代码的核心问题是引入了磁带字母表外的#作为输入结束标记，违反了{A,B,_}的限定。我们可以通过调整状态逻辑，直接利用空白_来标记输入结束，无需额外符号。

修改后的代码如下：

; 重复给定大写字母序列
; 字母表: {A, B, _}
; 状态: {0, 1, 2, 3, 4, 5, 6, HALT}

; 状态0: 移动到输入序列后的第一个空白(_)
0 A A r 0
0 B B r 0
0 _ _ l 1  ; 去掉#，直接用空白标记位置

; 状态1: 移动到输入序列的起始位置
1 A A l 1
1 B B l 1
1 _ _ r 2

; 状态2: 标记并复制每个字符到末尾
2 A X r 3
2 B Y r 4
2 _ _ l HALT  ; 遇到空白则停止，替代原#的终止逻辑

; 状态3: 找到末尾并复制'A'
3 A A r 3
3 B B r 3
3 _ A l 5  ; 去掉#的判断，直接定位到末尾空白

; 状态4: 找到末尾并复制'B'
4 A A r 4
4 B B r 4
4 _ B l 6  ; 去掉#的判断，直接定位到末尾空白

; 状态5: 复制'A'后返回起始位置
5 A A l 5
5 B B l 5
5 X A r 2  ; 去掉#的判断，直接寻找标记X

; 状态6: 复制'B'后返回起始位置
6 A A l 6
6 B B l 6
6 Y B r 2  ; 去掉#的判断，直接寻找标记Y

关键修改点 #

• 移除所有涉及#的状态转移，改用磁带允许的_作为结束标记
• 状态0中遇到空白时不再写入#，直接向左跳转
• 状态2中遇到空白时触发停机，替代原有的#判断
• 复制和返回阶段的状态转移不再处理#，只关注有效字符和标记

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