Skip to content

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.

Version
v1 · 2026-09-28 · History
Domain-specific #
12840
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Computability Theory, Models of Computation → Computer Science & Software Engineering

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.

Structural Signature

Sig role-phrases:

  • Unbounded marked tape — Stores blank or marked cells available to the computation. It is memory. Counterfactual: A fixed finite tape changes computational capacity.
  • Scanning head — Selects exactly one cell for reading, marking, and relative motion. It is state. Counterfactual: Random access would define a different machine model.
  • Left and right moves — Shift the scanned position by one cell. It is instructions. Counterfactual: No-move addressing is not part of the basic four primitives.
  • Mark instruction — Changes a blank scanned cell to marked and proceeds sequentially. It is instruction. Counterfactual: The B-machine cannot directly erase a mark.
  • Conditional transfer Cn — Jumps to instruction n on a mark and otherwise falls through. It is control. Counterfactual: An unconditional branch must be constructed from program context.
  • Finite numbered program — Orders instructions and defines halting by exiting or lacking a next step under the convention. It is program. Counterfactual: Tape contents alone do not determine computation without instruction state.

What It Is Not

  • 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.
  • Closest near-miss. The W-machine is the B-machine plus an erase instruction; this convenience changes the primitive instruction set even though both remain Turing-equivalent.

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.

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

  1. Encode data and simulated state on the marked tape and instruction counter.
  2. Read the scanned cell through conditional transfer.
  3. Mark blank cells when the encoding requires it.
  4. Move one square left or right.
  5. Compose instruction blocks simulating each source-machine transition.
  6. 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.

Examples

Applied / In Practice

A short instruction list marks the current square, moves right across marked cells using conditional jumps, then changes direction through the numbered control flow.

Mapped back: tape → binary; operations → mark, move, conditional jump.

Applied / In Practice

A Turing transition is represented by a finite block of B instructions that tests the scanned mark, encodes state in instruction position, marks as needed, and moves the head.

Mapped back: source → Turing step; target → B program block.

Applied / In Practice

A machine executes E to erase a scanned mark as one primitive; under Wang's terminology it is a W-machine, not the basic B-machine.

Mapped back: erase → primitive; classification → W-machine.

Structural Tensions

T1 — Minimal Primitives versus Simulation Overhead. A tiny instruction set clarifies computability while expanding programs that simulate richer machines.

Diagnostic: Which coding proves equivalence and what overhead does it incur?

T2 — Write-Only Mark versus Reversible Data Reuse. No erase seems restrictive, yet control and fresh tape can encode arbitrary computation.

Diagnostic: How does the simulation represent changes that appear to require deletion?

T3 — Sequential Program versus Branching Behavior. Most instructions fall through while conditional transfer supplies all nontrivial control.

Diagnostic: Where is machine state encoded?

Structural–Framed Character

Wang B-Machine is hybrid: structurally a transition system and framed by classical computability, tape conventions, and instruction-set history.

Structural Core vs. Domain Accent

The core is local memory inspection plus update, motion, and conditional control. Computability supplies unbounded tape, mark/blank alphabet, program counter, simulation, universality, Turing equivalence, Post machines, and erasure variants.

  • Approved root. Random-Access Machine and B-Method are lexical or computational neighbors, not genera; the frozen root is retained.

  • Related — Turing machine, Post–Turing machine, register machine, Wang W-machine, universal machine, and tag system. These provide equivalence targets and variants.

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

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Wang W-Machine. Tell: The W-machine adds a primitive erase instruction to the B-machine.
  • Wang Tile. Tell: Wang tiles form a geometric tiling system and share only the researcher's name.
  • Random-Access Machine. Tell: A RAM addresses registers directly rather than moving a local tape head.
  • B-Method. Tell: The B-Method is a formal software-development notation unrelated to Wang's machine B.

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Wang_B-machine (revision 1331045470).

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.