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.
_
_
_
1
0
1
1
_
_
_
state rightstep 0running
program
Scans right to find the end of the number, then carries leftward through the 1s the way you would by hand.
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. Unbounded memory is the whole story: it's the difference between a machine that can only recognize patterns and one that can actually compute.
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.
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's provably undecidable in general. But for small enough machines, you can just try every one of them: the included 3-state, 2-symbol machine was found by brute-force simulating all roughly one million possible 3-state machines and keeping the one that writes the most 1s (six) before halting, starting from a completely blank tape. It's a real answer to "how much can a machine this small actually do" — you just can't get that answer any way other than checking.
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;
max-width: 60ch;
}
`}</style>
</div>
);
}