Busy Beaver Revival

Projects General Guidance
1

Perhaps some old boy remembers the Busy Beaver contest a long time ago. The goal was to configure a beaver (Turing machine) to cut as many trees as possible and then stop, in 5 states. The count includes all 1s on the Turing machine tape when the machine halts.

Why did that idea come up just now, in the Arduino forum?
It could be a nice example for real multitasking and inter-task communication on an ESP32. The tasks or jobs include:

  1. Turing machine enumerator
  2. machine checker
  3. emulator
  4. high score notifier
  5. machine dispatcher

  1. The enumerator configures a first/next Turing machine. It should be possible to compute a unique ID for each machine and configure a machine according to a given ID.

  2. A check for obvious bugs includes e.g. missing Halt state, unreachable states...
    This can be done in the enumerator already, but for multi-tasking demonstration purposes can be separated into its own task (or coroutine?)

  3. The emulator (find a better name?) runs a configured machine until Halt or some other event. A timeout can indicate either an extraordinary busy beaver or a runaway without a chance to Halt.
    Some restrictions can be added so that a local champ can be found in reasonable time. Restrictions like no negative tape positions, no more than 64K moves or tape positions...

A basic Turing machine class can be defined and extended by subclasses for the tape implementation. The fastest implementation can use a bit array in memory, slower but nicer were pixels on various displays. Then we had a "natural" tape limit in the smallest display pixel count.

  1. Every new high score (candidate) can be sent to the Serial Monitor, local display or to a Web page.

  2. A Web server can dispatch packages of machines (ID ranges) to participating users for parallel search for the busiest beaver.

A beaver ID could consist of 10 records/structs for the 2x5 state transitions:
1 bit write 0/1, better: keep/toggle bit on tape
1 bit move tape left/right
3 bit next state (regular 1-5, Halt state 0)
These bits can be represented by a single letter, with 10 transitions in 10 letters for a unique machine ID.

I'm waiting for comments/contributions...

2

Looks like fun! I took a Turing Machine simulator I wrote in C a long time ago, and updated the state table to produce the Busy Beaver 2x2 machine. Fortunately, it gets the correct answer, 4.

I suppose for your contest idea, one could generate random state tables, feed them to the base simulator code, and see what happens.

#include <stdio.h>
#include <string.h>
#include <stdint.h>

// Turing machine simulator, translation of TM1.BAS Isaac Malitz, Byte Nov 1989 p 345.
// modified for Busy Beaver

// data tape
char tape[] = "000000000000000000000000000000";  //30
char state = 'A'; //starting machine state
char mark = 0; //symbol read

// state table format "state, symbol read, '-', new symbol, action, new state", 7 byte string

char state_table[][7]={ "A0-1RB", "A1-1LB", "B0-1LA", "B1-1RH"
                      }; //state table for busy beaver 2x2
int p = 10; //starting position on tape
char r[7];  //current state table entry

int main() {

    int state_table_size = sizeof(state_table)/7; //max index
    printf("state table size %d\n",state_table_size);
    int i;

    while(1) {

//  print tape and pointer
    printf("%s\n",tape);
    i=p;
    while(i)
        {
        i--;
        printf(" ");
        }
    printf("^\n");

//  check state for stop
    if (state == 'H') break;

//  read tape
    mark = tape[p];

    printf("s %c t %c\n",state,mark);

// state table lookup. Look for combination of state and symbol read
    for(i=0; i<state_table_size; i++)
    {
        memcpy(r,&state_table[i],7); // copy table entry

        if ( state==r[0] && mark==r[1]) break; //found an entry
        if (i == state_table_size-1) printf("state table error\n");
    }

// current instruction entry
    printf("r %s\n",r);

// rewrite symbol on tape according to instruction
    tape[p]=r[3];

// move tape head as instructed
    if (r[4] == 'L') p--;
    if (r[4] == 'R') p++;

// determine new machine state
    state = r[5];
    }
 return 0;
}

Output:

Capture

Added: State Table for Busy Beaver 4x2. Also works as advertised (13x '1').

// state table format "state, symbol read, '-', new symbol, action, new state", 7 byte string

char state_table[][7]={ "A0-1RB", "A1-1LB", "B0-1LA", "B1-0LC", "C0-1RH", "C1-1LD","D0-1RD","D1-0RA"
                      }; //state table for busy beaver 4x2
3

I wrote one in Delphi a long time ago. High score was about 3600.
So I know how to do everything but would like to see what others think about it, and how to achieve powerful task distribution, communication and synchronization on the ESP32.