turing machine
A simulator for a real Turing machine — an unbounded tape, a read/write head, and a handful of states — running four small preset programs.
Scans right to find the end of the number, then carries leftward through the 1s the way you would by hand.
the model
A Turing machine is barely more than the NFA from the regex visualizer: a set of states and a transition table, same as before. The difference is what it has to work with. An NFA's entire memory is which handful of states are currently lit up — that's it, nothing else persists between input characters. A Turing machine gets a tape it can read, write, and move along in either direction, and that tape is exactly as long as it needs to be. The entire machine is one function,
read as: given the current state and the symbol under the head, produce a new state, a symbol to write, and a direction to move. The program table above is exactly this , written out row by row. Unbounded memory is the whole story: it's the difference between a machine that can only recognize patterns and one that can actually compute. Alan Turing introduced the model in 1936, not as a design for a physical device but as a way to pin down what "computable" could even mean.
counting with the tape
The aⁿbⁿ preset is a direct callback to that earlier page, which explained why no NFA can recognize strings like "aabb" or "aaabbb" — doing that requires counting how many a's showed up before checking that the same number of b's follow, and an NFA has nowhere to put a running count. A Turing machine does: this preset crosses off one a and one matching b per pass, using the tape itself as the counter, and only accepts if both sides run out at exactly the same time.
busy beaver
The busy beaver preset is a different kind of demonstration. There's no algorithm that can look at an arbitrary Turing machine and say in advance whether it will ever halt — that's the halting problem, and it is undecidable in general. The undecidability result is Turing's, from that same paper, though he framed it in terms of machines that print an infinite sequence; the name and the now-standard phrasing came along later, in the 1950s. The busy beaver game, introduced by Tibor Radó in his 1962 paper On Non-Computable Functions, turns that fact into a concrete puzzle: among all machines with n states that do halt starting from a blank tape, which one writes the most 1s? For small enough n you can simply try every machine, and the included 3-state, 2-symbol winner was found by brute-force simulating roughly a million candidates and keeping the one that writes six 1s before stopping.
The catch is that this stops working almost immediately. The busy beaver function grows faster than any computable function — that was Radó's actual result, and it means no program can ever calculate it in general. Values are known only for n up to 5, and that last one took decades: Heiner Marxen and Jürgen Buntrock found the winning 5-state machine in 1990, but proving that no other 5-state machine beats its 47,176,870 steps was not finished until a collaborative, machine-checked effort settled it in 2024. Six states is already out of reach, with the best known candidates running for numbers of steps too large to write down conventionally. It's a real answer to "how much can a machine this small actually do," and you cannot get that answer any way other than checking.
the other model
The other model of computation proposed in the same decade took a completely different route to the same place — no tape, no states, nothing but functions. That's the lambda reducer, and the fact that the two turn out to be exactly equivalent in power is the Church–Turing thesis.
view source
import { useEffect, useMemo, useRef, useState } from 'react';
type Move = 'L' | 'R' | 'S';
type NextState = string | 'HALT' | 'ACCEPT' | 'REJECT';
interface Transition {
write: string;
move: Move;
next: NextState;
}
type Rules = Record<string, Record<string, Transition>>;
interface Program {
id: string;
label: string;
blank: string;
startState: string;
rules: Rules;
defaultTape: string;
blurb: string;
}
type Status = 'running' | 'halted' | 'accepted' | 'rejected';
interface MachineState {
tape: Record<number, string>;
head: number;
state: string;
steps: number;
status: Status;
}
const PROGRAMS: Program[] = [
{
id: 'inc',
label: 'binary +1',
blank: '_',
startState: 'right',
defaultTape: '1011',
blurb:
'Scans right to find the end of the number, then carries leftward through the 1s the way you would by hand.',
rules: {
right: {
'0': { write: '0', move: 'R', next: 'right' },
'1': { write: '1', move: 'R', next: 'right' },
_: { write: '_', move: 'L', next: 'carry' },
},
carry: {
'1': { write: '0', move: 'L', next: 'carry' },
'0': { write: '1', move: 'S', next: 'HALT' },
_: { write: '1', move: 'S', next: 'HALT' },
},
},
},
{
id: 'add',
label: 'unary add',
blank: '_',
startState: 'seekPlus',
defaultTape: '111+11',
blurb:
'Turns "m 1s + n 1s" into one run of m+n+1 1s by replacing the + with a 1, then erases the last 1 to correct for it.',
rules: {
seekPlus: {
'1': { write: '1', move: 'R', next: 'seekPlus' },
'+': { write: '1', move: 'R', next: 'seekEnd' },
},
seekEnd: {
'1': { write: '1', move: 'R', next: 'seekEnd' },
_: { write: '_', move: 'L', next: 'erase' },
},
erase: {
'1': { write: '_', move: 'S', next: 'HALT' },
},
},
},
{
id: 'anbn',
label: 'aⁿbⁿ',
blank: '_',
startState: 'start',
defaultTape: 'aaabbb',
blurb:
'Repeatedly crosses off one a and the next unmatched b, then rewinds -- accepts only if both run out at exactly the same time.',
rules: {
start: {
X: { write: 'X', move: 'R', next: 'start' },
a: { write: 'X', move: 'R', next: 'findB' },
Y: { write: 'Y', move: 'R', next: 'checkNoMoreA' },
b: { write: 'b', move: 'S', next: 'REJECT' },
_: { write: '_', move: 'S', next: 'ACCEPT' },
},
findB: {
a: { write: 'a', move: 'R', next: 'findB' },
X: { write: 'X', move: 'R', next: 'findB' },
Y: { write: 'Y', move: 'R', next: 'findB' },
b: { write: 'Y', move: 'L', next: 'returnLeft' },
_: { write: '_', move: 'S', next: 'REJECT' },
},
returnLeft: {
X: { write: 'X', move: 'L', next: 'returnLeft' },
a: { write: 'a', move: 'L', next: 'returnLeft' },
Y: { write: 'Y', move: 'L', next: 'returnLeft' },
b: { write: 'b', move: 'L', next: 'returnLeft' },
_: { write: '_', move: 'R', next: 'start' },
},
checkNoMoreA: {
Y: { write: 'Y', move: 'R', next: 'checkNoMoreA' },
_: { write: '_', move: 'S', next: 'ACCEPT' },
a: { write: 'a', move: 'S', next: 'REJECT' },
X: { write: 'X', move: 'S', next: 'REJECT' },
b: { write: 'b', move: 'S', next: 'REJECT' },
},
},
},
{
id: 'bb3',
label: 'busy beaver',
blank: '0',
startState: 'A',
defaultTape: '',
blurb:
'The 3-state, 2-symbol machine that writes the most possible 1s (six) before halting, starting from a completely blank tape.',
rules: {
A: {
'0': { write: '1', move: 'R', next: 'B' },
'1': { write: '1', move: 'L', next: 'C' },
},
B: {
'0': { write: '1', move: 'L', next: 'A' },
'1': { write: '1', move: 'R', next: 'B' },
},
C: {
'0': { write: '1', move: 'L', next: 'B' },
'1': { write: '1', move: 'L', next: 'HALT' },
},
},
},
];
function initMachine(program: Program, tapeStr: string): MachineState {
const tape: Record<number, string> = {};
for (let i = 0; i < tapeStr.length; i++) {
if (tapeStr[i] !== program.blank) tape[i] = tapeStr[i];
}
return {
tape,
head: 0,
state: program.startState,
steps: 0,
status: 'running',
};
}
function stepMachine(program: Program, m: MachineState): MachineState {
if (m.status !== 'running') return m;
const symbol = m.tape[m.head] ?? program.blank;
const transition = program.rules[m.state]?.[symbol];
if (!transition) return { ...m, status: 'halted' };
const newTape = { ...m.tape, [m.head]: transition.write };
const newHead =
transition.move === 'L'
? m.head - 1
: transition.move === 'R'
? m.head + 1
: m.head;
const status: Status =
transition.next === 'HALT'
? 'halted'
: transition.next === 'ACCEPT'
? 'accepted'
: transition.next === 'REJECT'
? 'rejected'
: 'running';
return {
tape: newTape,
head: newHead,
state: transition.next,
steps: m.steps + 1,
status,
};
}
const STATUS_LABEL: Record<Status, string> = {
running: 'running',
halted: 'halted',
accepted: 'accepted',
rejected: 'rejected',
};
const PAD = 3;
interface Props {
initialProgram?: string;
}
export default function TuringMachine({ initialProgram = 'inc' }: Props) {
const initial = PROGRAMS.find((p) => p.id === initialProgram) ?? PROGRAMS[0];
const [programId, setProgramId] = useState(initial.id);
const [tapeInput, setTapeInput] = useState(initial.defaultTape);
const [machine, setMachine] = useState(() =>
initMachine(initial, initial.defaultTape),
);
const [playing, setPlaying] = useState(false);
const [speed, setSpeed] = useState(200);
const program = PROGRAMS.find((p) => p.id === programId)!;
const headRef = useRef<HTMLDivElement>(null);
const selectProgram = (id: string) => {
const next = PROGRAMS.find((p) => p.id === id)!;
setProgramId(id);
setTapeInput(next.defaultTape);
setMachine(initMachine(next, next.defaultTape));
setPlaying(false);
};
const reset = () => {
setMachine(initMachine(program, tapeInput));
setPlaying(false);
};
const stepOnce = () => setMachine((m) => stepMachine(program, m));
useEffect(() => {
if (!playing) return;
const id = setInterval(() => {
setMachine((m) => (m.status === 'running' ? stepMachine(program, m) : m));
}, speed);
return () => clearInterval(id);
}, [playing, speed, program]);
useEffect(() => {
if (machine.status !== 'running') setPlaying(false);
}, [machine.status]);
useEffect(() => {
headRef.current?.scrollIntoView({
inline: 'center',
block: 'nearest',
behavior: 'smooth',
});
}, [machine.head]);
const cellRange = useMemo(() => {
const keys = Object.keys(machine.tape).map(Number);
const min = Math.min(machine.head, ...keys, 0) - PAD;
const max = Math.max(machine.head, ...keys, 0) + PAD;
const range: number[] = [];
for (let i = min; i <= max; i++) range.push(i);
return range;
}, [machine.tape, machine.head]);
return (
<div className="turing-machine">
<div className="tape-scroll">
<div className="tape">
{cellRange.map((i) => (
<div
key={i}
ref={i === machine.head ? headRef : undefined}
className={`cell ${i === machine.head ? 'head' : ''}`}
>
{machine.tape[i] ?? program.blank}
</div>
))}
</div>
</div>
<div className="status-line">
<span>
state <strong>{machine.state}</strong>
</span>
<span>
step <strong>{machine.steps}</strong>
</span>
<span className={`status ${machine.status}`}>
{STATUS_LABEL[machine.status]}
</span>
</div>
<div className="controls">
<div className="group">
<span className="group-label">program</span>
{PROGRAMS.map((p) => (
<button
key={p.id}
type="button"
className={programId === p.id ? 'active' : ''}
onClick={() => selectProgram(p.id)}
>
{p.label}
</button>
))}
</div>
<div className="group">
<button
type="button"
onClick={stepOnce}
disabled={machine.status !== 'running'}
>
step
</button>
<button
type="button"
onClick={() => setPlaying((p) => !p)}
disabled={machine.status !== 'running'}
>
{playing ? 'pause' : 'play'}
</button>
<button type="button" onClick={reset}>
reset
</button>
</div>
</div>
<div className="field">
<label htmlFor="tm-tape">
initial tape
<input
id="tm-tape"
type="text"
value={tapeInput}
maxLength={30}
spellCheck={false}
onChange={(e) => setTapeInput(e.target.value)}
/>
</label>
<label className="speed">
speed
<input
type="range"
min={50}
max={600}
step={25}
value={650 - speed}
onChange={(e) => setSpeed(650 - Number(e.target.value))}
/>
</label>
</div>
<p className="blurb">{program.blurb}</p>
<style>{`
.turing-machine {
border: 1px solid #2a2d31;
background: #0e1113;
}
.turing-machine .tape-scroll {
overflow-x: auto;
border-bottom: 1px solid #2a2d31;
padding: 1.5rem 0;
}
.turing-machine .tape {
display: flex;
width: max-content;
margin: 0 auto;
padding: 0 1rem;
}
.turing-machine .cell {
flex-shrink: 0;
width: 2rem;
height: 2rem;
display: flex;
align-items: center;
justify-content: center;
border: 1px solid #2a2d31;
margin-right: -1px;
font-size: 0.9rem;
color: var(--muted);
}
.turing-machine .cell.head {
border: 1px solid var(--accent);
color: #0b0d0f;
background: var(--accent);
position: relative;
z-index: 1;
}
.turing-machine .status-line {
display: flex;
gap: 1.25rem;
padding: 0.6rem 1rem;
border-bottom: 1px solid #2a2d31;
font-size: 0.8rem;
color: var(--muted);
}
.turing-machine .status-line strong {
color: var(--fg);
font-weight: normal;
}
.turing-machine .status.accepted {
color: var(--accent);
}
.turing-machine .status.rejected {
color: #e58a8a;
}
.turing-machine .controls {
display: flex;
flex-wrap: wrap;
gap: 1.25rem;
padding: 0.75rem 1rem;
}
.turing-machine .group {
display: flex;
align-items: center;
gap: 0.4rem;
flex-wrap: wrap;
}
.turing-machine .group-label {
color: var(--muted);
font-size: 0.75rem;
text-transform: uppercase;
letter-spacing: 0.04em;
margin-right: 0.15rem;
}
.turing-machine .controls button {
font-family: inherit;
font-size: 0.75rem;
color: #8a8f98;
background: rgba(0, 0, 0, 0.4);
border: 1px solid #2a2d31;
padding: 0.25rem 0.6rem;
cursor: pointer;
}
.turing-machine .controls button:hover:not(:disabled) {
color: #e6e6e6;
}
.turing-machine .controls button:disabled {
opacity: 0.4;
cursor: default;
}
.turing-machine .controls button.active {
color: #0b0d0f;
background: var(--accent);
border-color: var(--accent);
}
.turing-machine .field {
display: flex;
flex-wrap: wrap;
gap: 1.5rem;
padding: 0 1rem 0.75rem;
}
.turing-machine .field label {
display: flex;
align-items: center;
gap: 0.5rem;
color: var(--muted);
font-size: 0.75rem;
}
.turing-machine .field input[type='text'] {
font-family: var(--mono);
font-size: 0.85rem;
color: #e6e6e6;
background: #000;
border: 1px solid #2a2d31;
padding: 0.3rem 0.5rem;
width: 12rem;
}
.turing-machine .field input[type='text']:focus {
outline: none;
border-color: var(--accent);
}
.turing-machine .blurb {
color: var(--muted);
font-size: 0.8rem;
margin: 0;
padding: 0 1rem 1rem;
}
`}</style>
</div>
);
}