Some things were not supposed to be Turing-complete. This is a collection of such accidents.

Stuff which is somehow limited (stack overflows, arbitrary configuration, etc) is still considered Turing complete, since all "physical" Turing machines are resource limited.

C++ Templates

Although they were initially not supposed to, C++ templates are Turing-complete. For proof look at this paper (pdf).

X86 MMU

The page fault handling in X86 can be used to implement a simple machine. Basically, a page fault pushes a word to the stack, which might underflow generating another trap. This mechanism provides a "subtract and branch if less than or equal to zero" instruction. Enough to implement a Turing machine. Demo video Talk video

Magic: The Gathering

Magic is a card game. Apparently, the rules are complex enough to reach Turing-completeness.

HTML5 + CSS3

While older HTML/CSS versions are not, with some new additions, you can write a rule 110 automaton. The original page has moved here and there is also Github and a video.

Minecraft

Maybe this one was intentional, but the complexity of the computers people build in Minecraft is impressive. video example

SQL

SQL is usually not considered to be Turing-complete. However, with the features Common Table Expressions and Windowing, SQL is Turing Complete. The proof is in these slides. Also, look a Mandelbrot in SQL:2008. A broader exploration of various SQL-turing-machines was done by Fabien Coelho.

(C Preprocessor)

The C preprocessor is only Turing-complete, if executed in a loop, which feeds the output to the input ad infinitum. An example has won the IOCCC 2001 contest. Look into the herrmann1 entry. Nonetheless included in this list for coolness.

Apache Rewrite Rules

Apache comes with the mod_rewrite plugin to rewrite URLs. These rules ultimately are a Turing complete string rewrite system. Though the default configuration sets very low limits to recursion.

(Pokemon Yellow)

A Pokemon game, which is finished in 1minute 36seconds. The interesting point about this speedrun is the bug it exploits. Turns out the game logic itself is Turing-complete in the sense that you can rewrite the assembly itself with game actions. For example, someone turned the game into a MIDI player.

Scala Type System

Apparently, you can implement the SKI calculus (which is Turing complete) in Scala types. However, the compilers stack overflows at some point.

MediaWiki Templates

In MediaWiki you can define templates. Since they provide recursion, you can apparently implement lambda calculus.

Little Big Planet

Yet another game, where you can build a basic computer. For example, Conways Game of Life.

Server Side Includes

While SSI was design as a scripting language, loops were not planned. The trick was to find a way for recursion. The recursion is limited in all web servers.

Sendmail

The venerable mail server is known for its arcane configuration. Turns out the configuration is also turing complete.

Border Gateway Protocol (BGP)

BGP is an internet backbone technology, which manages the routes your data packages take. The paper "Using Routers to Build Logic Circuits: How Powerful is BGP?" prove Turing-Completeness via logic gate comparison.

© 2013-10-20
Google Analytics Alternative qznc