Last active
June 3, 2024 00:23
-
-
Save wpcarro/4002e3f1df0b64271a0d1e8964b3601a to your computer and use it in GitHub Desktop.
More ergonomic way of defining state transition ruleset
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Defines a function, compile, that can convert a textual | |
// representation of a state transition ruleset into a function | |
// that we can invoke to transition from one state to another. | |
// | |
// Also defines a simple function, decode, that converts a | |
// textual representation of a program into the "tape" that we | |
// feed our Turing Machine. | |
//////////////////////////////////////////////////////////////// | |
// Types | |
//////////////////////////////////////////////////////////////// | |
enum State { | |
Init = "INIT", | |
ReadInstruction = "READ", | |
MoveToEnd = "M2E", | |
MoveToBeg = "M2B", | |
Discard = "DSC", | |
Accept = "ACPT", | |
Reject = "RJCT", | |
} | |
type Head = { i: number; state: State; }; | |
enum Alphabet { | |
Zero = "0", | |
Hash = "#", | |
Discarded = "X", | |
SectorSep = "|", | |
EOL = "$", | |
}; | |
enum Direction { | |
Right = "R", | |
Left = "L", | |
Stay = "_", | |
}; | |
type Tape = Alphabet[]; | |
type Program = { | |
head: Head; | |
tape: Tape; | |
}; | |
type Transition = (program: Program) => [Alphabet | null, Direction, State]; | |
//////////////////////////////////////////////////////////////// | |
// Library | |
//////////////////////////////////////////////////////////////// | |
function matches(state: State, v: Alphabet | null, program: Program): boolean { | |
return program.head.state === state && (v === null ? true : program.tape[program.head.i] === v); | |
} | |
function compile(table: string): Transition { | |
const states: {[x: string]: State} = { | |
"INIT": State.Init, | |
"READ": State.ReadInstruction, | |
"M2E": State.MoveToEnd, | |
"M2B": State.MoveToBeg, | |
"DSC": State.Discard, | |
"ACPT": State.Accept, | |
"RJCT": State.Reject, | |
}; | |
const alphabet: {[x: string]: Alphabet} = { | |
"$": Alphabet.EOL, | |
"X": Alphabet.Discarded, | |
"#": Alphabet.Hash, | |
"|": Alphabet.SectorSep, | |
"_": null, | |
}; | |
const directions: {[x: string]: Direction} = { | |
"R": Direction.Right, | |
"L": Direction.Left, | |
"_": Direction.Stay, | |
}; | |
const rules: string[] = table.trim().split("\n"); | |
const result: [State, Alphabet | null, Alphabet | null, Direction, State][] = []; | |
for (const rule of rules) { | |
const [s0, read, write, dir, s1] = rule.trim().split(/\s+/); | |
const [a, b, c, d, e] = [states[s0], alphabet[read], alphabet[write], directions[dir], states[s1]]; | |
if (typeof a === "undefined") throw new Error(`Failed to decode s0: ${s1}`); | |
if (typeof b === "undefined") throw new Error(`Failed to decode read: ${read}`); | |
if (typeof c === "undefined") throw new Error(`Failed to decode write: ${write}`); | |
if (typeof d === "undefined") throw new Error(`Failed to decode direction: ${dir}`); | |
if (typeof e === "undefined") throw new Error(`Failed to decode s1: ${s1}`); | |
result.push([a, b, c, d, e]); | |
} | |
return (program) => { | |
for (const rule of result) { | |
const [s0, read, write, move, s1] = rule; | |
if (matches(s0, read, program)) { | |
return [write, move, s1]; | |
} | |
} | |
throw new Error(`Unsupported pattern: ${program.head.state} ${program.tape[program.head.i]}`); | |
}; | |
} | |
const transition = compile(` | |
INIT _ _ R READ | |
READ $ _ R M2E | |
M2E # _ L M2B | |
M2E _ _ R M2E | |
M2B $ _ L M2B | |
M2B # _ R DSC | |
M2B _ _ L M2B | |
DSC _ X R READ | |
READ | _ _ ACPT | |
`); | |
//////////////////////////////////////////////////////////////// | |
// Main | |
//////////////////////////////////////////////////////////////// | |
function decode(tape: string): Tape { | |
return tape.split(" ").map((x) => ({ | |
"#": Alphabet.Hash, | |
"0": Alphabet.Zero, | |
"$": Alphabet.EOL, | |
"|": Alphabet.SectorSep, | |
})[x]); | |
} | |
let program: Program = { | |
head: { i: 0, state: State.Init }, | |
// Schema:# PROGRAM # RAM # | |
// Read instruction from PROGRAM (including immediate values - no pointers) | |
tape: decode("# $ | 0 0 0 0 #"), | |
}; | |
let s: number = 0; | |
while (![State.Accept, State.Reject].includes(program.head.state)) { | |
console.log(`[ ${program.tape.join(" | ")} ] ${program.head.state}`); | |
console.log(" ".repeat(program.head.i * 4) + " ^ "); | |
if (s > 40) { | |
console.log("Exhausted"); | |
break; | |
} | |
const [w, direction, state] = transition(program); | |
if (w !== null) { | |
program.tape[program.head.i] = w; | |
} | |
program.head.state = state; | |
switch (direction) { | |
case Direction.Left: { | |
program.head.i -= 1; | |
break; | |
} | |
case Direction.Right: { | |
program.head.i += 1; | |
break; | |
} | |
} | |
s += 1; | |
} | |
if (program.head.state === State.Accept) { | |
console.log("Success!"); | |
} else { | |
console.log("Failure."); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment