Skip to content

Instantly share code, notes, and snippets.

@boriel
Forked from anonymous/list27.txt
Last active January 8, 2021 21:43
Show Gist options
  • Save boriel/3f0f74c1ba2fb4a6b2162fd8ee3c6d48 to your computer and use it in GitHub Desktop.
Save boriel/3f0f74c1ba2fb4a6b2162fd8ee3c6d48 to your computer and use it in GitHub Desktop.
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)
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)
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.
# 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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment