Created
May 12, 2016 13:46
-
-
Save jms137/cbb66fb58dde067b0bece12873fadc76 to your computer and use it in GitHub Desktop.
Goldbach Turing machine with 47 states
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This gist gives a 47-state, 2-symbol, 1-tape Turing machine that halts iff Goldbach's conjecture is false. | |
goldbach47.c gives a detailed description of the algorithm and runnable C program that directly corresponds | |
to the Turing machine. | |
goldbach47.tm2 gives the formal state machine from goldbach47.c in the format requested by Adam Yedidia | |
see here: https://github.com/adamyedidia/parsimony | |
goldbach73.c gives my initial 73-state variant. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Goldbach's conjecture tested by a 47-state Turing machine | |
Author: Jared Showalter | |
If "a" and "i" were unbounded, this program would halt iff Goldbach's | |
conjecture is false. Furthermore, the program structurally | |
corresponds to a Turing machine with two symbols, one tape, and a | |
small number of states. The array "a" corresponds to the tape (each | |
element is only assigned 0 or 1). The index "i" corresponds to the | |
head position. Each line containing a semicolon and not containing | |
"IGNORE" is an operational state. (There is also one non-operational | |
HALT state.) The operational states can be counted with | |
grep -v IGNORE | grep -c \; | |
and there are 47 operational states. | |
Except for the I/O instrumentation, which does not alter "a", "i", or | |
the control flow within main(), each line that is a state directly | |
implements the transition function entries for one state. The I/O | |
instrumentation generates output that illustrates the correct | |
operation of the program. Uncommenting the assignment to a[2*7] in | |
pp() forces 7 to be treated as composite and demonstrates that the | |
program terminates on n=12 in this case. | |
The high-level algorithm is: | |
Phase 0. Init with n=4 | |
Phase 1. Perform the sieve of Eratosthenes on an array from 1 to n-2, | |
inclusive. | |
Phase 2. Simultaneously move a pair of markers inward, testing the | |
primality of each pair from (2,n-2) to (n/2,n/2). If any of these | |
pairs are both prime, go to phase 3. Otherwise, halt. | |
Phase 3. Add 2 to n and go to phase 1. | |
Greater detail: | |
We define the initial head position to be 3. (This naturally has no | |
intrinsic meaning for a bidirectionally infinite TM starting on an | |
empty tape [1].) Then we define two boolean arrays: | |
Data[j] iff cell 2*j is 1. | |
Mark[j] iff cell 2*j+1 is 0. | |
The algorithm then operates at all times after initialization on an | |
array bounded by Mark[0] and Mark[n-1]. Markers play a number of | |
roles in different states, in addition to bounding the array. Because | |
most of the complication relates to markers, we use the following | |
format for tape diagrams: | |
0*1 2..[j]..k*..(n-1)* | |
This means that: | |
1. 2 < j < k < n-1 | |
2. only 0, k, and n-1 are marked, and | |
3. the head position is 2*j. | |
The head position may be given as "[]" to avoid wasting variables. | |
The Data array is simpler: for 1 < j < n-1, Data[j] is used for the | |
sieve such that "Data[j] iff j is prime" after the sieve. Data[0] is | |
never read (but always false). Data[1] and Data[n-1] are also always | |
false (except while adding 2 to n), and while they aren't read by the | |
algorithm as described here, they are read by the Turing machine due | |
to half-state-combining optimizations. | |
Phase 1: Sieve of Eratosthenes | |
We begin by describing the sieve implementation from the inside out. | |
We assume the reader is familiar with the general idea of the sieve: | |
starting with the whole array marked prime, we loop over the primes, | |
starting with 2, and filter out the multiples of each, so that if we | |
have filtered all the primes through p, the next number marked prime | |
after p must be prime since it is not the multiple of a lesser prime. | |
Filtering a prime p: | |
To clear Data for the multiples of a prime p, we maintain three | |
markers: p, 0<j<p, and p<k<n-1. Each iteration, we advance j | |
cyclically and k linearly until k reaches n-1, clearing a multiple of | |
p each time j wraps around. As a complication to save states | |
elsewhere, we don't finish until j=1, leaving k=n-2 for multiple | |
iterations if needed. | |
Iteration case 1: | |
Pre: 0*..j*..p*..[k]*..(n-1)*, with k=j mod p OR k=n-2 | |
Post: 0*..(j+1)*..p*..[k+1]*..(n-1)* if k < n-2 | |
OR 0*..(j+1)*..p*..[n-2]*(n-1)* otherwise | |
Iteration case 2: | |
Pre: 0*..(p-1)*p*..[k]*..(n-1)*, with k=-1 mod p OR k=n-2 | |
Post: 0*1*..p*..[k+2]*..(n-1)* if k+2 < n-1 | |
OR 0*1*..p*..[n-1]* otherwise | |
Data[k+1] is cleared, which is correct since either k+1=0 mod p or | |
k+1=n-1 (and Data[n-1] is already clear). If k+2>=n-1, we proceed to | |
the next iteration of the prime loop. | |
Finding the next prime: | |
Pre: 0*1*..p*..[n-1]* | |
Post: 0*1*..p..[q]*..[n-1]* where q is the least prime greater than p | |
OR 0*1*..p..[n-1]* if there is no prime q | |
This is straightfoward. If we find a prime q, we jump into the end of | |
filtering iteration case 2 such that we don't clear Data[q] but: | |
If q+1<n-1, we proceed to the next filtering iteration with the | |
valid filtering precondition: | |
0*1*..p..q*[q+1]*..(n-1)* | |
and thus filter multiples of q, while if q+1=n-1 we jump back to | |
find the next prime after q (which then ends the sieve). | |
If we don't find a prime between p and n-1, the sieve is done, and we | |
jump into sum-testing at an appropriate point as described below. | |
Phase 1 entry: There is a state after we have unmarked p and started | |
looking for q, where entry with: | |
0*1*[2]..(n-1)* | |
will immediately find q=2 and begin the sieve. | |
Phase 2: Testing sums | |
This phase simply repeats the following iteration until it exits: | |
Pre: 0*..j*[]..k*..(n-1)*, with j+k=n and j<k-1 | |
After step 1: 0*..j*..[k-1]*..(n-1)* | |
After step 2: 0*..[j]..(k-1)*..(n-1)* | |
Then, if k-1 was prime and j+1 is prime, we prepare to add 2 to n. | |
Otherwise, if j+1=k-1, we halt. | |
Otherwise, we iterate testing sums with the valid pre-condition: | |
Post: 0*..(j+1)*[]..(k-1)*..(n-1)* | |
The inequality j+2 < k-1 for the iteration is satisfied because we | |
know j+2 <= k-1 and k-j=3 must be false since j+k=n and n is even. | |
Phase 2 entry: When phase 1 finishes with: | |
0*1*..[n-1]* | |
it jumps into the middle of step 1 such that we start step 2 with: | |
0*1*..[n-2]*(n-1)* | |
This is correct for j=1 and k=n-1. Since each iteration tests the | |
pair (j+1,k-1), we indeed test the pairs (2,n-2) up to (n/2,n/2). | |
To prepare to add 2 to n, we unmark k-1 and leave the head at k: | |
0*..[k]..(n-1)* with k>=3 (since 0<j<k-1) | |
OR 0*..[k=n-1]* | |
Phase 3: Adding 2 to n | |
For clarity, n is the iteration we're finishing, so n'=n+2 is the next | |
iteration. We straightforwardly update to: | |
After step 1: 0*1..[n](n+1)* | |
with Data[n-1] and Data[n] set so that "Data[j] if j is prime" holds | |
for 1<j<n+1. In fact, we set Data[k] through Data[n] to save states. | |
But note that Data[1] and Data[n'-1=n+1] will not be set. Then we | |
update to: | |
After step 2: 0*1*[2]..(n+1)* | |
We then simply jump into the phase 1 entry point and begin anew. | |
Phase 0: Initialization | |
As bits, the following tape, with only Data[2] true, | |
0* 1 [2]3* | |
is: 00 01 11 00 | |
This is the end of step 1 of adding 2 to n=2: starting step 2 from | |
this state proceeds with n'=4. It can be verified that our start | |
state in the middle of phase 3 step 1 ends step 1 in the above state. | |
Even greater detail: | |
The code below is a fairly direct translation of the above. In | |
addition to brief descriptions of each basic block, each label has a | |
comment "data" or "mark" to indicate whether the head is on a Data or | |
Mark cell on *entry*. There are a few cases where the head could be | |
on either Data or Mark. The strangest are "combined half-states". If | |
a TM has two states q_i and q_j such that the current symbol will | |
always be 0 on entry to q_i and 1 on entry to q_j, these can be | |
combined to a single state. | |
While Data[j] (false/true) is used synonymously with the 0/1 value at | |
cell 2*j, for clarity MarkB[j] is defined as the bit at cell 2*j+1. | |
[FN 1] I believe that a unidirectionally infinite tape, starting on the | |
leftmost cell, with the traditional behavior that a left-move from the | |
leftmost cell remains in place but otherwise follows the transition | |
function, requires only one extra state with slight modifications. | |
*/ | |
#include <stdio.h> | |
#define N 0x10000 | |
char a[N]; // IGNORE | |
int i = 3, n; // IGNORE | |
void pp2(int x) { if (a[x*2]) printf("%d is prime\n", x); } // IGNORE | |
void pp() { /* a[7*2]=0; */ pp2(n-3); pp2(n-2); } // IGNORE | |
void ps() { int x = i/2; printf("%d=%d+%d\n", n, x, n - x); } // IGNORE | |
int main() | |
{ | |
goto at0; // IGNORE | |
// ADD TWO TO N | |
// Setting Data[k..n-1] to true and Mark[n-1] to false, move to Data[n]. | |
add_two: // data | |
a[i] = 1; i++; | |
at0: // mark | |
if (!a[i]) { a[i] = 1; i++; n = i/2+2; goto np4; } else { i++; goto add_two; } | |
// Data[n] and MarkB[n] will always be 0. | |
// They are set to 1 (true and false) via combined half-states np4 and ts1 | |
// and then we return to at1 with head on Data[n]. | |
// Find Mark[0] and increment to Data[1] | |
at1: // data | |
i--; | |
if (!a[i]) i++; else { i--; goto at1; } | |
// Set Mark[1]. Since Data[1]=0 and MarkB[1]=1, it only takes one state. | |
// Then we're on Data[2] and we jump to the sieve entry point. | |
at2: // 1=mark / 0=data | |
if (!a[i]) { i++; goto at2; } else { a[i] = 0; i++; goto np3; } | |
// SIEVE OF ERATOSTHENES | |
// Find next prime: entry point (head at Data[n-1]) | |
// Find and clear current prime's mark | |
next_prime: // data | |
i--; | |
if (!a[i]) { a[i] = 1; i++; } else { i--; goto next_prime; } | |
// Sieve entry point | |
// Look for either a prime or Mark[n-1] | |
np3: // data | |
if (a[i]) { i++; goto np4; } else i++; | |
if (!a[i]) { pp(); i--; goto ts0; } else { i++; goto np3; } | |
// Combined half-states | |
// 1: Set Mark[q] for new prime (which cannot already be marked) | |
// 0: Set Data[n] for adding two to n | |
np4: // 1=mark / 0=data | |
if (a[i]) { a[i] = 0; i++; goto fpw2; } else { a[i] = 1; i++; goto ts1; } | |
// Filter loop (head at Data[k]) | |
// Skip over prime p | |
filter_prime: // data | |
i--; | |
if (!a[i]) i--; else { i--; goto filter_prime; } | |
// Clear Mark[j] and increment to Mark[j+1] | |
fp0: // data | |
i--; | |
if (!a[i]) { a[i] = 1; i++; } else { i--; goto fp0; } | |
i++; | |
// If Mark[j+1], j+1=p and we wrap j to 1. Otherwise, set Mark[j+1]. | |
if (!a[i]) { i--; goto fp_wrap; } else { a[i] = 0; i++; } | |
// Skip over prime p | |
fp1: // data | |
i++; | |
if (!a[i]) i++; else { i++; goto fp1; } | |
// Clear Mark[k] and increment to Mark[k+1] | |
fp2: // data | |
i++; | |
if (!a[i]) { a[i] = 1; i++; } else { i++; goto fp2; } | |
i++; | |
// If Mark[k+1] is not set, set it and iterate filter. | |
// If Mark[k+1] is set, k+1=n-1 and we want to set Mark[k] and iterate. | |
// Since Data[n-1]=MarkB[n-1]=0, this only takes one state. | |
fp3: // 1=mark / 0=data OR mark | |
if (!a[i]) { i--; goto fp3; } else { a[i] = 0; i--; goto filter_prime; } | |
// Filter case where we wrap j to 1. | |
// Find Mark[0] and increment to Data[1] | |
fp_wrap: // data | |
i--; | |
if (!a[i]) i++; else { i--; goto fp_wrap; } | |
// Set Mark[1]. Since Data[1]=0 and MarkB[1]=1, it only takes one state. | |
fpw3: // 1=mark / 0=mark OR data | |
if (!a[i]) { i++; goto fpw3; } else { a[i] = 0; i++; } | |
// Skip over prime p | |
fpw0: // data | |
i++; | |
if (!a[i]) i++; else { i++; goto fpw0; } | |
// Clear Mark[k] and Data[k+1]. If k+1=n-1, find next prime. | |
fpw1: // data | |
i++; | |
if (!a[i]) { a[i] = 1; i++; } else { i++; goto fpw1; } | |
a[i] = 0; i++; | |
if (!a[i]) { i--; goto next_prime; } else i++; | |
// Entry point for filter from next_prime | |
// In entry point case, let m=q+1. Otherwise, let m=k+2. | |
// If m=n-1, find next prime. Otherwise, set Mark[m]. | |
fpw2: // data | |
i++; | |
if (!a[i]) { i--; goto next_prime; } else { a[i] = 0; i--; goto filter_prime; } | |
// TEST SUMS | |
// Loop iteration (head on Data[j+1]) | |
// Clear Mark[k] and decrement to Data[k]. | |
test_sums: // data | |
i++; | |
if (!a[i]) { a[i] = 1; i--; } else { i++; goto test_sums; } | |
// Entry point from sieve completion (k is effectively n-1) | |
// Decrement to Mark[k-1] | |
ts0: // data | |
i--; | |
// Combined half-states | |
// 1: Set Mark[k-1] (which cannot have been set), decrement to Data[k-1]. | |
// 0: Clear Mark[n] for adding two to n, decrement to Data[n]. | |
ts1: // mark | |
if (a[i]) { a[i] = 0; i--; } else { a[i] = 1; i--; goto at1; } | |
// Remember whether k-1 is prime or composite | |
if (a[i]) { i--; goto tsp0; } else { i--; goto tsc0; } | |
// Clear Mark[j] and increment to Data[j+1]. | |
ts_prime: // data | |
i--; | |
tsp0: // mark | |
if (!a[i]) { a[i] = 1; i++; } else { i--; goto ts_prime; } | |
// If j+1 is also prime, prepare to add two to n. | |
// Otherwise, increment to Mark[j+1] and prepare for next iteration. | |
if (a[i]) { ps(); i++; goto tsd0; } else { i++; goto ts_next; } | |
// Clear Mark[j], increment to Mark[j+1], and prepare for next iteration | |
ts_comp: // data | |
i--; | |
tsc0: // mark | |
if (!a[i]) { a[i] = 1; i++; } else { i--; goto ts_comp; } | |
i++; | |
// If Mark[j+1], j+1=k-1 and we HALT (if k-1=j+1 were prime, we'd be in ts_done) | |
// Otherwise, next test loop iteration | |
ts_next: // mark | |
if (!a[i]) { i--; goto HALT; } else { a[i] = 0; i++; goto test_sums; } | |
// Prepare to add two by clearing Mark[k-1] | |
ts_done: // data | |
i++; | |
tsd0: // mark | |
if (!a[i]) { a[i] = 1; i++; goto add_two; } else { i++; goto ts_done; } | |
HALT: return 1; // IGNORE | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
States: 47 | |
AddTwo_GotoEnd_data: | |
a -> AddTwo_GotoEnd_mark; R; b | |
b -> AddTwo_GotoEnd_mark; R; b | |
START AddTwo_GotoEnd_mark: | |
a -> COMBINED__AddTwo_SetDataN__NextPrime_FoundPrime; R; b | |
b -> AddTwo_GotoEnd_data; R; b | |
AddTwo_GotoStart_data: | |
a -> AddTwo_GotoStart_mark; L; a | |
b -> AddTwo_GotoStart_mark; L; b | |
AddTwo_GotoStart_mark: | |
a -> AddTwo_SetMarkOne; R; a | |
b -> AddTwo_GotoStart_data; L; b | |
AddTwo_SetMarkOne: | |
a -> AddTwo_SetMarkOne; R; a | |
b -> NextPrime_FindPrime_data; R; a | |
NextPrime_BackToPrime_data: | |
a -> NextPrime_BackToPrime_mark; L; a | |
b -> NextPrime_BackToPrime_mark; L; b | |
NextPrime_BackToPrime_mark: | |
a -> NextPrime_FindPrime_data; R; b | |
b -> NextPrime_BackToPrime_data; L; b | |
NextPrime_FindPrime_data: | |
a -> NextPrime_FindPrime_mark; R; a | |
b -> COMBINED__AddTwo_SetDataN__NextPrime_FoundPrime; R; b | |
NextPrime_FindPrime_mark: | |
a -> TestSums_SkipDataK_data; L; a | |
b -> NextPrime_FindPrime_data; R; b | |
COMBINED__AddTwo_SetDataN__NextPrime_FoundPrime: | |
a -> COMBINED__AddTwo_ClearMarkN__TestSums_SetMarkKm1; R; b | |
b -> FilterPrimeWrap_SkipDataKp2_data; R; a | |
FilterPrime_BackToPrime_data: | |
a -> FilterPrime_BackToPrime_mark; L; a | |
b -> FilterPrime_BackToPrime_mark; L; b | |
FilterPrime_BackToPrime_mark: | |
a -> FilterPrime_ClearMarkJ_data; L; a | |
b -> FilterPrime_BackToPrime_data; L; b | |
FilterPrime_ClearMarkJ_data: | |
a -> FilterPrime_ClearMarkJ_mark; L; a | |
b -> FilterPrime_ClearMarkJ_mark; L; b | |
FilterPrime_ClearMarkJ_mark: | |
a -> FilterPrime_SkipDataJp1_data; R; b | |
b -> FilterPrime_ClearMarkJ_data; L; b | |
FilterPrime_SkipDataJp1_data: | |
a -> FilterPrime_SetMarkJp1_mark; R; a | |
b -> FilterPrime_SetMarkJp1_mark; R; b | |
FilterPrime_SetMarkJp1_mark: | |
a -> FilterPrimeWrap_GotoStart_data; L; a | |
b -> FilterPrime_ForwardToPrime_data; R; a | |
FilterPrime_ForwardToPrime_data: | |
a -> FilterPrime_ForwardToPrime_mark; R; a | |
b -> FilterPrime_ForwardToPrime_mark; R; b | |
FilterPrime_ForwardToPrime_mark: | |
a -> FilterPrime_ClearMarkK_data; R; a | |
b -> FilterPrime_ForwardToPrime_data; R; b | |
FilterPrime_ClearMarkK_data: | |
a -> FilterPrime_ClearMarkK_mark; R; a | |
b -> FilterPrime_ClearMarkK_mark; R; b | |
FilterPrime_ClearMarkK_mark: | |
a -> FilterPrime_SkipDataKp1_data; R; b | |
b -> FilterPrime_ClearMarkK_data; R; b | |
FilterPrime_SkipDataKp1_data: | |
a -> FilterPrime_SetNewMarkK; R; a | |
b -> FilterPrime_SetNewMarkK; R; b | |
FilterPrime_SetNewMarkK: | |
a -> FilterPrime_SetNewMarkK; L; a | |
b -> FilterPrime_BackToPrime_data; L; a | |
FilterPrimeWrap_GotoStart_data: | |
a -> FilterPrimeWrap_GotoStart_mark; L; a | |
b -> FilterPrimeWrap_GotoStart_mark; L; b | |
FilterPrimeWrap_GotoStart_mark: | |
a -> FilterPrimeWrap_SetMarkOne; R; a | |
b -> FilterPrimeWrap_GotoStart_data; L; b | |
FilterPrimeWrap_SetMarkOne: | |
a -> FilterPrimeWrap_SetMarkOne; R; a | |
b -> FilterPrimeWrap_ForwardToPrime_data; R; a | |
FilterPrimeWrap_ForwardToPrime_data: | |
a -> FilterPrimeWrap_ForwardToPrime_mark; R; a | |
b -> FilterPrimeWrap_ForwardToPrime_mark; R; b | |
FilterPrimeWrap_ForwardToPrime_mark: | |
a -> FilterPrimeWrap_ClearMarkK_data; R; a | |
b -> FilterPrimeWrap_ForwardToPrime_data; R; b | |
FilterPrimeWrap_ClearMarkK_data: | |
a -> FilterPrimeWrap_ClearMarkK_mark; R; a | |
b -> FilterPrimeWrap_ClearMarkK_mark; R; b | |
FilterPrimeWrap_ClearMarkK_mark: | |
a -> FilterPrimeWrap_ClearDataKp1_data; R; b | |
b -> FilterPrimeWrap_ClearMarkK_data; R; b | |
FilterPrimeWrap_ClearDataKp1_data: | |
a -> FilterPrimeWrap_TestMarkKp1_mark; R; a | |
b -> FilterPrimeWrap_TestMarkKp1_mark; R; a | |
FilterPrimeWrap_TestMarkKp1_mark: | |
a -> NextPrime_BackToPrime_data; L; a | |
b -> FilterPrimeWrap_SkipDataKp2_data; R; b | |
FilterPrimeWrap_SkipDataKp2_data: | |
a -> FilterPrimeWrap_SetNewMarkK; R; a | |
b -> FilterPrimeWrap_SetNewMarkK; R; b | |
FilterPrimeWrap_SetNewMarkK: | |
a -> NextPrime_BackToPrime_data; L; a | |
b -> FilterPrime_BackToPrime_data; L; a | |
TestSums_ClearK_data: | |
a -> TestSums_ClearK_mark; R; a | |
b -> TestSums_ClearK_mark; R; b | |
TestSums_ClearK_mark: | |
a -> TestSums_SkipDataK_data; L; b | |
b -> TestSums_ClearK_data; R; b | |
TestSums_SkipDataK_data: | |
a -> COMBINED__AddTwo_ClearMarkN__TestSums_SetMarkKm1; L; a | |
b -> COMBINED__AddTwo_ClearMarkN__TestSums_SetMarkKm1; L; b | |
COMBINED__AddTwo_ClearMarkN__TestSums_SetMarkKm1: | |
a -> AddTwo_GotoStart_data; L; b | |
b -> TestSums_CheckDataKm1_data; L; a | |
TestSums_CheckDataKm1_data: | |
a -> TestSumsComp_ClearJ_mark; L; a | |
b -> TestSumsPrime_ClearJ_mark; L; b | |
TestSumsPrime_ClearJ_data: | |
a -> TestSumsPrime_ClearJ_mark; L; a | |
b -> TestSumsPrime_ClearJ_mark; L; b | |
TestSumsPrime_ClearJ_mark: | |
a -> TestSumsPrime_CheckDataJp1_data; R; b | |
b -> TestSumsPrime_ClearJ_data; L; b | |
TestSumsPrime_CheckDataJp1_data: | |
a -> TestSums_SetMarkJp1_mark; R; a | |
b -> TestSums_DoneClearK_mark; R; b | |
TestSumsComp_ClearJ_data: | |
a -> TestSumsComp_ClearJ_mark; L; a | |
b -> TestSumsComp_ClearJ_mark; L; b | |
TestSumsComp_ClearJ_mark: | |
a -> TestSumsComp_SkipDataJp1_data; R; b | |
b -> TestSumsComp_ClearJ_data; L; b | |
TestSumsComp_SkipDataJp1_data: | |
a -> TestSums_SetMarkJp1_mark; R; a | |
b -> TestSums_SetMarkJp1_mark; R; b | |
TestSums_SetMarkJp1_mark: | |
a -> HALT; L; a | |
b -> TestSums_ClearK_data; R; a | |
TestSums_DoneClearK_data: | |
a -> TestSums_DoneClearK_mark; R; a | |
b -> TestSums_DoneClearK_mark; R; b | |
TestSums_DoneClearK_mark: | |
a -> AddTwo_GotoEnd_data; R; b | |
b -> TestSums_DoneClearK_data; R; b |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Author: Jared Showalter | |
#include <stdio.h> | |
#define N 0x10000 | |
char a[N]; // IGNORE | |
int i, n; // IGNORE | |
void pp(int x) { if (a[x*2+2]) printf("%d is prime\n", x); } // IGNORE | |
void ps() { int x = i/2-1; printf("%d=%d+%d\n", n, x, n - x); } // IGNORE | |
int main() | |
{ | |
a[i] = 0; i++; // IGNORE | |
a[i] = 1; i++; | |
a[i] = 0; i++; | |
a[i] = 1; i++; | |
a[i] = 0; i++; | |
a[i] = 0; i++; | |
a[i] = 1; i++; | |
a[i] = 0; i++; goto at0; | |
add_two: | |
i++; | |
if (a[i]) { a[i] = 0; i--; } else { i++; goto add_two; } | |
at0: | |
n = i / 2; pp(n-3); pp(n-2); // IGNORE | |
a[i] = 1; i++; | |
a[i] = 0; i++; | |
a[i] = 1; i++; | |
a[i] = 0; i++; | |
a[i] = 0; i++; | |
a[i] = 1; i--; | |
at1: | |
i--; | |
if (a[i]) { i++; goto np3; } else { i--; goto at1; } | |
next_prime: | |
i--; | |
if (a[i]) i--; else { i--; goto next_prime; } | |
np0: | |
i--; | |
if (a[i]) { a[i] = 0; i--; } else { i--; goto np0; } | |
np1: | |
i--; | |
if (a[i]) i++; else { i--; goto np1; } | |
i++; | |
a[i] = 1; i++; | |
np2: | |
i++; | |
if (a[i]) { a[i] = 0; i++; } else { i++; goto np2; } | |
np3: | |
if (a[i]) { i++; goto np4; } else i++; | |
if (a[i]) { i--; goto ts0; } else { i++; goto np3; } | |
np4: | |
if (a[i]) { i--; goto ts0; } else { a[i] = 1; i++; goto fp3; } | |
filter_prime: | |
i--; | |
if (a[i]) i--; else { i--; goto filter_prime; } | |
i--; | |
if (a[i]) { a[i] = 0; i--; goto fp_wrap; } else i--; | |
fp0: | |
i--; | |
if (a[i]) { a[i] = 0; i++; } else { i--; goto fp0; } | |
i++; | |
a[i] = 1; i++; | |
fp1: | |
i++; | |
if (a[i]) i++; else { i++; goto fp1; } | |
fp2: | |
i++; | |
fp2a: | |
if (a[i]) { a[i] = 0; i++; } else { i++; goto fp2; } | |
fp3: | |
i++; | |
if (a[i]) { i--; goto next_prime; } else { a[i] = 1; i--; goto filter_prime; } | |
fp_wrap: | |
i--; | |
if (a[i]) i++; else { i--; goto fp_wrap; } | |
i++; | |
a[i] = 1; i++; | |
fpw0: | |
i++; | |
if (a[i]) i++; else { i++; goto fpw0; } | |
fpw1: | |
i++; | |
if (a[i]) i--; else { i++; goto fpw1; } | |
a[i] = 0; i++; goto fp2a; | |
test_sums: | |
i++; | |
if (a[i]) { a[i] = 0; i--; } else { i++; goto test_sums; } | |
ts0: | |
i--; | |
if (a[i]) { i--; goto ts1; } else { a[i] = 1; i--; } | |
if (a[i]) { i--; goto tsp0; } else { i--; goto tsc0; } | |
ts1: | |
if (a[i]) { ps(); i++; goto tsd0; } else { i++; goto ACCEPT; } | |
ts_prime: | |
i--; | |
tsp0: | |
if (a[i]) { a[i] = 0; i--; } else { i--; goto ts_prime; } | |
if (a[i]) { ps(); i++; goto tsd0; } else i++; | |
i++; goto ts_next; | |
ts_comp: | |
i--; | |
tsc0: | |
if (a[i]) { a[i] = 0; i++; goto ts_next; } else { i--; goto ts_comp; } | |
ts_next: | |
i++; | |
a[i] = 1; i++; goto test_sums; | |
ts_done: | |
i++; | |
tsd0: | |
if (a[i]) { a[i] = 0; i--; } else { i++; goto ts_done; } | |
tsd1: | |
i--; | |
if (a[i]) i++; else { i--; goto tsd1; } | |
i++; | |
a[i] = 1; i++; goto add_two; | |
ACCEPT: return 1; // IGNORE | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment