Awesome Turing Machine Completeness

A curated list of awesome Turing Machine Equivalent (TME) systems.

Programming languages are not included as they are trivially Turing-Machine Equivalent.

Contents

• Games
• "Surprising"
• Theoretical

Games

• Braid
• Dwarf Fortress
• Factorio
• Little Big Planet
• Magic: The Gathering
• Minecraft
• (Infinite) Minesweeper
• OpenTTD
• Pokemon (Yellow)
• Super Mario World

Surprising

• Airplane Ticket Planning/Validation
• Apache mod_rewrite
• BGP
• C++ Templates
• Domino Toppling
• Excel
• HTML + CSS3
• Java Generics
• MediaWiki Templates
• Packet Switching Networks
• PowerPoint
• Scala Type System
• Sendmail
• SSI
• SVG
• TypeScript Type System
• Vim Normal-Mode
• X86 MMU

Theoretical

• 1D Cellular Automata Rule 110
• Conway's Game of Life
• Cyclic Tag System
• Post-Turing Machine
• String Rewriting System
• Turing Machine
• Wang Tiles

References

• beza1e1.tuxen.de: Accidentally Turing-Complete
• Gwern.net: Surprisingly Turing-Complete
• Wikipedia: Turing machine equivalents
• Wikipedia: Turing completeness

License