Turing Machines and LBA

Turing Machines & LBA

Turing machines (TM) and linear‑bounded automata (LBA) sit at the top of what AutomataLab models. They read and write a tape and move a head, recognising the recursively enumerable (TM) and context‑sensitive (LBA) languages.

Transitions: read → write, direction

A TM/LBA move matches the single tape symbol under the head, overwrites it, then moves the head:

Field	Meaning
read	The tape symbol under the head this move matches (empty/blank matches a blank cell).
write	The symbol written under the head before moving (empty/blank writes a blank).
direction	Head move after writing: L (left), R (right), or S (stay).

Edit these in the transition editor's read → write, dir row with an L/R/S selector.

The tape

• The input is loaded into cells 0 … n‑1; every other cell holds the blank symbol (default _, configurable in the toolbar). The head starts on cell 0.
• A TM tape is two‑way infinite — the head may move arbitrarily far left or right.
• The Tape panel shows a live head (▲), the current state, the instantaneous description (α q β), boundary markers for LBAs, and a faded arrow marking the head's last move. It even previews your input live while idle, mirroring the input box as you type.
• For performance, the panel renders a bounded moving window around the head, so a head that travels far never materialises a giant cell array. See Simulation.

Acceptance, rejection, and the loop guard

• Accept by halting in an accept state — the input need not be consumed and the head can be anywhere.
• Reject when the machine enters an explicit reject state, or when no transition applies from a non‑accept state. Mark a reject state via right‑click; it renders with a red double‑ring and is mutually exclusive with accept.
• stuck — if a run exceeds the configurable step limit (default 10000), it halts as stuck and a toast points you at the adjustable limit. This is the infinite‑loop guard.

Multi‑tape Turing machines

Set the toolbar TAPES count to N > 1 to give a TM several tapes in parallel:

• Each transition carries arrays of length N: reads, writes, directions (one entry per tape), edited as a → b, R | _ → c, L.
• A move fires only when every tape's read matches; it then writes and moves each head simultaneously.
• The input seeds tape 1 only; all other tapes start blank. The Tape panel shows one row per tape.
• Determinism is checked on the full read‑tuple (reads[0], …, reads[N‑1]) per state. Multi‑tape is a plain‑TM feature — an LBA stays single‑tape.

LBA — Linear‑Bounded Automaton

An LBA is a TM whose head is confined to the input region [0, n] (the input cells plus the trailing end‑of‑input blank), bracketed by ⊢ / ⊣ markers on the tape:

• A move that would step the head past either end halts and rejects.
• Empty input still gets one usable cell, so the head can read the blank and decide.
• This bounded space is exactly what makes the LBA recognise the context‑sensitive languages (e.g. aⁿbⁿcⁿ).

Declared tape alphabet (Γ)

Optionally declare the tape alphabet Γ in the toolbar (TAPE (Γ)); it should include the blank and satisfy Σ ⊆ Γ. Like the PDA stack alphabet it is declarative, driving non‑blocking validation warnings (e.g. a written symbol outside Γ, or the blank appearing in Σ). See Validation & Alphabets.

For the JSON schema and worked 0ⁿ1ⁿ (TM), aⁿbⁿcⁿ (LBA), and 2‑tape aⁿbⁿ examples, see File Format.