うっかりチューリング完全になっちゃったもの

Accidentally Turing-Complete ― Andreas Zwinkau

本来なら、チューリング完全となるべきではなかったものがある。これは、そのようなうっかりチューリング完全になってしまったものの例である。

C++テンプレート

当初はチューリング完全を目指していなかったが、C++テンプレートはチューリング完全になってしまった。その証明は、この論文にある（PDF）

x86 MMU

x86のpage fault handlingは、単純なマシンの実装に使える。原理としては、page faultが1 wordをスタックに積み、それによりアンダーフローを起こして別のトラップを生成する。この仕組みは、「減算して0以下ならば分岐」処理を実現する。チューリングマシンを実装するには十分である。デモ動画、講演動画

マジック・ザ・ギャザリング

マジック・ザ・ギャザリングはカードゲームである。明らかに、ルールがチューリンク完全に達するほど十分に複雑である。

HTML5 + CSS

昔のHTML/CSSは違ったのだが、新機能の追加により、Rule 110 automatonを書くことができる。残念ながら、元のサイトは壊れているが、動画がある。

Minecraft

これは意図的かもしれないが、Minecraft上で構築されたコンピューターの複雑さには目をみはるものがある。動画例

SQL

SQLは通常、チューリング完全とはみなされない。しかし、Common Table Expressionとwindow機能により、SQLはチューリング完全である。証明はこのスライドにある。また、SQL:2008のマンデルブロも必見。Fabien Coelhoによる、SQLのチューリング完全性に関する後半な説明もある。

(Cプリプロセッサー)

Cプリプロセッサーは、ループ内で実行された場合、無限に出力を入力にでき、チューリング完全となる。IOCCC 2001コンテストで優勝した例。herrmann1のエントリを参照。面白かったので、ここに付け加えた

Apache Rewrite Rules

Apacheのmod_rewriteプラグインはURLを書き換える。この書き換えのルールは、究極的には、チューリング完全の文字列書き換えシステムになっている。しかし、デフォルトの設定では、再帰回数の制限がとても低く設定されている。

(ポケットモンスター　イエロー)

ポケモンのゲームの、1分36秒のゲームプレイがある。スピードランの興味深い点は、バグを利用する点にある。ゲーム操作によって、ゲームのアセンブリを書き換えることができるという点で、チューリング完全性を満たすゲームに書き換えることができる。たとえば、ゲームをMIDIプレイヤーに書き換えた者もいる。

Scalaの型システム

当然のことながら、Scalaの型を使って、SKI計算を実装できる。（SKIコンビネータ―計算はチューリング完全である）。しかし、いずれ、コンパイラーのスタックがオーバーフローを起こす。

MediaWikiのテンプレート

MediaWikiではテンプレートを定義できる。テンプレートは再起できるために、当然のことながら、lambda計算を実装できる。

Little Big Planet

このゲーム内では、基本的なコンピューターを構築できる。例えば、コンウェイの考案したライフゲーム。

Server Side Includes

SSIはスクリプト言語としては設計されていなかったので、ループは想定されていなかった。ループを作るコツは、再帰方法を見つけることだ。Webサーバーでは、再帰回数は制限されている。

Sendmail

由緒正しいこのメールサーバーは、古代技術のような設定で有名だ。どうやら、この設定自体がチューリング完全であったらしい。

Accidentally Turing-Complete | Hacker News

Hacker Newsでは、他にもDwarf FortressやApache Rewrite ruleや、Little Big Planet（どうもゲーム内にゲーム作成機能があるらしい）や、Scalaの型システムなどが、チューリング完全だとして紹介されている。

Colossal turing machine made in city-building game - Boing Boing
unsafePerformHack » An excursion in mod_rewrite
xkcd • View topic - Turing Completeness in weird places
Scala type level encoding of the SKI calculus | Michid's Weblog

2013-10-22追記：新たに追加されていたので更新。