list27.txt

000(023Rb|001Rb)
001(017La|002Rb)  find 1
002(021La|003Rb)  find 2
003(021La|004La)  place c2
004(009Rb|005Lb)
005(004Ra|005La)  向左找到 0, 1 -> 0
006(008La|007La)
007(009Rb|007La)  向左找到 0, 重写成 0
008(009Ra|008La)  向左找到 0, 重写成 0
009(010Ra|026Ra)
010(010Rb|011Ra)  向右找到 1, 重写成 1
011(012Rb|011Rb)  search the first 0 in the right, move 0 right
012(014La|013La)
013(006Lb|013Lb)  向左找到 0， 重写成 1
014(015La|014Lb)  search 00, replace to 11
015(016Rb|019Lb)  search 00, replace to 11
016(017Lb|ERR--)  search 00, replace to 11
017(018Lb|017Lb)  search 0, replace to 1
018(009Ra|025La)
019(020Rb|019Lb)  向左找到 0, 重写成 1
020(002Rb|020Rb)  向右找到 0, 重写成 1 
021(022La|021Lb)  find prime
022(000Ra|024Lb)  21-24 的过渡
023(024Lb|023Rb)  向右找到0, 重写成 1 
024(000Ra|024Lb)  找到隔板右边的数/找到开头， 开始判断 prime
025(HALT-|024Rb)
026(018Lb|026Rb)  向右找到 0, 重写成 1 

pseudocode.txt

isprime(m): Given 0 1^m 0 on the tape, test whether m is prime
            the Turing machine starts at the first '1', indexed a(1)
    if m == 1: return false
    if m == 2: return true
    for d = 2 ... m - 2:
        a(d + 1) := 0
        Now define 2 cursors, represented as 0's on the tape:
        c1 starting at position 1, and c2 starting at position d+2.
        while true:
            advance c1 -- if c1 is at position d, move it to position 1;
                otherwise increase its position by 1.
            if c2 is at position m:
                remove c2
                a(d+1) := 1
                remove c1
                if c1 was at position d:
                    return true
                else break
            move c2 forward 1
    return false
When returning from the function, the symbol to the left of the initial '0' is examined 
to determine whether it was called on the left or right number.

Program starts here:
for n = 4, 6, 8, ...
    Initialize the tape to a row of (n + 1) 1's.
    for i = n, n-1, ..., 1:
        Write a 0 at the ith location, dividing the tape into the unary numbers 
        (i - 1) and (n + 1 - i).
        Call isprime on the right-hand number (n + 1 - i).
        If it is prime:
            Call isprime on the left-hand number (i - 1).
            If it is also prime, continue to the next value of n.
    If no pair contained 2 primes, halt.

source27.txt

# the comments in this one aren't that accurate

100		- - -		1 R 110
110		0 L 314		1 R 120		# special-case 1
120		0 L 350		1 R 125		# special-case 2
125		0 L 350		0 L 126		# place c2, or find that we have tried all the divisors
126		- - -		1 L 130		# a(d+1) 
130		0 R 140		0 L 130
140		1 R 220		- - -		# a(1) = 1; start with a(2)

# advance c1, starting on a(d)
200		0 L 210		0 L 205		# test a(d)
205		1 R 220		0 L 205
# wrapping around
210		0 R 220		0 L 210

220		0 R 230		- - -		# write c1
230		1 R 230		0 R 250
# at d+2. time to advance c2
250		1 R 270		1 R 250
# at new c2 position
270		0 L 290		0 L 280
280		1 L 200		1 L 280
# hit end of number; at a(p)
290		0 L 300		1 L 290
300		1 R 310		1 L 320		# test a(d)
# found divisor. return false
310		1 L 314		- - -		# erasing a(d+1)
314		1 L 315		1 L 314		# erasing a(i) or ???
315		0 R 900		0 L 700
# found a non-divisor
320		1 R 330		1 L 320		# erase c1
330		1 R 120		1 R 330		# erase d+1

# at p-1. tried all divisors; return true
350		0 L 360		1 L 350
360		0 R %524	1 L 560


%524	1 R 525		- - -		# add a 1 on the left of the number
525		1 L 560		1 R 525		# erase divider between the 2 prime candidates

# mark split between 2 numbers to be prime tested
# primecheck2
560		0 R 100		1 L 560
# composite1
700		H H H		1 R 560

# composite2
900		- - -		0 R 910
910		1 L 315		1 R 910

c2++
10 11 12(掉头) 13

10 13 在隔板上
10 从左向右 **
13 从右向左

10 在隔板的时候， c1 c2 都是 0

13 6 7 肯定需要一个 lemma

不是 prime
0 -> 17