Turing and Post Machine Love

broken-tm-emulator.js

// a post machine emulator

function validatedAlphabet({ description: { A } }) {
  if (A == null) throw new Error('description missing alphabet');
  
  return A;
}

function validatedDeletionNumber({ description: { m } }) {
  if (m == null) throw new Error('description is missing its m');
  if (typeof m !== 'number' || isNaN(m)) throw new Error(`${m} is not a number`);
  if (m <= 0) throw new Error(`${m} must belong to ℕ+`);
  if (m !== Math.floor(m)) throw new Error(`${m} must belong to ℕ+`);
  
  return m;
}

function validatedHeadSymbol({ description, word }) {
  const A = validatedAlphabet({ description });
  
  if (word == null) throw new Error(`word missing`);
  
  const [head,] = word;
  if (head == null) throw new Error(`word empty`);
  
  if (!A.includes(head)) throw new Error(`alphabet ${A.join(', ')} does not contain ${head}`);
  
  return head;
}

function validatedHaltingSymbol({ description }) {
  
  const { H } = description;
  if (H == null) return null;
  
  const A = validatedAlphabet({ description });
  if (!A.includes(H)) throw new Error(`alphabet ${A.join(', ')} does not contain halting symbol ${H}`);
  
  return H;
}

function validatedProductionRules({ description: { P, H } }) {
  if (P == null) throw new Error('description missing production rules');
  if (H != null && Object.hasOwn(P, H)) throw new Error('the halting symbol ${H} should not have a production rule');
  
  return P;
}

function isHaltingWord({ description, word }) {
  
  const m = validatedDeletionNumber({ description });
  
  // too short
  if (word.length < m) return true;
  
  const head = validatedHeadSymbol({ description, word });
  
  const H = validatedHaltingSymbol({ description });
  
  // leads with the halting symbol
  if (H != null && head === H) return true;
  
  const P = validatedProductionRules({ description });
  
  // has no production rules
  return !Object.hasOwn(P, head);
}

function validatedProduction({ description, word }) {
  const A = validatedAlphabet({ description });
  const P = validatedProductionRules({ description });
  const head = validatedHeadSymbol({ description, word });
  
  if (!A.includes(head)) throw new Error(`alphabet ${A.join(', ')} does not contain ${head}`);
  
  return P[head];
}

function transformation({ description, word }) {
  // no change if halted
  if (isHaltingWord({ description, word })) return { description, word };
  
  // our definition of a halting word includes a word
  // that has a head without a production rule
  const p = validatedProduction({ description, word });
  
  const m = validatedDeletionNumber({ description });
  
  return { description, word: word.concat(p).slice(m) };
}

function * compute({ description, word }) {
  yield word;
  
  while (!isHaltingWord({ description, word })) {
    ({ word } = transformation({ description, word }));
    yield word;
  }
}

// hard coded to zero and 1

const tmSymbol = (prefix, state, suffix = null) =>
	suffix == null
		? `${prefix}-${state}`
		: `${prefix}-${state}-${suffix}`;

const tmAlphabet =
  (states) => states.flatMap(
    state => [
      `L-${state}`,
      `L-${state}-0`,
      `L-${state}-1`,
      `R-${state}`,
      `R-${state}-0`,
      `R-${state}-1`,
      `R-${state}-*`,
      `H-${state}`,
      `H-${state}-0`,
      `H-${state}-1`
    ]
  );

// let [write, move, nextState] = instruction;
const encodeTmRule = ({ currentState : k, read: z, write, move, nextState: kPrime }) => {
  const postRules = {};
  
  const a = (move === 0 && write === 1);
  const b = (z === 0)
  const c = (move === 1 && write === 1);
  const d = (move === 1);
  const e = (move === 0);
  
  const Hkz = tmSymbol('H', k, z);
  postRules[Hkz] = [];
  if (a) {
    postRules[Hkz].push(
      tmSymbol('R', kPrime, '*'),
      tmSymbol('R', kPrime, '*')
    );
  }
  if (b) {
    postRules[Hkz].push(
      tmSymbol('H', kPrime)
    );
  }
  postRules[Hkz].push(
    tmSymbol('H', kPrime)
  );
  if (c) {
    postRules[Hkz].push(
      tmSymbol('L', kPrime),
      tmSymbol('L', kPrime)
    );
  }
  
  const Lkz = tmSymbol('L', k, z);
  postRules[Lkz] = [ tmSymbol('L', kPrime) ];
  if (d) {
    postRules[Lkz].push(
      tmSymbol('L', kPrime),
      tmSymbol('L', kPrime),
      tmSymbol('L', kPrime)
    );
  }
  
  const Rkz = tmSymbol('R', k, z);
  postRules[Rkz] = [ tmSymbol('R', kPrime) ];
  if (e) {
    postRules[Rkz].push(
      tmSymbol('R', kPrime),
      tmSymbol('R', kPrime),
      tmSymbol('R', kPrime)
    );
  }
  
  return postRules;
};

const encodeTmState = (state, stateDescription) =>
	(Object.keys(stateDescription).length === 0)
	? {}
	: Object.entries(stateDescription).reduce(
      (acc, [read, [write, move, nextState]]) =>
      	({
      		...acc,
      		...encodeTmRule({
      			currentState: state,
      			read,
      			write,
      			move,
      			nextState
      		})
		}),
      {
        
        [tmSymbol('H', state)]: [
          tmSymbol('H', state, 1),
          tmSymbol('H', state, 0)
        ],
        [tmSymbol('L', state)]: [
          tmSymbol('L', state, 1),
          tmSymbol('L', state, 0)
        ],
        [tmSymbol('R', state)]: [
          tmSymbol('R', state, 1),
          tmSymbol('R', state, 0)
        ],
        [tmSymbol('R', state, '*')]: [
          tmSymbol('R', state),
          tmSymbol('R', state)
        ]
      }
    );

const encodeTmStateMap = (stateMap) =>
	Object.entries(stateMap).reduce(
      (acc, [state, stateDescription]) =>
      ({
        ...acc,
        ...encodeTmState(state, stateDescription)
      }),
      {}
    );

function compileTmToPostMachineDescription ({ stateMap, start, n: m }) {
  const states = Object.keys(stateMap);
  const A = tmAlphabet(states);
  
  const P = encodeTmStateMap(stateMap);
  
  const H = null;
  
  return { m, A, P, H };
}

function tmStartToStartingWord({ startTape, startPosition, startState, n }) {
  const repeat = (array, times) => new Array(times).fill(array).flat();
  
  // ----------
  //
  // Borrowed from the encoded TM implementation
  // encodes a tape as three numbers representing two stacks and
  // a register, representing the tape to the left, the tape
  // to the right, and the register
  //
  // thought to be broken, fundamental problem is not
  // fully understanding the mechanisms
  function validatedSymbolNumber (s, n) {
    if (s >= n || s < 0) throw new Error(`${s} must be >= 0 and < ${n}`);

    return s;
  }

  function encodeTape (tapeArray, n) {
    return tapeArray.reduce(
      (accumulator, currentValue, currentIndex) =>
          accumulator + (
            validatedSymbolNumber(currentValue, n) * Math.pow(n, currentIndex)
          ),
      0
    );
  }
  // ----------

  const leftTape = startTape.slice(0, startPosition).reverse();
  const leftEncoded = encodeTape(leftTape, n);

  const rightTape = startTape.slice(startPosition);
  const rightEncoded = encodeTape(rightTape, n);
  
  console.log({ leftEncoded, rightEncoded });
  
  // first crack (probably broken)
  const startingWord = [
    tmSymbol('H', startState, 1),
    tmSymbol('H', startState, 0),
    ...repeat(
      [tmSymbol('L', startState, 1), tmSymbol('L', startState, 0)],
      leftEncoded
    ),
    ...repeat(
      [tmSymbol('R', startState, 1), tmSymbol('R', startState, 0)],
      rightEncoded
    )
  ];
  
  return startingWord;
}

function decodeWord (word, n) {
  function decodeTape (code, n) {
    const tape = [];
    
    while (code > 0) {
      const remainder = code % n;
      const quotient = Math.floor(code / n);
      tape.push(remainder);
      code = quotient;
    }
    
    return tape;
  }
  
  const lefts = word.filter(s => s.startsWith('L')).length;
  const rights = word.filter(s => s.startsWith('R')).length;
  
  const decodedLeft = decodeTape(lefts, n);
  const decodedRight = decodeTape(rights, n);
  
  const leftHead = decodedLeft.length > 0
  	? decodedLeft[0]
  	: 0;
  const rightHead = decodedRight.length > 0
  	? decodedRight[0]
  	: 0;
  
  const leftTape = decodedLeft.slice(1).reverse();
  const rightTape = decodedRight.slice(1);
  
  if (leftHead > 0 && rightHead > 0) throw new Error(
    `${leftHead} and ${rightHead} can't both be the head`
  );
  const head = leftHead + rightHead;
  
  const tape = leftTape.concat([head]).concat(rightTape);
  const position = leftTape.length;
  
  return { tape, position };
}

try {
  const tmDefinition = {
    stateMap: {
      start: {
        0: [1, 1, 'halt'],
        1: [0, 1, 'start']
      },
      halt: {}
    },
    start: 'start',
    n: 2
  };
  
  const { n } = tmDefinition;
  
  const description = compileTmToPostMachineDescription(tmDefinition);
  
  // const startingWord = tmStartToStartingWord({
  //   startTape: [0, 0],
  //   startPosition: 0,
  //   startState: tmDefinition.start,
  //   n
  // });
  
  const startingWord = [
    'H-start-1',
    'H-start-0',
    'R-start-1',
    'R-start-0',
    'R-start-1',
    'R-start-0'
  ];
 
  const tapes = [];
  const words = [];
  
  console.log(description);

  for (let word of compute({ description, word: startingWord })) {
    if (word != null) {
      const { tape, position } = decodeWord(word, n);
      
      tapes.push(tape.join(''));
      words.push(word);
    }
  }
  
  const lastTape = tapes.slice(-1)[0];
  const lastWord = words.slice(-1)[0];
  
  // for (let tape of tapes) {
  //   console.log(tape);
  // }
  
  console.log(words);
} catch (e) {
  alert(e);
}

encoded-tm.js

// A minimal turing machine compute function based on godel encoding the tape
// The equivalence of this and an "ordinary" Turing Machine is useful for showing that
// recursive functions are Turing-complete and for showing that other machines are
// Turing-complete my showing they can emulate a godel-encoded TM.
//
// This machine dispenses with symbols, and instead requries that symbols from the alphabet
// are encoded with blank being zero, and all other symbols encoded as consecutive
// natural numbers starting with 1.
//
// This machine also does not have an explicit halt. It halts when there is no rule to
// match the symbol under the tape-head in the current state. The degenerate case is
// when we create a state that has no rules, it MUST halt when it reachest that state.
//
// N.B. The godel-encoded machine is limited to emulating the behaviour of machines that
// are bootstrapped with aa finite number of symbols. There are techniques for emulating
// machines with an infinite number of symbols that are periodic in nature.

function validatedSymbolNumber (s, n) {
  if (s >= n || s < 0) throw new Error(`${s} must be >= 0 and < ${n}`);
  
  return s;
}

function encodeTape (tapeArray, n) {
  return tapeArray.reduce(
    (accumulator, currentValue, currentIndex) =>
    	accumulator + (
          validatedSymbolNumber(currentValue, n) * Math.pow(n, currentIndex)
        ),
    0
  );
}

// n is number of symbols
// position is the location of the tape head
function encodeTapeAndPosition (tapeArray, position, n) {
  const leftTape = tapeArray.slice(0, position).reverse();
  const left = encodeTape(leftTape, n);
  const head = validatedSymbolNumber(tapeArray[position], n);
  const rightTape = tapeArray.slice(position + 1);
  const right = encodeTape(rightTape, n);
  
  return { left, head, right };
}

function next ({ definition, state, left, head, right }) {
  const rules = definition.stateMap[state];
  if (rules == null) throw new Error(`#{state} is not defined`);
  
  const { n } = definition;
  if (n == null) throw new Error(`n is not defined`);
  
  const instruction = rules[head];
  // if no instruction for a symbol, halt
  if (instruction == null) return null;
  
  let [write, move, nextState] = instruction;
  if (move === 0) {
    // left
    const nextHead = left % n;
    const nextLeft = (left - nextHead) / n;
    const nextRight = (right * n) + validatedSymbolNumber(write, n);
    
    return {
      definition,
      state: nextState,
      left: nextLeft,
      head: nextHead,
      right: nextRight
    };
  } else if (move === 1) {
    //right
    const nextHead = right % n;
    const nextRight = (right - nextHead) / n;
    const nextLeft = (left * n) + validatedSymbolNumber(write, n);
    
    return {
      definition,
      state: nextState,
      left: nextLeft,
      head: nextHead,
      right: nextRight
    };
  } else throw new Error(`${move} should be 0->L or 1 ->R`);
}

function * compute({ definition, left, head, right}) {
  let state = definition.start;
  if (state == null) throw new Error('definition lacks a start state');
  
  yield { state, left, head, right };
  
  let updated = null;
  while (updated = next({ definition, state, left, head, right })) {
    ({ state, left, head, right } = updated);
    yield { state, left, head, right };
  }
}

try {
  // this machine does a really naive "addition"
  // by assuming that the two numbers are encoded
  // as finite sequences of 1s separated by a single 0.
  //
  // The "addition" is p[erformed by erasing the first 1,
  // scanning right until it encounters a 0, and then writing a 1.
  //
  // 1, 1, 0, 1, 1, 1
  // 0, 1, 0, 1, 1, 1
  // 0, 1, 1, 1, 1, 1
  
  const definition = {
    stateMap: {
      start: {
        0: [0, 1, 'halt'],
        1: [0, 1, 'scan']
      },
      scan: {
        0: [1, 1, 'halt'],
        1: [1, 1, 'scan']
      },
      halt: {}
    },
    start: 'start',
    n: 2
  };
  const { left, head, right } = 
    encodeTapeAndPosition(
      [1, 1, 0, 1, 1, 1],
      0,
      2
    );
  
  const output = [];

  for (let { state, left, head, right } of compute({ definition, ...encodeTapeAndPosition(
      [1, 1, 0, 1, 1, 1],
      0,
      2
    ) })) {
    output.push(`${state}: ${left}, ${head}, ${right}`);
  }
  
  alert(output.join('\r'));
} catch (e) {
  alert(e);
}

post.js

// a post machine emulator

function validatedAlphabet({ description: { A } }) {
  if (A == null) throw new Error('description missing alphabet');
  
  return A;
}

function validatedDeletionNumber({ description: { m } }) {
  if (m == null) throw new Error('description is missing its m');
  if (typeof m !== 'number' || isNaN(m)) throw new Error(`${m} is not a number`);
  if (m <= 0) throw new Error(`${m} must belong to ℕ+`);
  if (m !== Math.floor(m)) throw new Error(`${m} must belong to ℕ+`);
  
  return m;
}

function validatedHeadSymbol({ description, word }) {
  const A = validatedAlphabet({ description });
  
  if (word == null) throw new Error(`word missing`);
  
  const [head,] = word;
  if (head == null) throw new Error(`word empty`);
  
  if (!A.includes(head)) throw new Error(`alphabet ${A.join(', ')} does not contain ${head}`);
  
  return head;
}

function validatedHaltingSymbol({ description }) {
  
  const { H } = description;
  if (H == null) return null;
  
  const A = validatedAlphabet({ description });
  if (!A.includes(H)) throw new Error(`alphabet ${A.join(', ')} does not contain halting symbol ${H}`);
  
  return H;
}

function validatedProductionRules({ description: { P, H } }) {
  if (P == null) throw new Error('description missing production rules');
  if (H != null && Object.hasOwn(P, H)) throw new Error('the halting symbol ${H} should not have a production rule');
  
  return P;
}

function isHaltingWord({ description, word }) {
  
  const m = validatedDeletionNumber({ description });
  
  // too short
  if (word.length < m) return true;
  
  const head = validatedHeadSymbol({ description, word });
  
  const H = validatedHaltingSymbol({ description });
  
  // leads with the halting symbol
  if (H != null && head === H) return true;
  
  const P = validatedProductionRules({ description });
  
  // has no production rules
  return !Object.hasOwn(P, head);
}

function validatedProduction({ description, word }) {
  const A = validatedAlphabet({ description });
  const P = validatedProductionRules({ description });
  const head = validatedHeadSymbol({ description, word });
  
  if (!A.includes(head)) throw new Error(`alphabet ${A.join(', ')} does not contain ${head}`);
  
  return P[head];
}

function transformation({ description, word }) {
  // no change if halted
  if (isHaltingWord({ description, word })) return { description, word };
  
  // our definition of a halting word includes a word
  // that has a head without a production rule
  const p = validatedProduction({ description, word });
  
  const m = validatedDeletionNumber({ description });
  
  return { description, word: word.concat(p).slice(m) };
}

function * compute({ description, word }) {
  yield word;
  
  while (!isHaltingWord({ description, word })) {
    ({ word } = transformation({ description, word }));
    yield word;
  }
}

try {
  const description = {
    // deletion number
    m: 2,

    // alphabet
    A: ['a', 'b', 'c', 'H'],

    // production rules
    P: {
      a: 'bc'.split(''),
      b: 'a',
      c: 'aaa'.split('')
    },

    // halting symbol, not used in this machine
    H: 'H'
  };
  const startingWord = 'aaaaa'.split('');
   
  const output = [];

  for (let word of compute({ description, word: startingWord })) {
    if (word != null) output.push(word.join(''));
  }
  
  for (let line of output) {
    console.log(line);
  }
} catch (e) {
  alert(e);
}