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).

Java Generics

Although Java set out to fix the errors of C++, it also fell into Turing-completeness eventually. Radu Grigore built a parser generator for fluent interfaces.

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.

Also see the talk.

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.

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.

Excel

It is no surprise, since Excel includes a scripting language. However, there is a nice blog post, which shows how to encode a Turing machine in Excel using only formulas.

Super Mario World

There are glitches in Super Mario World, such that you can write arbitrary values into some unused parts of the memory and then execute them. Here is a video, where a human (not a script!) creates a playable Flappy Bird clone this way.

PowerPoint

Tom Wildenhain made a hilarious presentation (see video below) and also wrote a paper "On the Turing Completeness of MS PowerPoint. It answers the question "whether any other applications are necessary at all, or if all computational tasks can be accomplished through the creation of dedicated .pptx files" with "Yes". Of course, he does not use VBScript or Macros. Wildenhain only used AutoShape, Animation, and hyperlinks. Nevertheless, Powerpoint is not really Turing-complete as the viewer is required to click for each step of the machine.


Also interesting: When Goto Is Just Fine, One Letter Programming Languages, and Hacker Titles for Business Cards.

© 2013-10-20
qznc