Wang B-machine¶
A four-instruction, mark-only sequential tape machine—left, right, mark, and conditional jump—that retains Turing-complete computational power without a primitive erase operation.
Core Idea¶
The B-machine combines an unbounded tape of blank or marked squares with a scanning head and a finite numbered program. Movement and marking fall through to the next instruction; a conditional transfer branches to a named instruction only when the scanned square is marked.
Its importance is representational economy. Direct erasure and richer Turing-state transitions are absent, yet appropriate encodings simulate a Turing machine. The W-machine is a nearby variant obtained by adding erase, so instruction-set fidelity matters when naming an implementation.
Scope of Application¶
- Computability theory. Shows Turing equivalence with unusually sparse primitives.
- Machine-model comparison. Studies how state and operations are encoded across formalisms.
- Universal computation. Supports constructions of interpreters and universal programs.
- Minimal instruction sets. Separates convenience of primitives from computability power.
- History of computer models. Connects Turing and Post formalisms to computer-like sequential instructions.
Clarity¶
State tape extent and alphabet, initial configuration, head position, numbered program, exact fall-through and jump semantics, halting convention, and whether erase is primitive. Demonstrate equivalence through an explicit simulation rather than the word universal alone. Inclusion test: Require the B-machine's binary tape, single head, finite numbered program, sequential fall-through, four exact primitives, and simulation semantics sufficient for Turing equivalence. Exclusion test: Exclude the W-machine with erase, Post–Turing machines with broader instruction sets, Wang tiles, random-access machines, and any informal register program sharing only the letter B. Nearest boundary: The W-machine is the B-machine plus an erase instruction; this convenience changes the primitive instruction set even though both remain Turing-equivalent. Exit condition: The identity changes when direct erase or random access is admitted as a basic operation. Common misclassifications: It is not Wang tile computation. It is not the W-machine with a primitive erase. It is not a random-access machine. It is not the B-Method for software specification. Nearest named distinctions: Wang W-Machine: The W-machine adds a primitive erase instruction to the B-machine. Wang Tile: Wang tiles form a geometric tiling system and share only the researcher's name. Random-Access Machine: A RAM addresses registers directly rather than moving a local tape head. B-Method: The B-Method is a formal software-development notation unrelated to Wang's machine B.
Manages Complexity¶
The abstraction isolates three resources—unbounded binary memory, local head motion, and conditional control—and shows they suffice despite a mark-only update. It makes hidden state encodings visible and supports exact comparison of instruction-set economy.
Abstract Reasoning¶
- Encode data and simulated state on the marked tape and instruction counter.
- Read the scanned cell through conditional transfer.
- Mark blank cells when the encoding requires it.
- Move one square left or right.
- Compose instruction blocks simulating each source-machine transition.
- Verify halting and output correspondence under the declared coding.
Knowledge Transfer¶
The transferable cargo is universality under a severely restricted local instruction set. It transfers to other machine models through proven simulations; it stops at assuming all simple-looking tape systems are equivalent without encoding and halting arguments.
Neighborhood in Abstraction Space¶
Wang B-machine sits in a moderately populated region (51st percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Digital Logic & Finite-State Machines (10 abstractions)
Nearest neighbors
- Klecksography — 0.87
- Memory Organisation — 0.86
- Moore machine — 0.86
- Switching circuit theory — 0.86
- Generalized Büchi Automaton — 0.85
Computed from structural-signature embeddings · 2026-10-08