Discover more from Matt Rickard
Accidentally Turing Complete
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.
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.
Pokemon Yellow (YouTube) – You can write and execution arbitrary programs in memory by buying specific items in a certain way.
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.
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.
1More formally, a system is Turing-complete if it can be used to simulate any Turing machine.