Collection · 10 machines · curated by @thethinkmachine
Beyond regular
Stacks, queues, counters and tapes: what each kind of memory buys.
The machines
aⁿbⁿ
DPDA · 3 states
Deterministic
Added 28 Sept 2026Updated 28 Sept 2026
Bracket matcher ( ) [ ] { }
DPDA · 1 state
Tested · Deterministic
Added 28 Sept 2026Updated 28 Sept 2026
Palindromes: guess the middle
NPDA · 3 states
Tested
Added 28 Sept 2026Updated 28 Sept 2026
Bank account: never overdrawn
Counter · 2 states
Tested
Added 28 Sept 2026Updated 28 Sept 2026
Perfect copy: w#w
QA · 2 states
Tested
Added 28 Sept 2026Updated 28 Sept 2026
aⁿbⁿcⁿ — beyond one stack
2PDA · 4 states
Tested
Added 28 Sept 2026Updated 28 Sept 2026
aⁿbⁿcⁿdⁿ — four counts, one stack of stacks
EPDA · 6 states
Tested
Added 28 Sept 2026Updated 28 Sept 2026
Powers of two, by halving
LBA · 6 states
Tested · Deterministic
Added 28 Sept 2026Updated 28 Sept 2026
Binary addition a+b
TM · 8 states · halts in 0
Tested · Deterministic
Added 28 Sept 2026Updated 28 Sept 2026
Palindromes in linear time
MTM · 5 states
Tested · Deterministic
Added 28 Sept 2026Updated 28 Sept 2026