list27-named.txt

# Formatted for http://morphett.info/turing/turing.html
test-or-start-next-loop _ 1 R start-next-loop
test-or-start-next-loop 1 1 R test-1
test-1 _ _ L not-prime-return
test-1 1 1 R test-2
test-2 _ _ L is-prime
test-2 1 1 R init-counter2-or-prime
init-counter2-or-prime _ _ L is-prime
init-counter2-or-prime 1 _ L init-counter1
init-counter1 _ 1 R place-counter1
init-counter1 1 1 L invert-to-start-for-counter1
invert-to-start-for-counter1 _ _ R init-counter1
invert-to-start-for-counter1 1 _ L invert-to-start-for-counter1
advance-counter1 _ _ L reset-counter1
advance-counter1 1 _ L increment-counter-1
increment-counter-1 _ 1 R place-counter1
increment-counter-1 1 _ L increment-counter-1
reset-counter1 _ _ R place-counter1
reset-counter1 1 _ L reset-counter1
place-counter1 _ _ R invert-to-divider
place-counter1 1 _ R move-cut-left
invert-to-divider _ 1 R invert-to-divider
invert-to-divider 1 _ R find-and-shift-counter2
find-and-shift-counter2 _ 1 R place-counter2
find-and-shift-counter2 1 1 R find-and-shift-counter2
place-counter2 _ _ L check-divisibility
place-counter2 1 _ L back-from-counter2
back-from-counter2 _ 1 L advance-counter1
back-from-counter2 1 1 L back-from-counter2
check-divisibility _ _ L does-counter1-divide
check-divisibility 1 1 L check-divisibility
does-counter1-divide _ 1 R not-prime-replace-divider
does-counter1-divide 1 1 L reset-counter-1
not-prime-replace-divider _ 1 L not-prime-return
not-prime-return _ 1 L cut
not-prime-return 1 1 L not-prime-return
cut _ _ R place-counter1
cut 1 _ L check-cut
reset-counter-1 _ 1 R increment-divider
reset-counter-1 1 1 L reset-counter-1
increment-divider _ 1 R test-2
increment-divider 1 1 R increment-divider
is-prime _ _ L test-after-prime
is-prime 1 1 L is-prime
test-after-prime _ _ R test-or-start-next-loop
test-after-prime 1 1 L goto-test-left
start-next-loop _ 1 L goto-test-left
start-next-loop 1 1 R start-next-loop
goto-test-left _ _ R test-or-start-next-loop
goto-test-left 1 1 L goto-test-left
check-cut _ _ * halt-done
check-cut 1 1 R goto-test-left
move-cut-left _ 1 L cut
move-cut-left 1 1 R move-cut-left

list27.txt

000(023Rb|001Rb)
001(017La|002Rb)
002(021La|003Rb)
003(021La|004La)
004(009Rb|005Lb)
005(004Ra|005La)
006(008La|007La)
007(009Rb|007La)
008(009Ra|008La)
009(010Ra|026Ra)
010(010Rb|011Ra)
011(012Rb|011Rb)
012(014La|013La)
013(006Lb|013Lb)
014(015La|014Lb)
015(016Rb|019Lb)
016(017Lb|ERR--)
017(018Lb|017Lb)
018(009Ra|025La)
019(020Rb|019Lb)
020(002Rb|020Rb)
021(022La|021Lb)
022(000Ra|024Lb)
023(024Lb|023Rb)
024(000Ra|024Lb)
025(HALT-|024Rb)
026(018Lb|026Rb)

list31.txt

000(006Lb|001Rb)
001(018La|002Rb)
002(022La|003Rb)
003(022La|004La)
004(018Lb|005La)
005(006Ra|005Lb)
006(011Lb|007Ra)
007(008La|007Rb)
008(010Lb|009Lb)
009(011Rb|009Lb)
010(011Ra|010Lb)
011(024Rb|012Ra)
012(013Ra|012Rb)
013(014Rb|013Rb)
014(016La|015La)
015(008La|015Lb)
016(017La|016Lb)
017(004Rb|020Lb)
018(019La|018Lb)
019(028Ra|026Rb)
020(021Rb|020Lb)
021(002Rb|021Rb)
022(023La|022Lb)
023(011Ra|027Lb)
024(025Rb|024Rb)
025(026Lb|025Rb)
026(028Lb|000Ra)
027(000Ra|027Lb)
028(030Ra|029Lb)
029(HALT-|026Rb)
030(028Lb|030Rb)

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

source31.txt

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		- - -		0 L 130		# a(d+1) = 0
130		0 R 140		1 L 130
140		- - -		0 R 150		# set a(1)
150		0 L 200		1 R 150
# advance c1, starting on a(d)
200		1 L 210		1 L 205		# test a(d)
205		1 R 220		1 L 205
# wrapping around
210		0 R 220		1 L 210

220		- - -		0 R 230		# write c1
230		0 R 250		1 R 230
# 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		0 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		0 L 315		1 L 314
315		0 R 900		1 R 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 600

000		1 L 510		- - -
510		1 L 524		- - -

524		1 R 525		- - -		# add a 1 on the left of the number
525		1 R 526		1 R 525		# erase divider between the 2 prime candidates
526		1 L 560		1 R 526		# add a 1 on the right
# mark split between 2 numbers to be prime tested. initially n-1, 1
560		- - -		0 R 100

# primecheck2
600		0 R 100		1 L 600
# composite1
700		1 L 710		- - -		# a(i) = 1
710		- - -		1 L 730
730		H H H		1 R 560

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