图灵机无法正确重复给定的序列

Question

我需要编写一个图灵机来重复给定的大写字母序列。磁带的字母可以是 {A, B, _}。例如，如果初始输入为 ABB，则结果为 ABBABB。

我使用图灵机模拟器写这篇文章https://morphett.info/turing/turing.html

我编写的代码的问题是，它返回的是 ABB#ABB，而不是 ABBABB。我不知道如何删除#，因为没有它，我就无法工作。

The logic i wrote:

; 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

Answer 1

让我们首先重写程序以仅使用字母表中的符号：

（状态 2 变为状态 0） 每个符号将有 5 个阶段：

0 A _ r 1a
0 B _ r 1b
0 _ _ l HALT

; reach next(middle) `_`
1a _ _ r 2a
1a * * r 1a

; reach next(last) `_`, then write A
2a _ A l 3a
2a * * r 2a

; return to previous(middle) `_`
3a _ _ l 4a
3a * * l 3a

; return to prevous(first) `_`, then write A
4a _ A r 0
4a * * l 4a

; idem for B (1b, 2b, 3b, 4b)
 

现在我们需要将后半部分左移 1 位：

• 将

  0 _ _ l HALT

  更改为

  0 _ _ r shift1

    ; reach last `_`
    shift1 _ _ l replace_
    shift1 * * r shift1
    
    ; replace with `_`, then replace prevoius with symbol
    replace_ A _ l replaceA
    replace_ B _ l replaceB
    replace_ _ _ l HALT

    ; idem with A and B (replaceA, replaceB)

---

另一种方法是从第二个位置开始复制，然后将第一个复制到中间

_

:

• 将

  0 _ _ l HALT

  更改为

  0 _ _ l cf1

  (copy_first1)
• 从状态

  before0

开始

before0 * * r 0


cf1 _ _ r cf2
cf1 * * l cf1

cf2 A A r cfa

cfa _ A l HALT
cfa * * r cfa

cfb _ B l HALT
cfb * * r cfb

---

最后（如果我们可以使用外部符号）我们可以复制到最终位置，但使用占位符符号，然后替换它们：

    0 A X r 1a
    0 B Y r 1b
    0 * * * 3

    1a _ a l 2
    1a * * r 1a

    1b _ b l 2
    1b * * r 1b

    2 X A r 0
    2 Y B r 0
    2 * * l 2

    3 a A r 3
    3 b B r 3
    3 _ _ * HALT