Turing-machine (busy beaver)

// Turing machine programming :

/*

    i-th row of 'rules' is i-th state. In each row:

    0th element - what to write to tape if current cell is 0

    1st element - where to move if current cell is 0 (0 - left, 1 - right)

    2nd element - which state to go to if current cell is 0 (-1 is the halt state)

    3rd element - what to write to tape if current cell is 1

    4th element - where to move if current cell is 1 (0 - left, 1 - right)

    5th element - which state to go to if current cell is 1 (-1 is the halt state)

*/

​

​

​

// let rules = [[0,   1, 1, -1,   0, 0, 0]]   // busy beaver (2-symbol, 1-state)

​

// let rules = [[0,   1, 1, 1,     1, 0, 1],    // busy beaver (2-symbol, 2-state)

//             [1,   1, 0, 0,     1, 1, -1]]

​

// let rules = [[1, 1, 1,     1, 1, -1],    // busy beaver (2-symbol, 3-state)

//             [0, 1, 2,     1, 1, 1],

//             [1, 0, 2,    1, 0, 0]];

​

let rules = [[1, 1, 1,     1, 0, 1],    // busy beaver (2-symbol, 4-state)

             [1, 0, 0,     0, 0, 2],

             [1, 1, -1,    1, 0, 3],

             [1, 1, 3,     0, 1, 0]];

​

// let rules = [[0,   1, 1, 1,     1, 0, 2],    // busy beaver (2-symbol, 5-state)

//             [1,   1, 1, 2,     1, 1, 1],

//             [2,   1, 1, 3,    0, 0, 4],

//             [3,   1, 0, 0,     1, 0, 3],

//             [4,   1, 1, -1,     0, 0, 0]];

​

​

​

let num_cells = 255;

​

let side;

let tape, new_tape;

let head, ix_head, new_ix_head;

​

function setup() {

  createCanvas(windowWidth, windowHeight);

  background(100);

  // print(height/30);

  side = height/16;

  button_up = createButton('SPEED +');

  button_up.position(19, 19);

  button_up.mousePressed(tape_speed_up);

  button_down = createButton('SPEED -');

  button_down.position(19, 45);

  button_down.mousePressed(tape_speed_down);

  tape = Array(num_cells).fill(0);

  new_tape = tape.slice()

  head = tape[ix_head];

  ix_head = floor(num_cells/2);

}

​

​

​

let ix_rule = 0;

let delta = 0;

let steps = 0;

let offset = 0.0;

let tape_speed = 1;

​

function draw() {

  rectMode(CENTER);

  translate(width/2, height/2);

  scale(1, -1);

  background(100);

  if (ix_rule != -1) {      // if not halted

  let head = tape[ix_head];

​

  if (head == 0)

  {

    new_tape[ix_head] = rules[ix_rule][0];  // write a new symbol and move accordingly

    let move;                             

    if (rules[ix_rule][1] == 0) {         

      move = tape_speed;

      new_ix_head = ix_head - 1;}

    else {

      move = -tape_speed;

      new_ix_head = ix_head + 1;}

​

    if (delta < side){    // make transitions smooth

      delta = delta + move;

      offset = offset + move;}

​

  }

  else if (head == 1)

  {

    new_tape[ix_head] = rules[ix_rule][3];

    let move;

    if (rules[ix_rule][4] == 0) {

      move = tape_speed;

      new_ix_head = ix_head - 1;}

​

    else {

      move = -tape_speed;

      new_ix_head = ix_head + 1;}

​

    if (delta > -side){

      delta = delta + move;

      offset = offset + move;}

  }

  if ((delta >= side) || (delta <= -side))  // once the head moved by a cell-sized amount

  {

    // transition into a new state

    if (head == 0)

      ix_rule = rules[ix_rule][2];

​

    if (head == 1)

      ix_rule = rules[ix_rule][5];

​

    delta = 0;

    if (ix_rule != -1)

      tape = new_tape.slice();

    ix_head = new_ix_head;

    steps += 1;   

  }

  }

​

  if (ix_rule == -1) {

    let discrepancy = offset%side;

    offset -= discrepancy;

  }

  // draw tape

  for (let i=-floor(num_cells/2); i<=floor(num_cells/2); i++)

    rect(i*side + offset, 0, side, side);

  // head

  circle(0, -side, 10);

  scale(1, -1);

  // draw symbols

  textSize(height/21);

  fill(0);

  let num_ones = 0;

  for (let i=-floor(num_cells/2); i<=floor(num_cells/2); i++)

  {

    let j = i+floor(num_cells/2);

    let symbol = new_tape[j];

    if (symbol == 1)

      num_ones += 1;

​

    text(symbol, i*side + offset - side/5, side/5);

  }

  fill(255);

  textSize(1.5*height/21);

  text("Steps: " + steps, -width/2.732, -height/3.225);

  text("Number of 1's: " + num_ones, -width/2.732, -height/4.607);

  translate(-width/2, -height/2);

}

​

​

function tape_speed_up() {

  if (tape_speed < 8)

    tape_speed += 1;

}

​

function tape_speed_down() {

  if (tape_speed > 1)

    tape_speed -= 1;

}