Accidentally Turing Complete

Apr 13, 2022

In layman's terms, a system is Turing-complete if that system can compute as much as any general-purpose computer or computer language1. It means that you can model things like conditional logic (if/else), arithmetic, state, transitions, looping and recursion, input and output.

Most computer languages are intentionally Turing-complete – Java, C++, JavaScript are designed so that they can run arbitrary programs. But some systems are surprisingly Turing complete. Through some feature or escape hatch, they can be made to run any program (of course, there's no guarantee that they will run them in a reasonable time). Here are some accidentally Turing-complete systems.

Languages that aren't meant to be Turing-Complete

  • SQL (blog) – Through CTE and windowing, you can implement a cyclic tag system, which has been proven to be Turing-Complete.
  • CSS (GitHub) – With CSS declarations, you can encode logic gates and eventually recreate the Rule 110 cellular automaton (think Conway's Game of Life).
  • BGP (paper) – BGP configurations can be assembled into logic gates, clocks, and other arbitrary logic circuits.

Video Games

  • Pokemon Yellow (YouTube) – You can write and execution arbitrary programs in memory by buying specific items in a certain way.
  • Minecraft (YouTube) – Uses a block called Redstone to simulate Turing-machines. Some have even built an entire CPU (YouTube).
  • Doom (blog) – The author implemented logic circuits using monster movements in Doom.
  • Dwarf Fortress (wiki)
  • Super Mario World
  • Magic the Gathering (paper) – Not a video game, but the ruleset of Magic the Gathering can create a Turing-Machine.

Programs

  • Excel (blog)– The LAMBDA function allows you to create custom functions that can recursively call themselves or each other, making Excel's formula language Turing-complete.
  • PowerPoint (paper) – The author creates a Turing Machine with just AutoShapes and On-Click animations.
  • Sendmail (blog) – A corollary to Zawinski's Law.
  • Vim (GitHub)

1More formally, a system is Turing-complete if it can be used to simulate any Turing machine.