To calculate the terms of the chaotic TM sequence, it’s best to do it one bit at a time, meaning to do the
least significant bit first (or bit 1), then bit 2, then bit 3 and so on for a number of bit positions
approximately equal to log_2(n_max), where n_max is the largest value of n for which we wish to compute s_n
(chaotic TM sequence). gen 1 has period 1, and for k>=2 the period of gen k is a divisor of 2^k, most
likely equal to 2^k.

It’s perhaps easiest to consider gen 1 through gen 5 as given , and to compute successive generations according
to rules explained below for finding gen 6 knowing gen 5.

gen 1 = [1] , meaning 1 1 1 1 1 1 1…
gen 2 = [1 0 0 1] , meaning 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 …
gen 3 = [0 0 1 0 1 0 0 0]
gen 4 = [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1]
gen 5, given below, has a period of 32 beginning with the first term.

How to compute gen 6:

Set a = 6, and toggle = 0.

gen5 =
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 1, 0, 0, 0, 1, 0,
0, 0, 1, 0, 1, 0, 0, 1

gen6, which we view as one-dimensional, will be displayed in 4 rows of 16. We initially fill it with all zeros:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Set gen6[31] to 1.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

For 0<=j<16, set gen6[33+j] = gen5[17+j] or IOW,
set the 3rd row of gen6 to be the last two rows of gen5:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

For 0<=j<16, set gen6[49+j] = gen5[17+j] or IOW,
set the fourth row of gen6 to be the last two rows of gen5:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1

Set gen6[64]=0 and gen6[31]=1 :

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0

For 1<= j <=16 , if gen6[32+j] is 1,
and if the count of 1s so far has parity toggle, then
replace gen6[32+j] by 0. IOW, count the 1s in the 3rd row of gen6,
and every time the count is even, replace the corresponding 1 by a 0.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0

Let a = floor(a*(3/2)), so a = floor(6*(3/2))= 9.
Set toggle to be the parity of a, so toggle = 1.

Next, set gen6[64] = 1-toggle = 0.
Set gen6[48] = 0 and gen6[47] = 1:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 // gen 6 in final form
0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0

Analogous rules apply to generations 7 and above. The lowest index for which gen 6 has a 1 entry is 31,
and in general if k>=6, the lowest index for which gen k has a 1 seems to be 2^(k-1)-1.

The rules have been implemented in a C program of roughly 90 lines of code. This predictor was put to the
test by comparing its output with the number sequence appearing on the tape of the chaotic Turing machine, examined
when the reading head is at an extreme right position. The two agreed to over 4 million terms. It’s conceivable that
the predictor captures the whole behavior of the Turing machine, although trying to prove it seems to be a
difficult problem to the author.

C language source code to calculate/predict the first 2000 terms of the sequence can be found below.

#include <stdio.h>
#define P2k (1<<k)
#define MAX_SIZE 2048
#define NUMBITS 11

int gen1[32] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int gen2[32] = {1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1};
int gen3[32] = {0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0};
int gen4[32] = {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1};       
int gen5[32] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1};

int g[25][MAX_SIZE];

int main(void)
{
    int k = 5;
    int j;
    int t;
    int count;
    int toggle=0;
    int a=6;

    // Copy gen1-gen5 into g
    for(j=0; j<32; j++)
    {
        g[0][j] = gen1[j];
        g[1][j] = gen2[j];
        g[2][j] = gen3[j];
        g[3][j] = gen4[j];
        g[4][j] = gen5[j];
    }

   while(k<NUMBITS) 
  {
     for(j=0; j< P2k; j++)
     {
       g[k][j] = 0;
     }
     g[k][P2k-2] = 1;

     for(j=0;j<P2k/2;j++)
     {
        g[k][P2k + j] = g[k-1][P2k/2 + j];
        g[k][P2k+(P2k)/2+j] = g[k-1][(P2k/2)+j];
     }
     
     g[k][2*P2k - 1]=0;

     /*******
      next, we need to perform decimation on the third quarter of g_[k+1][j]    *********/

     count=0;                  
     a = (3*a)/2;
        
     for(j=0;j<P2k/2;j++)
     {
       if(g[k][P2k+j])
       {
         count++;
         if((count%2)==toggle)
         {
           g[k][P2k+j]=0;           
         }
        }
      }
            
      toggle = a%2;      
      g[k][2*P2k-1] = 1-toggle;      
      g[k][P2k+(P2k)/2-1] = 0;
      g[k][P2k+(P2k/2)-2] = 1; 
 k++;
 }  

for(j=0; j< MAX_SIZE-2; j++)
{
  t=0;
  for(k=0;k<NUMBITS;k++)
  {
     if(g[k][j%(2*P2k)])
     {
       t= t+ P2k;
     }
   }

   /***************
   compute t= ms[j] by combining g[k][j%P2k]
   for k = 0 ... 22
  *******/  
      
   printf("%d ", t); 
  }
printf("\n");
return 0;
}