raganwald

// 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');

raganwald

const truncated = a => {
  let aa = [...a];
  
  while (aa.length > 1 && (aa[aa.length - 1] === 0 || aa[aa.length - 1] == null)) {
    aa = aa.slice(0, aa.length - 1);
  }
  
  return aa;
}

raganwald

// Multiplies two numbers
//
// The numbers are encoded as strings of `1`s separated by a single `0`
//
// e.g. 2x3 => 6
// [1, 1, 0, 1, 1, 1] => [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
//
// Dependencies:
// - The TM must understand aribtrary tape marks (numbers *and* strings)
// - The TM must allow sequences of instructions e.g. Write(1), Move(LEFT)

raganwald

(from Hilbert's Grand JavaScript School)

---

day six

Bertie goes home, exhausted, and dreams that having graduated everyone at the end of Day Five, things are busier than ever. In his dreams he imagines an infinite number of galactic superclusters, each containing an infinite number of galaxies, each containing an infinite number of stars, each containing an infinite number of worlds, each containing an infinite number of oceans, each containing an infinite number of aircraft carriers, each containing an infinite number of buses, each containing an infinite number of students.

He awakens and reasons that what he is dealing with are powers of infinity. A simple infinity is infinity to the first power. Two infinities (buses and students) is infinity to the second power. Three infinities (aircraft carriers, buses, and students) is infinity to the third power. And so forth up to galactic superclusters, infinity to the eighth power.

raganwald

//
// http://raganwald.com/2019/01/14/structural-sharing-and-copy-on-write.html
// http://raganwald.com/2019/01/26/reduce-reuse-recycle.html
//

const SliceHandler = {
  has (slice, property) {
    if (property in slice) {
      return true;
    }

raganwald

// handles primitives like integers and arrays of simple primitives
// all other behaviour is undefined

function superSimpleEquivalent(a, b) {
  if (a instanceof Array && b instanceof Array) {
    if (a.length != b.length) return false;
    
    for (let i = 0; i < a.length; ++i) {
      if (!superSimpleEquivalent(a[i], b[i])) return false;
    }

raganwald

// A state machine that works from a description including explicit transitions,
// and can generate a transition map and a digraph

const STATES = Symbol("states");
const STARTING_STATE = Symbol("starting-state");
const TRANSITIONS = Symbol("transitions");
const RESERVED = [STARTING_STATE, TRANSITIONS];

const MACHINES_TO_CURRENT_STATE_NAMES = new WeakMap();
const MACHINES_TO_STARTING_STATES = new WeakMap();

raganwald

function * just (...values) {
  yield * values;
};

function first (iterable) {
  const iterator = iterable[Symbol.iterator]();

  const { done, value } = iterator.next();
  if (!done) return value;
};

raganwald

We wish to compute fib(7).

This is a FRACTRAN program for computing any Fibonacci number: 17/65, 133/34, 17/19, 23/17, 2233/69, 23/29, 31/23, 74/341, 31/37, 41/31, 129/287, 41/43, 13/41, 1/13, 1/3.

The seed n is computed n = 78 * 5^(x - 1). Therefore, we start with n = 78 * 5^(7-1), which is 1,218,750.

• The first fraction in the program is 17/65. 1,218,750 multiplied by 17/65 is 318,750, so we replace 1,218,750 with 318,750 and begin again.
• The first fraction in the program is 17/65. 318,750 leaves a remainder when divided by 65, so we move on.
• The next fraction in the program is 133/34. 318,750 multiplied by 133/34 is 1,246,875, so we replace 318,750 with 1,246,875 and begin again.
• The first fraction in the program is 17/65. 1,246,875 leaves a remainder when divided by 65, so we move on.

raganwald

const END = Symbol('end');

class PushdownAutomaton {
  constructor(internal = 'start', external = []) {
    this.internal = internal;
    this.external = external;
    this.halted = false;
    this.recognized = false;
  }