Skip to content

Instantly share code, notes, and snippets.

View raganwald's full-sized avatar

Reg Braithwaite raganwald

View GitHub Profile
@raganwald
raganwald / broken-tm-emulator.js
Last active November 21, 2023 15:33
Turing and Post Machine Love
View 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');
@raganwald
raganwald / collatz-minky.js
Created September 25, 2023 15:54
A Magnificent Minsky Machine that determines whether a natural number halts
View collatz-minky.js
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
raganwald / multiply.es6
Last active June 26, 2023 19:54
Turing Machine program that multiplies two numbers
View multiply.es6
// 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
raganwald / infinity.md
Last active December 21, 2022 03:12
Infinity to the power of infinity
View infinity.md

(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.

View slice.es6
//
// 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
raganwald / pyramid_problem.js
Created January 14, 2022 15:07
Sketching out some solutions to the Pyramid Problem
View pyramid_problem.js
// 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
raganwald / draw-diagrams.es6
Last active January 3, 2022 20:38
State Machines
View draw-diagrams.es6
// 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
raganwald / out.md
Last active May 4, 2020 18:19
Computing fib(7) with FRACTRAN
View out.md

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
raganwald / pushdown.oop.es6
Created September 21, 2019 21:46
Pushdown Automata
View pushdown.oop.es6
const END = Symbol('end');
class PushdownAutomaton {
constructor(internal = 'start', external = []) {
this.internal = internal;
this.external = external;
this.halted = false;
this.recognized = false;
}