Proposal: cycle-detection utility on top of onIter (signature-set + Brent's)

[mellonis]

Motivation

Turing machines that don't halt either loop or wander forever. The engine catches the latter via `stepsLimit` / `WORKER_TIMEOUT_MS` but has no built-in cycle detection beyond the machine's own halting — a 5-state loop will burn through `MAX_STEPS` before the engine notices.

With `onIter` from v6.4.0, a user-land cycle-detection utility is straightforward to build. This issue proposes its shape and asks whether to ship it as a package or leave it as a documented snippet.

Shape — pluggable algorithm via factory

```ts
import {
TuringMachine,
type MachineState,
type TapeBlock,
} from '@turing-machine-js/machine';

// ===== Pluggable algorithm interface =====

export interface CycleDetectionAlgo {
/** Create fresh per-run state. The returned callback is invoked per

• iter and throws on a positive detection. */
  create(tapeBlock: TapeBlock): (m: MachineState) => void;
  }

// ===== Typed errors =====

export class CycleDetectedError extends Error {
constructor(public readonly step: number, public readonly stateName: string) {
super(Cycle detected at step ${step}, state ${stateName});
this.name = 'CycleDetectedError';
}
}

export class TooManyConfigsError extends Error {
constructor(public readonly seenCount: number) {
super(Too many unique configurations (${seenCount}));
this.name = 'TooManyConfigsError';
}
}

// ===== Wrapper =====

export function withCycleDetection(
machine: TuringMachine,
algo: CycleDetectionAlgo,
): TuringMachine {
const originalRun = machine.run.bind(machine);
// Note: mutates machine.run in place. Wrap once at construction time;
// don't re-wrap. Documented in the JSDoc.
machine.run = async (config = {}) => {
const detect = algo.create(machine.tapeBlock);
const userOnIter = config.onIter;
return originalRun({
...config,
onIter: async (m) => {
detect(m); // throws on cycle / too-many
if (userOnIter) await userOnIter(m); // compose with user's onIter
},
});
};
return machine;
}

// ===== Algorithm 1: signature set =====

/** Hash full machine configuration each iter; throw when a hash repeats.

• O(n) memory bounded by maxUniqueConfigs. Correct: identical configs in
• a deterministic machine guarantee identical trajectory thereafter. */
  export function bySignatureSet(opts: { maxUniqueConfigs?: number } = {}): CycleDetectionAlgo {
  const maxUniqueConfigs = opts.maxUniqueConfigs ?? 50_000;
  return {
  create(tapeBlock) {
  const seen = new Set();
  return (m) => {
  const sig = signatureOf(m, tapeBlock);
  if (seen.has(sig)) {
  throw new CycleDetectedError(m.step, m.state.name ?? String(m.state.id));
  }
  seen.add(sig);
  if (maxUniqueConfigs > 0 && seen.size > maxUniqueConfigs) {
  throw new TooManyConfigsError(seen.size);
  }
  };
  },
  };
  }

// ===== Algorithm 2: Brent's algorithm (O(1) memory) =====

/** Brent's algorithm: snapshot at power-of-2 step indices, compare current

• against the snapshot every iter, double the snapshot interval when no
• match found. Detects cycles with O(1) extra memory + finds cycle
• length. Useful for very long runs where signature-set's O(n) memory
• is a concern. */
  export function byBrent(): CycleDetectionAlgo {
  return {
  create(tapeBlock) {
  let snapshotSig: string | null = null;
  let power = 1; // next power-of-2 to snapshot at
  let lam = 1; // step count since last snapshot
  return (m) => {
  const sig = signatureOf(m, tapeBlock);
  if (snapshotSig === sig) {
  throw new CycleDetectedError(m.step, m.state.name ?? String(m.state.id));
  }
  if (lam === power) {
  snapshotSig = sig;
  power *= 2;
  lam = 0;
  }
  lam += 1;
  };
  },
  };
  }

// ===== Configuration signature =====

function signatureOf(m: MachineState, tapeBlock: TapeBlock): string {
const stateName = m.state.name ?? String(m.state.id);
const tapes = tapeBlock.tapes
.map((t, i) => T${i}[${t.position}]:${t.symbols.join('')})
.join('|');
return ${stateName}|${tapes};
}
```

Usage

```ts
import { TuringMachine, TapeBlock, Tape, Alphabet } from '@turing-machine-js/machine';

const alphabet = new Alphabet([' ', '0', '1']);
const tape = new Tape({ alphabet, symbols: ['1', '0', '1', '1'] });
const tapeBlock = TapeBlock.fromTapes([tape]);

const machine = withCycleDetection(
new TuringMachine({ tapeBlock }),
bySignatureSet({ maxUniqueConfigs: 30_000 }),
);

try {
await machine.run({ initialState });
console.log('halted');
} catch (e) {
if (e instanceof CycleDetectedError) {
console.error(Cycle at step ${e.step}, state ${e.stateName});
} else if (e instanceof TooManyConfigsError) {
console.warn(Visited ${e.seenCount} unique configs without detecting cycle);
} else throw e;
}
```

Three things to call out vs. the original sketch

1. Engine field names. `m.state` (not `m.currentState`), `m.state.name` / `m.state.id`, `tape.position` (not `tape.getPosition()`), `tape.symbols` (not `tape.getViewport(60)`).
2. No `onTooManyConfigs` callback — typed error is enough; caller `instanceof`-checks. Same for `onCycleDetected`.
3. Brent's algorithm instead of a Tortoise-Hare sketch. Floyd's TH needs two pointers advancing at different speeds over the same sequence — hard to do inside a single per-iter callback. Brent's variant snapshots at power-of-2 step indices, compares current against the snapshot every iter — fits the `onIter` shape directly. Same O(1) memory win.

Open questions

Where does this live?

• A. New published package: `@turing-machine-js/cycle-detection` alongside `library-binary-numbers` / `library-binary-numbers-bare`. Lockstep version. Discoverable. Article-aligned (utility on top of engine, doesn't grow engine API).
• B. User-land snippet in the README's "Engine quirks" section, with the `signatureOf` + algos as copy-pasteable code. Cheaper but less discoverable.
• C. Demo-only — `machines-demo` Toolbar adds a "Detect cycles" checkbox that wraps the user's machine with `bySignatureSet`. Demo gets a teachable feature; no published utility.

Signature granularity

`signatureOf` snapshots state name + all tape contents + all head positions — that's the full configuration of a deterministic Turing machine. Two identical configs guarantee identical trajectories thereafter. But `tape.symbols` may be very long for tapes that wander far; the signature scales with tape width × number of tapes per iter. For machines that work on small tapes this is fine; for ones with millions of cells, signature cost dominates.

Possible improvement: snapshot only the relevant window (cells between leftmost-touched and rightmost-touched indices). The engine doesn't track this directly; the wrapper would have to.

Composition with user's `onIter`

The wrapper chains: `detect(m)` first, then `await userOnIter(m)`. If `detect` throws, user's callback doesn't fire for that iter. Caller learns via the rejected `run()` Promise. Is that the right order? Or should user's callback fire first (so e.g. a debugger UI shows the just-arrived iter before the cycle exception)?

Mutation in place

`withCycleDetection(machine, algo)` mutates `machine.run` in place and returns the same instance. Convenient but surprising for callers who pass the machine around — every consumer sees the wrapped run after the call. Alternatives:

• Return a new object: `{ ...machine, run: wrappedRun }` — loses `instanceof TuringMachine`.
• Subclass: `class CycleDetectingTuringMachine extends TuringMachine` — class identity preserved, but the per-machine wrap-once decision lives in the constructor.
• Pure function: `runWithCycleDetection(machine, algo, config)` — caller passes the machine and config; we run via the original `run` plus the detector. No mutation, but call-site is verbose.

Probably the pure-function shape is cleanest. The factory-style `withCycleDetection` reads better at the call site but the mutation is a real footgun.

Not in scope

• Cycle detection for non-deterministic machines (engine is deterministic by construction; no need).
• Detecting eventually-periodic trajectories (the trajectory enters a cycle after a non-cycling prefix). Both algorithms above handle this — Brent's finds the cycle's start step + length; signature-set just throws on the first repeat.
• Engine-side changes. This is a wrapper. The engine stays minimal.

Appendix: original sketches with field-name corrections

For reference — the two functions that prompted this proposal, rewritten with the engine's actual field names (m.state.name / m.state.id not currentState; tape.position / tape.symbols not getPosition() / getViewport(60)). Both also need machine.tapeBlock access (the per-iter MachineState doesn't carry the tape block) — passed in as the closure-captured tapeBlock.

import { TuringMachine, type MachineState, type TapeBlock } from '@turing-machine-js/machine';

export interface CycleDetectionOptions {
  maxUniqueConfigs?: number;     // 0 = unlimited
  maxSteps?: number;
  onCycleDetected?: (info: { steps: number; state: string; tape: string }) => void;
  onTooManyConfigs?: (steps: number) => void;
}

/** Wraps a TuringMachine with cycle detection (signature-set algorithm). */
export function withCycleDetection(
  machine: TuringMachine,
  options: CycleDetectionOptions = {},
) {
  const {
    maxUniqueConfigs = 50_000,
    maxSteps = 100_000,
    onCycleDetected,
    onTooManyConfigs,
  } = options;

  const tapeBlock: TapeBlock = machine.tapeBlock;
  const seen = new Set<string>();
  let steps = 0;

  function createSignature(m: MachineState): string {
    const stateName = m.state.name ?? String(m.state.id);
    const tapesInfo = tapeBlock.tapes
      .map((tape, i) => `T${i}[${tape.position}]:${tape.symbols.join('')}`)
      .join('|');
    return `${stateName}|${tapesInfo}`;
  }

  const originalRun = machine.run.bind(machine);
  machine.run = async (config = {}) => originalRun({
    ...config,
    stepsLimit: maxSteps,
    onIter: async (m: MachineState) => {
      steps++;
      const signature = createSignature(m);
      if (seen.has(signature)) {
        onCycleDetected?.({
          steps,
          state: m.state.name ?? String(m.state.id),
          tape: tapeBlock.tapes.map((t) => t.symbols.join('')).join('|'),
        });
        throw new Error(`Cycle detected after ${steps} steps`);
      }
      seen.add(signature);
      if (maxUniqueConfigs > 0 && seen.size > maxUniqueConfigs) {
        onTooManyConfigs?.(steps);
        throw new Error(`Too many unique configurations (${seen.size})`);
      }
      if (config.onIter) await config.onIter(m);
    },
  });

  return machine;
}

/** Brent's algorithm replaces the Tortoise-Hare sketch from the original
 *  draft. Floyd's TH needs two pointers advancing at different speeds over
 *  the same sequence, which doesn't fit a single per-iter callback — Brent's
 *  variant (snapshot at power-of-2 step indices, compare current against
 *  the snapshot every iter, double the snapshot interval when no match) is
 *  the on-iter-friendly cycle finder with the same O(1) memory win. */
export function withBrentCycleDetection(
  machine: TuringMachine,
  options: { onCycleDetected?: () => void } = {},
) {
  const { onCycleDetected } = options;
  const tapeBlock: TapeBlock = machine.tapeBlock;

  let snapshotSig: string | null = null;
  let power = 1;
  let lam = 1;
  let steps = 0;

  function sigOf(m: MachineState): string {
    const stateName = m.state.name ?? String(m.state.id);
    const tapesInfo = tapeBlock.tapes
      .map((t, i) => `T${i}[${t.position}]:${t.symbols.join('')}`)
      .join('|');
    return `${stateName}|${tapesInfo}`;
  }

  const originalRun = machine.run.bind(machine);
  machine.run = async (config = {}) => originalRun({
    ...config,
    onIter: async (m: MachineState) => {
      steps++;
      const sig = sigOf(m);
      if (snapshotSig === sig) {
        onCycleDetected?.();
        throw new Error(`Cycle detected by Brent at step ${steps}`);
      }
      if (lam === power) {
        snapshotSig = sig;
        power *= 2;
        lam = 0;
      }
      lam += 1;
      if (config.onIter) await config.onIter(m);
    },
  });

  return machine;
}

Key field-name corrections from the original sketches:

• ms.currentState → m.state
• ms.currentState.name || ms.currentState.id → m.state.name ?? String(m.state.id) (name may be undefined; id is always a number)
• tape.getPosition?.() → tape.position (it's a getter, not a method)
• tape.getViewport?.(60) → tape.symbols.join('') (no getViewport method; symbols is the underlying array)
• ms.tapeBlock.tapes → use machine.tapeBlock.tapes (the per-iter MachineState does NOT carry tapeBlock; capture it from the wrapped machine instead)
• ms.tapeBlock.toString() → manually join symbols (no toString on TapeBlock)

These two are the inline-mutation variants (each call wraps the machine in place). The proposal above factors them into the pluggable withCycleDetection(machine, algo) shape; see "Open questions → Mutation in place" for the trade-off discussion.