@turing-machine-js/library-binary-numbers-bare

Single-number binary arithmetic on a 3-symbol alphabet (blank, 0, 1) — same operations as @turing-machine-js/library-binary-numbers but without ^/$ start/end markers. Side-by-side with the marker-based library so the trade-off between alphabet size and state-graph size is visible.

Install

npm install @turing-machine-js/machine @turing-machine-js/library-binary-numbers-bare

@turing-machine-js/machine is a peer dependency.

Concept

A number is a contiguous run of 0/1 cells. Blanks surround it on both sides. There are no explicit boundary markers — the first/last digit is detected by walking until the next blank cell.

…blank 101011 blank 110010 blank…
       ╰─43─╯       ╰─50─╯

All algorithms in this library assume the head starts at the leftmost digit of the number.

Algorithms

| name | what it does | |---|---| | plusOne | adds 1 to the number; extends leftward on overflow (111 + 1 = 1000) | | minusOne | subtracts 1; leaves leading zeros if the borrow chain hits the MSB (1000 − 1 = 0111) | | invertNumber | flips every bit (0 ↔ 1) | | normalizeNumber | erases leading zeros; preserves a single 0 for the value zero |

Usage

import { Tape, TuringMachine } from '@turing-machine-js/machine';
import binaryNumbersBare from '@turing-machine-js/library-binary-numbers-bare';

const tapeBlock = binaryNumbersBare.getTapeBlock();
const tape = new Tape({
  alphabet: tapeBlock.alphabets[0],
  symbols: '101'.split(''), // binary 5
});

tapeBlock.replaceTape(tape);

const machine = new TuringMachine({ tapeBlock });

await machine.run({ initialState: binaryNumbersBare.states.plusOne });

console.log(tape.symbols.join('').trim()); // "110" (binary 6)

To run several algorithms in sequence on the same value, reuse the same TapeBlock across machine.run(...) calls.

How it compares to the marker-based library

Both libraries solve the same problem; the trade is alphabet symbols vs state-graph size.

| algorithm | this library (3-symbol) | marker-based library (5-symbol) | |---|---|---| | plusOne | 3 states | 5 states | | minusOne | 3 states | 17 / 10 (minusOne / minusOneFast) | | invertNumber | 2 states | 5 states | | normalizeNumber | 2 states | 7 states | | multi-number on tape? | no | yes — goToNumber, goToNextNumber, etc. | | head-position flexibility | leftmost digit | anywhere on the number | | minusOne auto-normalizes? | no — leading 0 kept | yes — minusOneFast chains into normalizeNumber |

The marker library's extra states are mostly bookkeeping for the ^/$ markers (planting ^ on left-overflow, sweeping past it on entry, etc.). Drop the markers and most of that disappears — but you also lose the ability to put several numbers on one tape, which is what the marker library's goToNumber / goToNextNumber family is for.

For a teaching context, both libraries shipping in parallel makes the cost of representation choices tangible.

See the rendered Mermaid graphs for every state in states.md (regenerated via npm run docs:states from the repo root; the spec at src/graphs.spec.ts only verifies structural properties of the graphs, not the markdown file).

Links

• @turing-machine-js/machine — the core engine
• @turing-machine-js/library-binary-numbers — the marker-based counterpart
• Turing Machine on Wikipedia