Goldbach Turing machine with 47 states

readme.txt

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.

goldbach47.c

/*

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
}

goldbach47.tm2

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

goldbach73.c

// 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
}