@turing-machine-js/machine

A composable Turing-machine engine for JavaScript: multi-tape, subroutine composition via withOverriddenHaltState, Mermaid round-trip, and runtime breakpoints.

For runtime highlight + breakpoint rendering on top of the engine's Graph, plus a byte-identical edge-label formatter and snippet-recording artifacts, see the companion package @turing-machine-js/visuals.

• Install
• Quick start
• Building from a state table
• Classes — Alphabet · Tape · TapeBlock · TapeCommand · Command · State · Reference · TuringMachine
• Subroutine composition with withOverriddenHaltState
• State tags
• Debugging breakpoints
• Special objects — haltState · Sentinels: halt vs abort · ifOtherSymbol · movements · symbolCommands
• Introspection and testing
• Diagram conventions
• Versioning notes
• Libraries
• Links

Install

Using npm:

npm install @turing-machine-js/machine

Quick start

Replace every b on the tape with *:

import {
  Alphabet,
  State,
  Tape,
  TapeBlock,
  TuringMachine,
  haltState,
  ifOtherSymbol,
  movements,
} from '@turing-machine-js/machine';

const alphabet = new Alphabet([' ', 'a', 'b', 'c', '*']);
const tape = new Tape({ alphabet, symbols: ['a', 'b', 'c', 'b', 'a'] });
const tapeBlock = TapeBlock.fromTapes([tape]);
const machine = new TuringMachine({ tapeBlock });

machine.run({
  initialState: new State({
    [tapeBlock.symbol(['b'])]: {
      command: [{ symbol: '*', movement: movements.right }],
    },
    [tapeBlock.symbol([alphabet.blankSymbol])]: {
      command: [{ movement: movements.left }],
      nextState: haltState,
    },
    [ifOtherSymbol]: {
      command: [{ movement: movements.right }],
    },
  }, 'replaceB'),
});

console.log(tape.symbols.join('').trim()); // a*c*a

The state graph for the example above (toMermaid(toGraph(replaceB, tapeBlock))):

flowchart TD
%% alphabets: [[" ","a","b","c","*"]]
  s0(((halt)))
  u1["replaceB"]
  idle([idle])
  idle -. enter .-> u1
  u1 -- "['b'] → ['*']/[R]" --> u1
  u1 -- "[B] → [K]/[L]" --> s0
  u1 -- "[*] → [K]/[R]" --> u1

Reading this specific diagram: replaceB (the rectangle) is the start state, marked by the dotted enter arrow from the idle sentinel. Three self-or-halt transitions: read 'b' → write '*' and step right; read anything else (*) → keep, step right; read blank (B) → keep, step left, halt. Full notation reference — shapes, edge styles, label vocabulary — in §Diagram conventions.

A State is keyed by JS Symbols returned from tapeBlock.symbol(pattern) — the pattern lists the expected symbol under each tape's head. Sentinels and constants used throughout: ifOtherSymbol is the fallback key when nothing else matches; transitioning into haltState stops the run; movements.{left,right,stay} direct head moves; symbolCommands.{keep,erase} are write shortcuts. Full definitions in §Special objects.

For multi-tape machines, pass one element per tape: tapeBlock.symbol(['0', 'a']) matches only when tape 1 is at '0' and tape 2 is at 'a'. See the multi-tape example in §Diagram conventions for what the rendered graph looks like.

Building from a state table

If you prefer a textbook-style declarative API where every transition is one row of (state, currentSymbol) → (nextState, nextSymbol, movement), you can build a small helper on top of the raw API. The whole thing fits in ~30 lines:

import {
  Alphabet,
  Reference,
  State,
  TapeBlock,
  TuringMachine,
  haltState,
  ifOtherSymbol,
  movements,
  symbolCommands,
} from '@turing-machine-js/machine';

function buildFromTable({ alphabetString, initialState, finalStates, table }) {
  const alphabet = new Alphabet(alphabetString.split(''));
  const tapeBlock = TapeBlock.fromAlphabets([alphabet]);
  const movementOf = { L: movements.left, R: movements.right, S: movements.stay };

  // Pre-create a Reference per state name so transitions can point forward.
  const refs = Object.fromEntries(Object.keys(table).map((name) => [name, new Reference()]));
  const states = {};

  for (const [name, row] of Object.entries(table)) {
    const def = {};
    for (const [read, action] of Object.entries(row)) {
      const key = read === '*' ? ifOtherSymbol : tapeBlock.symbol([read]);
      def[key] = {
        command: {
          symbol: action.write ?? symbolCommands.keep,
          movement: movementOf[action.move ?? 'S'],
        },
        nextState: finalStates.includes(action.goto) ? haltState : refs[action.goto],
      };
    }
    states[name] = new State(def, name);
    refs[name].bind(states[name]);
  }

  return { tapeBlock, machine: new TuringMachine({ tapeBlock }), initialState: states[initialState] };
}

// Same "replace b with *" example as above, written declaratively:
const { tapeBlock, machine, initialState } = buildFromTable({
  alphabetString: ' abc*',
  initialState: 'scan',
  finalStates: ['HALT'],
  table: {
    scan: {
      'b': { write: '*', move: 'R', goto: 'scan' },
      ' ': {              move: 'L', goto: 'HALT' },
      '*': {              move: 'R', goto: 'scan' },  // '*' = ifOtherSymbol
    },
  },
});

This is what @turing-machine-js/builder provides as a separate package. Inline lets you tweak the format (multi-tape, OR-patterns, custom action shapes) freely; the builder package is more opinionated and limited to single-tape, single-symbol-per-row transitions.

Classes

Alphabet

The set of single-character symbols a tape can hold. The first symbol passed to the constructor is the blank — it fills any tape cell the head reaches before that cell has been written. At least two unique single-character symbols are required.

const alphabet = new Alphabet([' ', '0', '1']);
alphabet.blankSymbol;   // ' '
alphabet.symbols;       // [' ', '0', '1']
alphabet.has('0');      // true
alphabet.index('1');    // 2

Tape

An infinite-in-both-directions sequence of cells over an Alphabet, plus a head position. Cells the head moves into that haven't been written are blank.

const tape = new Tape({ alphabet, symbols: ['a', 'b', 'c'], position: 0 });
tape.symbol;        // 'a' (cell under head)
tape.right();       // move head right; auto-extends with blanks at the edge
tape.symbol = 'X';  // write the cell under head

For visualization-friendly UIs, Tape exposes a fixed-width viewport centered on the head:

const tape = new Tape({ alphabet, symbols: ['a', 'b', 'c'], viewportWidth: 7 });
tape.viewport;       // 7-cell snapshot centered on the head, padded with blanks
tape.viewportWidth;  // 7 (the constructor bumps even values to the next odd)

viewportWidth defaults to 1 and must be ≥ 1; tape.viewport always has exactly viewportWidth cells regardless of how many symbols the tape actually holds. Useful for rendering a sliding window in a UI; ignore if you only need tape.symbols / tape.position.

For wire-data tape transmission (worker boundaries, snippet recording, snapshot tests), the package exports the TapeSnapshot type ({ symbols: string[]; position: number }) and a pure-function equivalent of Tape.viewport:

import { tapeViewport } from '@turing-machine-js/machine';

const snapshot = { symbols: ['a', 'b', 'c'], position: 1 };
const { cells, headIndex } = tapeViewport(snapshot, 7, ' ');
// cells: [' ',' ','a','b','c',' ',' '], headIndex: 3

tapeViewport(snapshot, width, blank) returns { cells, headIndex } with cells.length === width (out-of-bounds positions padded with blank) and headIndex === Math.floor(width / 2). Throws RangeError on non-positive or non-integer width. Tape.viewport and tapeViewport share an internal centering core, so the two routes produce identical results when given equivalent inputs. (TapeSnapshot + tapeViewport are also re-exported from @turing-machine-js/visuals for backwards-compatible imports from earlier alphas; canonical home is @turing-machine-js/machine as of v7.0.0-alpha.8, #227.)

TapeBlock

A bundle of one or more Tapes that the machine reads/writes together in lock-step. Construct via either factory:

TapeBlock.fromAlphabets([alphabetA, alphabetB]);  // creates fresh blank tapes
TapeBlock.fromTapes([tape1, tape2]);              // reuses existing tapes

The key method is tapeBlock.symbol(pattern): it returns an interned JS Symbol that simultaneously serves as a State's transition key and matches the current configuration across all tapes. The pattern is one alphabet character per tape; pass several patterns by concatenating to express alternatives.

tapeBlock.symbol(['^']);                  // single tape: matches '^'
tapeBlock.symbol(['^', '0', '1', '$']);   // single tape: matches any of '^', '0', '1', '$'
tapeBlock.symbol(['0', 'a']);             // 2 tapes: matches when tape 1 is '0' AND tape 2 is 'a'

TapeCommand

A single-tape instruction the machine applies in one step: optionally write a symbol, optionally move the head. Defaults to keep current symbol, do not move.

const cmds = [
  { symbol: '0', movement: movements.right },     // write '0' and move right
  { movement: movements.left },                   // keep current symbol, move left
  { symbol: symbolCommands.erase },               // write the blank, stay
  {},                                             // no-op
];

You'll rarely construct TapeCommand instances yourself — pass plain objects in your State definitions and they're wrapped automatically.

Command

A bundle of TapeCommands, one per tape in the TapeBlock. Like TapeCommand, you usually pass a plain array in the State definition rather than constructing Command directly.

State

A node in the transition graph. Construct with a definition object whose keys are JS Symbols from tapeBlock.symbol(...) (or ifOtherSymbol for the catch-all). Each value is { command, nextState }.

const s = new State({
  [tapeBlock.symbol(['1'])]: { command: { symbol: '0', movement: movements.right } },
  [tapeBlock.symbol(['$'])]: { command: { movement: movements.left }, nextState: haltState },
}, 'name');

Notable members and statics:

• state.id, state.name — identity (isHalt is id === 0).
• state.withOverriddenHaltState(other) — returns a CallFrame (a State subclass, so it flows anywhere a State does) whose would-be halt transitions fall through to other. The subroutine-call composition mechanism (see library-binary-numbers/src/index.ts for examples). instanceof CallFrame is the wrapper discriminator.
• State.toGraph(state, tapeBlock) — walks the reachable graph from state and returns a serializable Graph (states, transitions, alphabets).
• State.fromGraph(graph) — inverse of toGraph: rebuilds State instances + a fresh TapeBlock from a Graph. Round-trips together with toMermaid / fromMermaid.
• State.collectStates(state, tapeBlock) — walks the same graph and returns a Map<number, {state, transitionSymbols}> keyed by GraphNode.id. Use when downstream tooling holds a numeric id (e.g. a clicked node in a rendered graph) and needs the live State instance or the per-pattern Symbol for breakpoint setup. See Setting breakpoints by graph id.

For visualization, pair State.toGraph with toMermaid to render the graph in any Mermaid-aware viewer (GitHub, VS Code, mermaid.live):

import { State, toMermaid } from '@turing-machine-js/machine';

const graph = State.toGraph(s, tapeBlock);
console.log(toMermaid(graph));

The string toMermaid produces is a real Mermaid flowchart that renders in-place anywhere Mermaid is supported:

flowchart TD
%% alphabets: [[" ","0","1","$"]]
  s0(((halt)))
  u1["name"]
  idle([idle])
  idle -. enter .-> u1
  u1 -- "['1'] → ['0']/[R]" --> u1
  u1 -- "['$'] → [K]/[L]" --> s0

Edge labels are read → write/move. Write commands: K = keep (no write), E = erase (write the blank). Literal alphabet symbols are quoted ('1', '$'). Movements: L (left), R (right), S (stay).

💡 Mermaid renders at most one edge per source/target pair. If a state has two distinct transitions back to itself (or two parallel transitions to the same target), only one shows in the diagram. The string output is correct — this is a viewer-side limitation. For graphs with multiple parallel edges, paste the toMermaid output into mermaid.live and switch to the stateDiagram-v2 renderer, or post-process the output to your preferred format.

fromMermaid parses the same format back into a Graph. The round-trip is behaviorally lossless — the rebuilt graph runs to the same outputs on the same inputs (tested in test/round-trip.spec.ts for the binary-numbers libraries). Under the v7 callable-subtree emit (#174), bytewise stability holds across rebuilds even for shared-bare cases (modulo state-id renumbering, which the test normalizes). The composite name is not stored as any graph node's label — fromGraph recomputes it fresh on reconstruction — so the accumulation problem from #138 cannot reoccur.

Reference

A forward-declaration handle, used when a State needs to point at another State that doesn't exist yet (cyclic graphs). Construct unbound, pass as nextState, call .bind(actualState) once that state has been built.

const ref = new Reference();
const a = new State({ [symbol(['x'])]: { nextState: ref } }, 'a');
const b = new State({ [symbol(['y'])]: { nextState: a  } }, 'b');
ref.bind(b);   // a's transition now resolves to b at run time

The resulting cycle (toMermaid(toGraph(a, tapeBlock))):

flowchart TD
%% alphabets: [[" ","x","y"]]
  u1["a"]
  u2["b"]
  idle([idle])
  idle -. enter .-> u1
  u1 -- "['x'] → [K]/[S]" --> u2
  u2 -- "['y'] → [K]/[S]" --> u1

idle -. enter .-> points at the initial state passed to toGraph (a here); b is reachable from a via the bound Reference.

reference.ref returns the bound state and throws if the reference is still unbound when the machine runs. bind() is sticky — the first call wins; subsequent calls are silent no-ops that return the existing binding.

TuringMachine

The runtime. Owns one TapeBlock and drives a state graph until it reaches haltState.

const machine = new TuringMachine({ tapeBlock });

// Run to halt — `run()` is synchronous and returns a RunResult:
const result = machine.run({ initialState, stepsLimit: 1e5 });
// result: { outcome: 'halted' | 'aborted', state, stack, step } — see
// "Sentinels: halt vs abort" below for the aborted case.

// Or step-by-step (useful for tracing / observation):
for (const step of machine.runStepByStep({ initialState })) {
  console.log(step.state.name, step.currentSymbols, '→', step.nextSymbols, step.movements);
}

// For interactive debugging (breakpoints, step-in / step-over / step-out,
// throttle, click-pause), construct a DebugSession — see "Debugging" below.

Each yielded step (MachineState) has these fields:

| Field | Type | Meaning | |---|---|---| | step | number | 1-indexed iteration number | | state | State | the state about to execute | | currentSymbols | string[] | per-tape head symbols, before the command applies | | nextSymbols | string[] | per-tape symbols that will be written | | movements | symbol[] | per-tape head moves (movements.left/right/stay) | | nextState | State | the state that will execute next | | matchedTransition | { id: string, matchKinds: ('wildcard'\|'literal')[] } | the transition the engine picked for this iter — see Matched transition below |

stepsLimit (default 1e5) guards against runaway loops — exceeding it throws.

Choosing between run(), runStepByStep(), and DebugSession

Three non-overlapping entry points, picked by the consumer's actual need:

| | run() | runStepByStep() | new DebugSession(machine, ...) | |---|---|---|---| | Shape | sync, returns RunResult | sync generator, returns RunResult | async session with events | | Observation | none | per-iter via .next() | event-based (pause, step, iter, halt) | | Step controls | — | — | continue / stepIn / stepOver / stepOut / pause / stop | | Throttle | — | — | setRunInterval(ms) | | Breakpoint handling | not consulted — runs straight to halt | not consulted — yields every iter; state.debug is ignored | the only mode that reacts — fires a pause event | | Best for | run-to-halt with no observation overhead | tracing, snapshots, test harnesses, custom batching | UI debuggers, IDE extensions, educational demos |

Rule of thumb. No observation → run(). Sync per-iter observation → iterate runStepByStep(). Anything interactive (breakpoints, step controls, throttle, click-pause) → construct a DebugSession.

run() / runStepByStep() both return a RunResult — { outcome: 'halted' | 'aborted', state, stack, step }, call-scoped so re-running the same machine never leaks stale state from a previous call. runStepByStep's generator carries the value as its return (visible in the final { done: true, value }) — a plain for...of discards it, so per-iter consumers that need the outcome either drain the generator manually (as run() does internally) or check the final yield's nextState identity. See §Sentinels: halt vs abort for the full shape and the abortState counterpart to haltState.

Breakpoint detection lives only in DebugSession. runStepByStep is the pure-iteration primitive — it advances the machine and reports a minimal MachineState with no pause/debug field, ignoring state.debug entirely. DebugSession is what evaluates the filters and turns a match into a pause event. (A consumer that wants its own breakpoint behavior on the raw generator can read state.debug itself.)

Matched transition

Every yielded MachineState carries a matchedTransition describing which transition the engine picked for that iter. The engine already resolves this via state.getNextState(symbol) internally; this field exposes the resolution to consumers so visualizations, log formatters, and coverage maps don't have to re-derive an ambiguous (source, nextState) pair (which collides when multiple transitions on the same source share a destination) or parse pattern strings from toGraph.

matchedTransition: {
  id: string;                               // resolvable in toGraph
  matchKinds: ('wildcard' | 'literal')[];   // per-tape, length = tape count
}

• id — ${stateId}.${transitionIx}. Resolvable in toGraph's output: graph.nodes[stateId].transitions has an entry with the matching id. For wrapper-entry iters (source is a wrapper produced by withOverriddenHaltState), id references the bare's transition — the wrapper's own transitions array in toGraph is empty because wrappers delegate, and the pattern actually lives on the bare. Detect by comparing id.split('.')[0] against state.id: different → wrapper delegation.

• matchKinds — per-tape match kind for the matched alternative's selector at each tape position. 'wildcard' if the position held ifOtherSymbol (catch-all) in the winning alternative; 'literal' if it held a specific symbol or symbol-list. Length always equals tape count.

Example use:

for (const m of machine.runStepByStep({initialState})) {
  const wildcardPositions = m.matchedTransition.matchKinds  // per-tape, e.g. ['wildcard', 'literal']
    .map((k, i) => k === 'wildcard' ? i : -1)
    .filter((i) => i >= 0);
  console.log(`step ${m.step}: fired transition ${m.matchedTransition.id} (wildcards at tapes: ${wildcardPositions.join(',') || 'none'})`);
}

Subroutine composition with withOverriddenHaltState

state.withOverriddenHaltState(other) returns a CallFrame — a State subclass that delegates transition lookups and debug to state (its bare) and whose would-be halt transitions fall through to other at run time. The bare is left untouched. Because a CallFrame is a State, it flows anywhere a State does (as a nextState, through toGraph/fromGraph); instanceof CallFrame distinguishes it from a plain state. This is the engine's only composition primitive — bigger machines are built by stacking smaller halt-on-completion subroutines.

import { Alphabet, State, TapeBlock, TuringMachine, Tape, haltState, ifOtherSymbol, movements, symbolCommands } from '@turing-machine-js/machine';

const alphabet = new Alphabet([' ', 'a', 'b', 'X']);
const tapeBlock = TapeBlock.fromAlphabets([alphabet]);
const { symbol } = tapeBlock;

// Reusable subroutine 1: walk right until 'X', halt on it.
const scanToX = new State({
  [symbol(['X'])]: { nextState: haltState },
  [ifOtherSymbol]: { command: { movement: movements.right } },
}, 'scanToX');

// Reusable subroutine 2: erase the head cell, halt.
const eraseHere = new State({
  [ifOtherSymbol]: { command: { symbol: symbolCommands.erase }, nextState: haltState },
}, 'eraseHere');

// Compose: scan to X, then ERASE it. scanToX is unmodified.
const scanThenErase = scanToX.withOverriddenHaltState(eraseHere);

const tape = new Tape({ alphabet, symbols: ['a', 'b', 'X', 'b', 'a'] });
tapeBlock.replaceTape(tape);
await new TuringMachine({ tapeBlock }).run({ initialState: scanThenErase });

console.log(tape.symbols.join('')); // "ab ba" — the X at index 2 is gone, head landed there.

What changes between running scanToX standalone and running the composed wrapper:

toMermaid(toGraph(scanToX, tapeBlock)) — the standalone subroutine:

flowchart TD
%% alphabets: [[" ","a","b","X"]]
  s0(((halt)))
  u1["scanToX"]
  idle([idle])
  idle -. enter .-> u1
  u1 -- "['X'] → [K]/[S]" --> s0
  u1 -- "[*] → [K]/[R]" --> u1

toMermaid(toGraph(scanThenErase, tapeBlock)) — the wrapped composition:

flowchart TD
%% alphabets: [[" ","a","b","X"]]
  s0(((halt)))
  u2["eraseHere"]
  u3[["scanToX(eraseHere)"]]
  idle([idle])
  subgraph w_1["callable subtree of scanToX"]
    u1["scanToX"]
    s0-1(((halt)))
  end
  idle -. enter .-> u3
  u3 == "call" ==> u1
  w_1 -. "return" .-> u3
  u3 --> u2
  u1 -- "['X'] → [K]/[S]" --> s0-1
  u1 -- "[*] → [K]/[R]" --> u1
  u2 -- "[*] → [E]/[S]" --> s0

Reading guide — the v7 callable-subtree emit (introduced in #174) models withOverriddenHaltState as a function call: the wrapper is the call site, the bare's subtree is the callable body.

1. [[scanToX(eraseHere)]] (Mermaid subroutine / double-walled-rectangle shape) is the wrapper node. It's the runtime entry point — idle -. enter .-> arrives here — and shows the composite name (bare(override)). Wrappers have no transitions of their own; they delegate to the bare via the call arrow. Placement: this top-level wrapper is drawn OUTSIDE any subgraph; a wrapper that participates in a caller's frame (e.g. an inner-call continuation of another wrapper, as in library-binary-numbers/minusOne) renders INSIDE its owner frame's subgraph with the same [[…]] shape (see #223).
2. subgraph w_1["callable subtree of scanToX"] is the bare's callable subtree — the scope of code that runs when the wrapper is "called." It contains the bare u1["scanToX"], any body states reachable from the bare, and a local halt marker s0-1(((halt))) where the bare's halt-bound transitions land — s0-1 reads as "frame 1's local stand-in for s0" (see §Mermaid id scheme for the full namespacing rule).
3. The bold ==> call from wrapper to bare is the call arrow — visual signature of "wrapper invokes this callable subtree, pushing its override onto the runtime stack." Bold arrows are reserved for wrapper-to-bare calls; counting them in a diagram counts the wrappers in play.
4. The dotted -. return .-> from the subtree back to the wrapper is the return arrow — fires when the bare halts (lands on s0-1) and the stack pops. The wrapper's solid --> u2 (to eraseHere) is the post-return continuation; ordinary transition under the function-call mental model.
5. Real (((halt))) outside any subgraph (s0) is the actual run terminus. Reached only by states OUTSIDE any callable subtree — here, by eraseHere after it erases the cell.

Reading runtime sequence on tape ['a','b','X','b','a']: enter at wrapper [[scanToX(eraseHere)]] (with eraseHere queued as the override); call into the subtree of scanToX; [*] → [K]/[R] self-loops on u1 until the head sees X; the ['X'] → [K]/[S] edge lands on s0-1; return to the wrapper; solid --> u2 to eraseHere; eraseHere runs [*] → [E]/[S] and halts at real s0. Run terminates.

💡 Round-trip stability. toMermaid → fromMermaid → toGraph → toMermaid is bytewise stable for simple wrapped states (#139 regression). The callable-subtree emit (#174) eliminates per-context duplication: shared bares like library-binary-numbers's invertNumber (used by two wrappers in minusOne) render as a single subtree with two & -joined call arrows, and fromGraph rebuilds one shared instance — the sharing survives the round-trip. Bytewise stability does not extend to shared-bare cases, though: node ids are runtime State ids reassigned on every rebuild, and a shared bare's post-rebuild id no longer follows the original emission order, so the serialization reorders. Use equivalentOn to confirm behavioural identity (allAgree: true) when bytewise comparison no longer applies.

Wrappers nest: inner.withOverriddenHaltState(middle).withOverriddenHaltState(outer) chains halt-redirects through middle → outer → halt. library-binary-numbers/src/index.ts's minusOne (the ~(~x + 1) composition) uses a 4-deep nest of wrappers.

State tags

A State carries an optional set of string tags — out-of-band metadata for visualization grouping and debugger labels. Tags don't affect runtime transition lookup, equivalentOn comparisons, or any structural identity; they ride alongside the State.

const s = new State({...}, 'walkToBlank::1')
  .tag('hot', 'subroutine-entry');

s.tags; // readonly ['hot', 'subroutine-entry'] — frozen snapshot
s.untag('hot');
s.tags; // readonly ['subroutine-entry']

Scoped to the wrapper instance. Under withOverriddenHaltState memoization (#175), A.wohs(t1) and A.wohs(t2) are distinct CallFrame instances even though both delegate to the same bare A. Tags live on the frame instance, so tagging one wrapper doesn't propagate to siblings sharing the same bare. Wrappers from withOverriddenHaltState start with an empty tag set (do not inherit from bare); the caller tags explicitly as needed.

Round-trip preserved. state.toGraph writes the tag set to GraphNode.tags; state.fromGraph reads it back and reapplies. toMermaid renders tags two ways: inline in the node label (uN["name<br>tag1, tag2"], universal Mermaid line break) and as classDef tag_<sanitized> + class uN tag_<sanitized> lines for color grouping. fromMermaid splits the label on <br> as source of truth; the class lines are decorative and discarded on parse.

See §Diagram conventions § Tags for the full emit shape.

Debugging

The library exposes interactive debugging through the DebugSession class, constructed directly with a TuringMachine. Breakpoints are configured on the engine (state.debug / haltState.debug / abortState.debug); the session dispatches them as events plus offers step-in / step-over / step-out controls, an external pause(), and a per-iter throttle.

import { DebugSession } from '@turing-machine-js/machine';

const session = new DebugSession(machine, { initialState });

session.on('pause', (m) => {
  console.log(`paused at ${m.state.name}, ${m.pause.side} side, cause: ${m.pause.cause}`);
  session.stepIn();              // or stepOver(), stepOut(), continue(), stop()
});
session.on('step', (m) => { /* fires once per iter, mid-iter */ });
session.on('iter', (m) => { /* fires once per iter, end-of-iter */ });
session.on('halt', (result) => { /* fires on natural halt (not on stop()) */ });
session.on('abort', (result) => { /* fires when the run hits abortState (not on stop()) */ });

await session.start();           // resolves on halt, abort, or stop()

Configuring breakpoints

Breakpoints live on the engine, not on the session. The session reads state.debug / haltState.debug / abortState.debug and fires a pause event when a filter matches.

import { State, abortState, haltState, ifOtherSymbol } from '@turing-machine-js/machine';

const myState = new State({...});

// state.debug is always a DebugConfig instance — chained writes work
// without prior whole-object assignment:
myState.debug.before = true;
myState.debug.after = [symA];

// Whole-object assignment also works for one-shot setup:
myState.debug = { before: true };
myState.debug = { before: [symA] };
myState.debug = { before: [symA], after: [symA] };

// Pause when the engine is about to enter halt (program exit OR subroutine pop).
// haltState.debug is a `boolean` (#207) — halt is terminal, so there's only
// one meaningful pause moment (post-triggering-iter, before halt processing).
haltState.debug = true;
haltState.debug = false;        // turn off
haltState.debug = null;         // alias of false (reset)

// abortState.debug mirrors haltState.debug (#239) — same boolean shape, same
// single pause moment: the AFTER side of the iter whose transition targets
// abortState, fired before the terminal 'abort' event.
abortState.debug = true;
abortState.debug = false;       // turn off
abortState.debug = null;        // alias of false (reset)

// Reset filters later on a regular state — next read returns a fresh empty DebugConfig:
myState.debug = null;

⚠️ haltState.debug and abortState.debug are boolean-only. Any object-shaped write ({ before: true }, { after: true }, { before: true, after: true }) throws at write time on either sentinel. The pause fires on the AFTER side of the iter whose transition leads to the sentinel — m.state is the triggering state (not the sentinel itself), m.pause.side === 'after'.

⚠️ An after-side breakpoint on the sentinel-triggering state collapses with haltState.debug / abortState.debug into a single pause. Both target the AFTER side of the same iter — the one whose transition leads to halt or abort — and the engine fires at most one pause per iter-side, so you get one pause event (side: 'after', cause: 'breakpoint'), not two. This is intentional: neither sentinel has an iteration of its own, so "after the triggering state" and "before halt/abort" are the same execution moment. (Contrast two ordinary states A → B: A's after and B's before are different iters, so they fire as two pauses.) There is deliberately no flag to emit a second, ephemeral sentinel pause — one event for one real moment.

⚠️ Chained-form haltState.debug.before = true (or abortState.debug.before = true) doesn't throw in non-strict mode — this is a JavaScript primitive quirk, not engine behavior. The getter returns the boolean false; assigning .before to that boolean is a no-op in non-strict mode (silent), a TypeError in strict mode. The engine setter only sees whole-object writes (haltState.debug = X / abortState.debug = X). Always use the whole-object form: = true / = false / = null.

The debug field is mutable — toggle breakpoints at runtime without rebuilding the graph. A CallFrame (from state.withOverriddenHaltState(...)) delegates its debug to the bare, so an assignment on the original is visible from every wrapper and vice versa. state.debug is always a DebugConfig instance (lazy-initialized on first read); plain-object input is wrapped automatically. The instance is Object.seal-ed — typos like state.debug.bofore = true throw TypeError instead of silently creating a useless property.

Filter semantics: true is a wildcard (match any symbol). [ifOtherSymbol] is NOT a wildcard — it matches only the catch-all resolution case (same meaning as in transition keys).

Caveat: haltState and abortState are both module-level singletons. Setting either one's .debug affects every machine in the process; clear in afterEach / finally for test isolation.

DebugSession API

| Method | Description | |---|---| | start(): Promise<void> | Begin execution. Resolves on natural halt, abort, or after stop(). Single-use — a second call throws. | | continue() | Resume from a pause and run to the next breakpoint or halt. | | stepIn() | Resume and pause at the very next iter, regardless of depth — descends into any subroutine the current iter enters. Mirrors DevTools Step Into. | | stepOver() | Resume and pause at the next iter back at (or above) the click-time halt-stack depth (depth ≤ clickTimeDepth) — subroutines the stepped-over iter enters run to completion without pausing inside. Mirrors DevTools Step Over. | | stepOut() | Resume and pause at the next iter strictly shallower than the click-time depth (depth < clickTimeDepth) — i.e. once the current frame has been popped. Throws if the click-time depth is 0 (no enclosing frame to exit). Mirrors DevTools Step Out. | | pause() | Request a pause from outside the loop. Fires on the next iter with cause: 'manual'. If a breakpoint matches that same iter, the breakpoint wins (single pause, cause: 'breakpoint'). | | stop() | Terminate immediately. halt event does NOT fire. | | setRunInterval(ms) | Insert an awaited setTimeout(ms) at the end of each iter. 0 disables. Useful for visualization UIs. | | on(event, listener) / off(event, listener) | Register / unregister listeners. Multiple listeners per event are supported. Listener dispatch differs by event — see Events below. |

The three step controls are depth-based to mirror DevTools: from a pause at halt-stack depth D, stepIn pauses at the next iter (any depth), stepOver at the next iter with depth ≤ D, stepOut at the next iter with depth < D. For a plain iter (no subroutine entry) all of Into/Over coincide — they differ only under genuine nesting (a bare that itself enters a withOverriddenHaltState wrapper). One engine-specific nuance: composition is continuation-passing (A.wohs(B) = "run A, then B" — sequential, where wohs is withOverriddenHaltState), so a flat .wohs() chain has no real nesting and Over/Out behave the same there; the distinction appears only when a subroutine's body enters another wrapper.

Events

| Event | Argument | Dispatch | Fires | |---|---|---|---| | pause | PausedMachineState (MachineState + pause: {side, cause}) | Implicitly awaited via internal pause-promise — engine blocks until continue / stepIn / stepOver / stepOut / stop is called. Listener Promise itself is fire-and-forget. | A breakpoint matched, a step-mode endpoint was reached, or session.pause() was requested. | | step | MachineState | Fire-and-forget (sync hot-loop tracing). | Once per iter, between any before-pause and after-pause. | | iter | MachineState | Awaited (sequenced, blocks the engine). Use for throttle / per-iter coordination / step-boundary synthesis. | Once per iter, at end. After any after-pause. | | halt | RunResult | Fire-and-forget. | Once, on natural halt. Does NOT fire when stop() was called. | | abort | RunResult | Fire-and-forget. | Once, when the run hits abortState. Does NOT fire when stop() was called. |

halt and abort are mutually exclusive terminal events — a run ends in exactly one of the two, never both, and both carry the same run's RunResult ({outcome, state, stack, step} — see §RunResult) as their listener's argument.

The pause descriptor: m.pause

pause listeners receive a PausedMachineState — a plain MachineState plus a pause: { side, cause } descriptor (raw runStepByStep yields have no such field).

• side — 'before' or 'after'. Exactly one: DebugSession dispatches the two timings as separate pause events, so a descriptor is always one-sided. ('step' / 'manual' causes only ever fire on the 'before' side.)
• cause — distinguishes the origin:
  • 'breakpoint' — a state.debug filter matched, or haltState.debug === true / abortState.debug === true triggered.
  • 'step' — a stepIn / stepOver / stepOut directive's natural endpoint was reached.
  • 'manual' — session.pause() was called from outside.

When an iter satisfies more than one trigger, exactly one pause event fires — never two at the same iter — and cause is chosen by precedence:

breakpoint  >  step  >  manual

So a step-mode endpoint (or a pending manual pause) that lands exactly on a breakpoint reports cause: 'breakpoint'; a manual pause that coincides with a step endpoint reports cause: 'step'. Rationale: a breakpoint is the user's explicit, persistent intent ("always stop here"), so it's the most informative attribution; a step directive is a specific computed endpoint, more specific than the vaguer "pause soon" of a manual request. The step-mode is still consumed (one-shot rule below) regardless of which cause is reported — if the iter was the step's endpoint, the step is satisfied. Matches IDE convention (a breakpoint on the line you step onto reports as a breakpoint stop).

One-shot step-mode rule

Every active step-mode (stepIn / stepOver / stepOut) is dropped on the next pause dispatch — whether that dispatch is the step's own endpoint, an inner breakpoint that fired sooner, or a manual pause. To keep stepping, call stepIn / stepOver / stepOut again from the new pause. Matches IDE convention.

Setting breakpoints by graph id

Downstream UIs (graph renderers, debugger panels) often have only a numeric GraphNode.id — the user clicked a state node, or a transition edge in a rendered SVG. State.collectStates(initial, tapeBlock) returns a Map keyed by that numeric id, with the live State instance and the per-pattern Symbol array as its value:

import { State, ifOtherSymbol } from '@turing-machine-js/machine';

const stateMap = State.collectStates(initial, tapeBlock);

// Toggle a state-level breakpoint by id (any pattern triggers).
const entry = stateMap.get(clickedStateId);
if (entry) {
  entry.state.debug.before = true;
}

// Per-pattern breakpoint by GraphTransition.id — the contract is
// positional: `transitionSymbols[K]` is the Symbol that the
// `${stateId}-${K}` GraphTransition fires on.
const [n, k] = clickedEdgeId.split('-').map(Number);
const e = stateMap.get(n);
const sym = e?.transitionSymbols[k];
if (e && sym) {
  e.state.debug.before = [sym];
}

Coverage rules: regular / bare states get the full [...#symbolToDataMap.keys()] including ifOtherSymbol at its natural slot; wrappers and the halt singleton get empty transitionSymbols; synthetic halt markers (Graph nodes with id = -2 * frameId, one per callable-subtree frame) are excluded from the map. See State.collectStates JSDoc for the full contract.

⚠️ stateMap.get(0)!.state === haltState — the entry at id 0 is the process-wide halt singleton. Toggling its debug affects every machine in the runtime, same caveat as direct haltState.debug writes.

Throttle pattern

For per-iter throttle / animation / "wait between steps" UIs, use session.setRunInterval(ms):

const session = new DebugSession(machine, { initialState });
session.setRunInterval(50);     // 50ms between iters
session.on('iter', (m) => { /* update UI with iter snapshot */ });
await session.start();

The throttle inserts an awaited setTimeout(ms) at the end of every iter, after both pause dispatches (if any) and the iter event. Updates take effect on the next iter. 0 disables.

v7 migration from run({onPause, onStep, onIter, debug})

v7 splits the v6 mixed-mode run() into three non-overlapping entry points. Old shape → new shape:

// v6 — async run() with optional callbacks
await machine.run({
  initialState,
  onStep: (m) => { ... },
  onPause: async (m) => { ... },
  onIter: async (m) => { ... },
  debug: true,
});

// v7 — DebugSession for interactive use
const session = new DebugSession(machine, { initialState });
session.on('step', (m) => { ... });
session.on('pause', (m) => { ...; session.continue(); });
session.on('iter', (m) => { ... });
await session.start();

Or, if you only used run({ initialState }) with no callbacks, just drop the await — run() is now synchronous:

// v6
await machine.run({ initialState });

// v7
machine.run({ initialState });

For sync per-iter tracing without breakpoint-driven flow, iterate the runStepByStep generator directly — onStep no longer exists:

// v6
await machine.run({ initialState, onStep: (m) => trace(m) });

// v7
for (const m of machine.runStepByStep({ initialState })) {
  trace(m);
}

The debug: false master switch is gone — in v7 the session is the only consumer of breakpoints; if you don't register a pause listener, breakpoints fire-and-resume invisibly (the session's start() still resolves cleanly), or you can use runStepByStep directly, which ignores state.debug altogether (its yields carry no pause field).

(History: v6.2.0 briefly widened onStep to void | Promise<void> and added an inline await, motivated by this same throttle use case. That was a mistake — restored to sync in v6.3.0. v6.3.0 documented a workaround using onPause self-rearm on state.debug.after = true; that workaround is superseded by onIter in v6.4.0+.)

Special objects

haltState

A singleton State (id === 0). Transitioning into it stops the run. Imported as a named export from @turing-machine-js/machine; do not construct your own — state.isHalt checks identity against this single instance. See §Sentinels: halt vs abort for abortState, the non-overridable counterpart used for abnormal termination.

Sentinels: halt vs abort

haltState and abortState are the two members of the sentinel family (state.isSentinel ≡ id <= 0) — the only states a machine can transition into that end a run rather than continue it. They mean different things:

• haltState (id === 0) inside a subroutine means return — the run-loop pops the halt-stack and resumes at the caller's continuation. It's the composable case: state.withOverriddenHaltState(next) builds bigger machines out of halt-on-completion subroutines.
• abortState (id === -1, #239) means stop everything. It is never popped by the subroutine halt-stack and never composed by withOverriddenHaltState — it punches straight through call/return and terminates the run, through any call depth. Aborting is a legitimate program outcome, not a host failure: no Error is thrown when a run ends this way.

abortState is strictly opt-in. The existing idiom — reserve an alphabet symbol and write an in-band error marker before halting — remains the right tool for most machines. Reach for abortState when in-band signaling doesn't fit: a 2-symbol machine has no alphabet symbol left to spare for "termination kind," or the final tape must stay a clean result (e.g. golden tests that diff tapes byte-for-byte).

import { Alphabet, State, Tape, TapeBlock, TuringMachine, abortState, haltState, ifOtherSymbol } from '@turing-machine-js/machine';

const alphabet = new Alphabet([' ', 'a', 'b']);
const tapeBlock = TapeBlock.fromTapes([new Tape({ alphabet, symbols: ['a'] })]);
const { symbol } = tapeBlock;

const cont = new State({ [ifOtherSymbol]: { nextState: haltState } }, 'cont');
const inner = new State({
  [symbol(['a'])]: { nextState: abortState },   // legal: abort as a transition TARGET
  [ifOtherSymbol]: { nextState: haltState },
}, 'inner');
const outer = inner.withOverriddenHaltState(cont);   // subroutine call: run inner, then cont

inner.withOverriddenHaltState(abortState);   // throws — abortState can't be a continuation
abortState.withOverriddenHaltState(inner);   // throws — abortState can't be overridden

Identity: abortState.id === -1, abortState.isAbort === true, abortState.isHalt === false; state.isSentinel (id <= 0) is true for both sentinels and false for every user state. abortState.debug is a boolean, mirroring haltState.debug — see §Debugging.

toMermaid(State.toGraph(outer, tapeBlock)) for the wrapped machine above:

flowchart TD
%% alphabets: [[" ","a","b"]]
  s1(((abort)))
  s0(((halt)))
  u1["cont"]
  u3[["inner(cont)"]]
  idle([idle])
  subgraph w_2["callable subtree of inner"]
    u2["inner"]
    s0-2(((halt)))
  end
  idle -. enter .-> u3
  u3 == "call" ==> u2
  w_2 -. "return" .-> u3
  u3 --> u1
  u1 -- "[*] → [K]/[S]" --> s0
  u2 -- "['a'] → [K]/[S]" --> s1
  u2 -- "[*] → [K]/[S]" --> s0-2
  classDef abortSentinel stroke:#c0392b,stroke-width:2px,stroke-dasharray:4 3
  class s1 abortSentinel

The solid u2 -- "['a'] → [K]/[S]" --> s1 edge is the abort punch-through: it leaves inner's callable-subtree subgraph (w_2) and lands straight on the global abortState node, bypassing the frame entirely — no marker, no dispatch. Contrast the frame's own dotted dispatch, w_2 -. "return" .-> u3: that one only fires when inner instead falls through to ifOtherSymbol, lands on the frame-local halt marker s0-2, and returns normally through the wrapper to cont.

RunResult

run() and runStepByStep() both return a call-scoped RunResult:

type RunResult = {
  outcome: 'halted' | 'aborted';
  state: State;              // the state whose transition triggered the sentinel
  stack: readonly State[];   // frozen; [] for 'halted' by construction
  step: number;              // 1-based iter count; 0 if initialState was itself a sentinel
};

• 'halted' implies stack === [], by construction, for a run that terminates NATURALLY — a haltState transition inside a subroutine pops and resumes; the run only reaches real halt once every pushed frame has already popped. No union type is needed to model the two natural outcomes because this invariant always holds for them.
• 'aborted': stack is the frozen backtrace of continuations abortState punched through — precisely the call-chain information an abort would otherwise discard. state is the triggering state, unwrapped to its bare if the transition fired from inside a withOverriddenHaltState wrapper (mirrors matchedTransition's same unwrap — see §Matched transition).
• External stop caveat: a run stopped externally — e.g. via generator.throw(haltState) on the runStepByStep generator — does NOT go through a natural halt/abort transition — it reports 'halted', but stack is whatever it stood at when the throw landed (not necessarily []) and state is the PREVIOUS iteration's state, not a sentinel-triggering one.
• Generator-return caveat: runStepByStep's generator carries the same object as its return value (visible in the final { done: true, value }) — but a plain for...of discards generator returns. The canonical step-level signal is the one runStepByStep always had: the last yielded MachineState's nextState === abortState.

// Continuing the cont/inner/outer example above:
const result = new TuringMachine({ tapeBlock }).run({ initialState: outer });
// head reads 'a' → inner's transition fires → abortState, punching straight through `cont`:
// { outcome: 'aborted', state: inner, stack: [cont], step: 1 }

Mermaid id scheme

Diagrams namespace node ids by prefix so a rendered graph reads user states, sentinels, and per-frame plumbing apart at a glance:

| Thing | Mermaid id | Was | |---|---|---| | user states | u{id} (u1, u2, …) | s{id} | | sentinels | s{ordinal} — halt s0, abort s1, a hypothetical 3rd sentinel s2, … | (halt was already s0) | | halt marker, frame f | s0-{f} — "frame-f-local stand-in for s0" | c{f} | | frame subgraphs | w_{f} | unchanged | | idle | idle | unchanged |

mermaidIdFor(id) / parseMermaidId(mermaidId) (both exported) implement the mapping and its inverse. Changelog one-liner: rendered-output churn only — the numeric Graph ids for user states and halt are unchanged; only the Mermaid string ids and the synthetic halt-marker's numeric id (-frameId → -2 * frameId, freeing the odd negatives for sentinels) moved.

ifOtherSymbol

A sentinel Symbol used as a key in a State definition to mean match any symbol not handled by the other keys (the fallback transition).

movements

Per-tape head movement directives passed in TapeCommand.movement:

• movements.left — move the head one cell left
• movements.right — move the head one cell right
• movements.stay — leave the head where it is

symbolCommands

Special values for TapeCommand.symbol:

• symbolCommands.keep — leave the current cell unchanged (default)
• symbolCommands.erase — write the alphabet's blank symbol

Introspection and testing

@turing-machine-js/machine ships two complementary runtime utilities:

summarize / summarizeGraph — structural analysis. Looks at the state graph without running it.

import { summarize } from '@turing-machine-js/machine';

const stats = summarize(myState, myTapeBlock);
// {
//   stateCount, transitionCount,
//   compositionEdgeCount, maxCompositionDepth,
//   selfLoopCount, hasCycles,
//   tapeCount, alphabetCardinalities,
// }

State.inspect(state) returns the same kind of data for a single state (transitions, override-halt target, etc.) without traversing the graph.

equivalentOn — behavioral comparison. Runs two machines on a list of test inputs and reports whether their outputs agree, where they first diverge, and how many steps each took.

import { equivalentOn } from '@turing-machine-js/machine';

const report = equivalentOn(
  { state: referenceState, getTapeBlock: () => referenceTapeBlock.clone() },
  { state: candidateState, getTapeBlock: () => candidateTapeBlock.clone() },
  ['^1$', '^10$', '^11$', '^111$'],   // test cases
);
// report.allAgree → true | false
// report.results[i] → { agree, referenceOutput, candidateOutput,
//                       referenceSteps, candidateSteps, firstDivergenceStep }

For different alphabets, pass { reference, candidate } paired cases plus a custom output comparator. See packages/machine/src/utilities/equivalence.spec.ts for worked examples.

Together: use summarize to ask "is this machine the right shape?" (size, composition, cycles), and equivalentOn to ask "does this machine compute the right thing?" (correctness against a reference). Useful when comparing two implementations of the same algorithm — e.g., the marker-based and bare binary libraries — or when grading student-written machines against a reference.

For visualization and round-tripping, see State.toGraph / State.fromGraph and toMermaid / fromMermaid.

Diagram conventions

The full reference for reading toMermaid output — shapes, edge styles, and the bracketed edge-label vocabulary. All shapes and arrows are standard Mermaid flowchart syntax; any Mermaid renderer (GitHub preview, IDE plugins, mermaid-js client-side) paints these diagrams the same way.

Node shapes

| Shape | Meaning | |---|---| | s0(((halt))) | the halt state | | uN["name"] | a regular state (or a bare, when inside a subgraph) | | uN[["composite-name"]] | a withOverriddenHaltState wrapper (call site; outside any subgraph when top-level, INSIDE its owner frame's subgraph when its continuation chain participates in a caller's frame — see §Subroutine composition and #223) | | s0-F(((halt))) inside a subgraph | frame F's halt marker (visualization aid; maps back to the singleton haltState at runtime) | | s1(((abort))) | the abortState sentinel — same terminal shape as halt, distinguished by a dashed-red classDef abortSentinel; emitted only when the graph actually references it (see §Sentinels: halt vs abort) | | idle([idle]) | pre-execution sentinel (not a real state) |

Node ids follow a namespaced scheme (u/s/s0-) — see §Mermaid id scheme for the full mapping and the mermaidIdFor / parseMermaidId helpers.

Edge styles

| Style | Where | Meaning | |---|---|---| | --> regular solid | between states; wrapper → override | plain transition / wrapper's post-return continuation | | ==> "call" thick solid | wrapper → bare | the wrapper's call into its callable subtree; reserved for wrapper-to-bare | | w_N -. "return" .-> dotted | subtree → wrapper | the subtree's halt-marker has incoming → control returns to the calling wrapper | | w_N -. "halt" .-> dotted | subtree → s0 | the subtree has a non-wrapper entry path → halt-marker can fire with empty stack (real halt) | | --> regular solid, crossing a subgraph boundary | any state (including in-frame) → s1 | abort punch-through: drawn straight to the global abortState node, deliberately in contrast with halt's frame-local s0-F marker + dotted dispatch — no per-frame retargeting, no abort marker | | idle -. enter .-> dotted | from idle to initial state | execution-start marker |

The & ribbon syntax (s_W1 & s_W2 == "call" ==> s_A) collapses multiple wrappers that share a bare into one arrow. Bold ==> is reserved exclusively for the wrapper-to-bare call arrow.

Groupings

subgraph w_N["callable subtree of NAME"] … end wraps a bare + its body + a halt marker — the callable scope of code that runs when a wrapper "calls" the bare. Multi-bare frames (union-find merged from shared body states) use the label "callable scope: A ∪ B".

Tags

Tagged states (via state.tag('hot', 'sampled') — see §State tags) render two ways simultaneously:

• Inline in the node label: uN["name<br>tag1, tag2"] — the <br> is Mermaid's universal line break, so the tags display as a second line under the state name in any renderer.
• As a color class: classDef tag_<sanitized> fill:#...,stroke:#... per unique tag (6-color palette selected by tag-name hash), plus class uN,uM tag_<sanitized> listing all nodes carrying the tag. Lets the eye group related states by color even when their names are scattered across the diagram.

The <br>-embedded label is the source of truth for fromMermaid round-trip; the classDef/class lines are decorative and regenerate on the next toMermaid emit. Tag-name sanitization in classDef identifiers: any char outside [A-Za-z0-9_-] is replaced with _. Labels preserve the raw tag names.

Edge label format

[reads] → [writes]/[moves]. Each bracketed list is a tape-block reading — one entry per tape; brackets always present, even single-tape.

| Glyph | Where | Meaning | |---|---|---| | 'X' | read, write | literal alphabet symbol (single-quoted) | | * | read only | ifOtherSymbol catch-all (ASCII *; a literal * in the alphabet renders as the quoted '*', so the marker stays unambiguous) | | B | read only | the tape's blank symbol (a literal B in the alphabet appears as 'B', so the marker stays unambiguous) | | K | write only | keep (no write) | | E | write only | erase (write the tape's blank) | | L / R / S | move only | left / right / stay |

Alternation rule

Alternative read patterns are always per-pattern-bracket:

• Single-tape: ['^']|['1']|['0']
• Multi-tape: ['0','a']|['1','b'] — "(tape 1='0' AND tape 2='a') OR (tape 1='1' AND tape 2='b')"

The compact in-bracket form ['^'|'1'] is rejected by fromMermaid — and never emitted by toMermaid. The reason is pedagogical: each alternative is its own drawn transition, and the compact form would read as cross-product semantics in multi-tape (['0'|'1','a'|'b'] could mean 4 combinations rather than 2 paired alternatives). One consistent rule across tape counts: each alternative is a full bracketed pattern.

Multi-tape example

A 2-tape "copier" machine — as long as tape 1 reads a non-blank, write the same symbol to tape 2 and step both right; halt when tape 1 reads blank:

flowchart TD
%% alphabets: [[" ","0","1"],[" ","0","1"]]
  s0(((halt)))
  u1["copy"]
  idle([idle])
  idle -. enter .-> u1
  u1 -- "['0',*] → [K,'0']/[R,R]" --> u1
  u1 -- "['1',*] → [K,'1']/[R,R]" --> u1
  u1 -- "[B,*] → [K]/[S]" --> s0

Reading ['0',*] → [K,'0']/[R,R]:

• Read ['0',*] — tape 1 must be literal '0'; tape 2 is ifOtherSymbol (any).
• Write [K,'0'] — tape 1: keep; tape 2: write literal '0'.
• Move [R,R] — both tapes step right.

Versioning notes

API surface changes since v3, in past tense so the timing of each piece is explicit:

• v4 — run() became async (Promise<void>). Per-state runtime breakpoints landed (state.debug.before / state.debug.after); run() accepted an onDebugBreak hook. MachineState exposed on each yield.

• v5 — onDebugBreak renamed to onPause. New run({ debug: boolean }) master switch suppresses all onPause dispatches without unsetting state.debug assignments. Assigning a truthy .after to haltState.debug now throws at write time (halt is terminal — no iteration-after-halt to anchor on). Superseded in v7 by #207: haltState.debug is now boolean, all object-shaped writes throw.

• v6 — Per-iter lifecycle reordered to before → step → after, all firing on the same yield. Previously after fired on iter K+1's tick with a prevYield substitution dance; that substitution is gone. (The MachineState.debugBreak field shape held through v6; v7 removes it — breakpoint detection moved into DebugSession, and the pause descriptor is now m.pause: {side, cause} on the pause event only.)

• v6.1 — state.debug ergonomics: the field is now always a non-null DebugConfig instance (lazy-initialized on first read), so chained field writes like state.debug.before = true work on a fresh state without a prior whole-object assignment. The DebugConfig instance is Object.seal-ed, so typos like state.debug.bofore = true throw TypeError at write time instead of silently creating a useless property. state.debug = null continues to work but semantically means "reset filters" — the next read returns a fresh empty DebugConfig (#150).

• v6.2 (superseded by v6.3.0) — widened onStep's signature to (m) => void | Promise<void> and added an inline await onStep(...) in the run loop, enabling throttle-in-onStep patterns. This overturned the docstring-stated contract that onStep is sync (microtask-free); the right place for per-iter throttling is onPause with self-rearm (see Throttle pattern). Restored in v6.3.0.

• v6.3 — onStep reverted to its v6.0–v6.1 sync contract — (m) => void, called synchronously inside the run loop. The Throttle pattern section documents the engine-native shape for per-iter throttle / "wait between iters" UIs. No other API changes.

• v6.4 — New onIter hook on run(): awaited, fires once at the end of every iter (after both onPause dispatches on the same yield), unaffected by the debug master switch. Use for per-iter throttle / animation / coordination needing a suspend point; complements the existing sync onStep (tracing) and conditional onPause (user breakpoints). Three-hook contract is now onStep (sync, mid-iter) / onPause (awaited, on state.debug match) / onIter (awaited, end-of-iter). Additive — peer-deps unchanged. The v6.3.0 README's onPause-rearm throttle workaround is superseded.

• v7 (2026-06-03) — Composition-representation overhaul + first-class state tags + id-keyed State.collectStates lookup + DebugSession step controls + CallFrame + tapeViewport/TapeSnapshot. Stable release on the latest dist-tag: npm install @turing-machine-js/machine. Highlights across the v7 alpha cycle:

  alpha.8 — TapeSnapshot type + tapeViewport helper (#227) moved into the engine from @turing-machine-js/visuals, next to the live Tape class (visuals re-exports for consumer-import stability). Tape.viewport getter refactored to share its centering loop with tapeViewport via an internal core — the centering math now lives once; the two public surfaces supply their own data-shape-appropriate cellAt lambdas. See §Tape.

  alpha.7 — CallFrame extraction (#213) — withOverriddenHaltState's wrapper is now a first-class CallFrame extends State subclass that delegates transition lookups + debug to its bare; instanceof State preserved (additive), instanceof CallFrame discriminates wrappers. Plus toMermaid framed-wrapper emit fix (#223) — toGraph's reach-set now tunnels through wrappers AND captures the wrappers themselves, so framed-wrapper-continuations (e.g. library-binary-numbers/minusOne's goToNumberStart(invertNumberGoToNumberWithInversion) inside invertNumber's callable subtree) render inside the owner subgraph rather than escaping to the top level. library-binary-numbers/states.md regenerated under the new emit.

  alpha.6 — Debugger step controls (#102) — full reshape of the debug surface. run() is now sync + callback-free; runStepByStep is the pure-iteration primitive (no state.debug filter evaluation); a new DebugSession class (new DebugSession(machine, {initialState})) owns all interactive debugging via pause / step / iter / halt events, depth-based stepIn / stepOver / stepOut, external pause() / stop() / setRunInterval(ms). Per-yield m.debugBreak: {before?, after?, cause} replaced by one-sided m.pause: {side, cause} on pause events only. See §Debugging.

  alpha.5 — Per-iter matchedTransition (#205) on every MachineState yield ({id, matchKinds}, id is ${stateId}.${ix} resolvable in toGraph). haltState.debug collapsed to a boolean (#207) — object-shaped writes throw; halt pause fires on the AFTER side of the halt-triggering iter with m.state = the triggering state. HaltState typed alias narrows debug to boolean at the canonical access path.

  alpha.4 — State.collectStates(initial, tapeBlock) (#195) returns a Map<number, {state, transitionSymbols}> keyed by GraphNode.id so downstream tooling can mutate state.debug by numeric id and set per-pattern breakpoints by GraphTransition.id. Graph serialization extracted to utilities/stateGraph.ts with a Symbol-keyed @internal accessor on State (#180; no public-API change — the State.toGraph / .fromGraph statics remain as thin delegates). Two upstream fixes: toMermaid HTML-entity-escapes user content in labels so alphabets containing ", <, etc. parse correctly (#194); runStepByStep's halt stack is now run-scoped, fixing a memory leak / ghost-iteration when the same TuringMachine instance is reused across calls ([#196](https://g