Unexpectedly Turing-complete
This is a collection of systems, such as restricted subsets of programming
languages or games, that are Turing-complete, but may not be expected. I have
included programs that prove Turing-completeness by construction, but also other
interesting programs for fun and demonstration.
Subsets of programming languages
- C variable-length arrays: A subset of C99, “disembodied C”, with only VLA
length expressions and functions with empty bodies, parameters, and forward
declarations.
- C++ templates: A subset of C++ with only templates, template specialization,
struct, typename, and typedef.
-
“Impact of Economics on Compiler Optimization”
by Arch D. Robison (2001), in section 4, frames C++ templates as a
compile-time optimization in, provides a tree sum example, and compares it
to functional programming:
Template metaprograms are programs that run at compilation time. When the
ISO C++ committee added templates to C++, the following features were
required:
- Instantiation of member types (and member constants of integral type) is
demand driven.
- Template identifiers may be overloaded, with resolution based on pattern
matching.
- Templates may be recursive.
The list above makes obvious to functional programmers what the committee
did not realize until later: templates are a functional language,
evaluated at compilation time.
- λ-calculus
by Matt Might (2009)
- 4-bit adder
by Aaron Ballman (2013)
- Coq typeclass resolver: Typeclass instance resolution is an unrestricted proof
search. Notably, Coq’s type system is Turing-complete, but it’s language is
not—the opposite of typical.
- Haskell type system: A subset of Haskell with multi-parameter typeclasses,
functional dependencies, and undecidable instances.
- Java generics: A subset of Java with subtype checking.
- POSIX
printf: A single call to POSIX printf in a loop.
- PostgreSQL: Uses common table expressions (CTEs) and windowing.
- Cyclic tag system
by Andrew Gierth (2009)
- Mandelbrot set
by Peter Eisentraut (2009)
- Presentation
on cyclic tag system, Mandelbrot set, and travelling salesman problem
by David Fetter (2009)
- Turing machine
by Fabien Coelho (2013)
- Brainfuck with CTEs by David Archibald (2024, unpublished)
- Rust type system: A subset of Rust with type parameters, traits,
multi-parameter traits, and associated types.
- Rust
macros_rules! and traits
- fortraith: compile-time Forth
compiler by Szymon Mikulicz (2020)
[HN]
- Transact-SQL
- TypeScript type system
- x86 MMU fault handling
- x86
mov: Only the mov instruction of x86.
DSLs
Domain-specific languages that are Turing complete.
- awk
- jq
- bf.jq: Brainfuck interpreter
by TSUYUSATO Kitsune (2014)
- JSON formatter
by itchyny (2019)
- bf.jq: Brainfuck
interpreter by itchyny (2019) [blog]
- wsjq: Whitespace interpreter
by Thalia Archibald (2021)
- jqjq: jq interpreter
by Mattias Wadman (2022)
- sed
Automata
- OpenType fonts
- HarfBuzz
- llama.ttf by Søren Fuglede Jørgensen
(2024) is a LLM and inference engine in a HarfBuzz Wasm shaper.
Games
- Doom
- counter.wad
by fraggle (2006) is an in-game 4-bit binary ripple carry adder circuit
using voodoo dolls and conveyor belts [video].
- Half-adder
by Jared Candelaria (2021) is an in-game half-adder circuit using lifts and
teleporters [video].
- Doom-in-Doom
by kgsws (2022) uses a code execution exploit to run Chocolate Doom in Doom
2 on DOS [code].
- conway.wad
by Piotr Wieczore (2022) is an in-game simulator for Conway’s Game of Life,
using scrollers, teleporters and floor movement [code].
- Adding Machine
by Danny Spencer (2022) is an in-game calculator that adds 2-digit decimal
numbers with a display, using a BDD encoding of logic as monsters, doors,
teleporters, and switches [code].
- Dwarf Fortress
- Magic: The Gathering
- Magic Turing Machine
by Alex Churchill (2012) embeds a Turing machine in Magic, Wolfram’s (2,3)
universal Turing machine in versions 1–4
and Yurii Rogozhin’s
(2,18) universal Turing machine in version 5. Cory Doctorow reported
on it.
- “Magic: The Gathering is Turing Complete”
by Alex Churchill, Stella Biderman, and Austin Herrick (2019) embeds
Rogozhin’s (2,18) universal Turing machine in the game, such that the first
player is guaranteed to win if and only if the Turing machine halts. Unlike
the previous designs by the first author, players are not required to make
particular choices.
- I Built a COMPUTER in Magic: The Gathering
by Because Science (2019) demonstrates the Turing machine of the paper in
gameplay
- Minecraft
- Rollercoaster Tycoon
- Terraria
- Tetris
Other
- Excel
- Excel 16-Bit CPU
by Inkbox (2024) is a CPU in Excel with programs compiled from Excel-ASM16
assembly [code]
Lists
Not Turing-complete