HTML5 + CSSがチューリング完全であるという話

この前非情報系の友人と飲んでいて話題に出そうとして出せなかった話。

その友人は以前HTMLがプログラミング言語だとうっかり情報系の先輩の前で口にしてしまい、当然のごとくそれは間違っているとツッコミを受けたそうだ。

そこで「実はHTML(+CSS)はチューリング完全と言えなくもないからプログラミングはできるんだよ！」というこの前聞いた話を振ろうとしたものの、相手はチューリングテストとチューリングマシンの違いも分かっていなかったので諦めたのだった。ウカツ！

チューリングテストとチューリングマシン

â’¸ Duane Wessels 2012

どちらも計算機科学の発展に大きく寄与したアラン・チューリングによって考案された概念。 (でも中身は月とスッポンくらい違う)

チューリングテストとは

チューリングテストはある機械が知性を持つかどうかを判定するためにチューリング先生が考えだしたテストのこと。 どういうテストをするかというと、判定者が人間とコンピュータを相手に(文字で)対話を行い、判定者が人間とコンピュータを明確に区別できなければそのコンピュータは知性を持つと判定する。

ただし、結局は人間の主観で判定するため、明確な合格というのは定義しづらい、というかできない。 最近"合格した"と主張するAIが出てきたらしい。

史上初のチューリングテスト合格スパコンが登場、コンピュータの「知性」を認定 - GIGAZINE

チューリングマシンとは

チューリングマシンとは計算機を数学の世界に持ち込むためにチューリング先生が考えだした、 ものすごーく単純な仮想機械のこと。(ただし、考案された1936年当時電子計算機なんてものは存在しなかった！)

チューリングマシンとは 【 Turing machine 】 - 意味/解説/説明/定義 ： IT用語辞典

チューリングマシンはあらかじめ設定された幾つかの「状態」を持っており、その「状態」とヘッドから読み出したデータの組み合わせによって、「ヘッドをテープ上で一マス移動させる」「テープのヘッドのあるマスにデータを書き込む」「『状態』を変更する」のいずれかの動作を行う。その後、移動後のヘッド位置からデータを読み込み、そのデータと新しい「状態」の組み合わせに従って、次の動作を行う。

とても単純な原理で動作するが、一定の計算手順(アルゴリズム)に基づいて答えが出せるような問題はすべてチューリングマシンで 答えを求めることができる。(もちろんチューリングマシンで答えを求められないような問題はアルゴリズムに基づいてコンピュータで解くことはできない。)

そしてある計算のメカニズムがこのチューリングマシンと同等の計算能力を備えていることを、チューリング完全と呼ぶ。

HTML+CSSの計算能力について

と、ここまでが前座である。ここからが本題のはずだったが、巻いて説明しようと思う。

プログラミング言語はある意味でアルゴリズムを記述するための言語である。チューリング完全でないプログラミング言語処理系は 存在価値がない。(メモリとか現実的な制約は抜きにして)

では逆に、ある言語がアルゴリズムを記述できるならプログラミング言語と言えるだろうか？ 実は世の中にはプログラミング言語と呼べないまででもチューリング完全になってしまったものがたくさんある。

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

百聞は一見にしかず。これ(Rule 110)を開いて一番上の行をどこかクリックし、 左上の指示にしたがってTabとSpaceをカチカチやってみよう。開くのが面倒な人には動画もある。

Eli Fox-Epstein's Rule 110 HTML & CSS3 Machine ...

ライフゲームを知っている人はそれっぽい動きと思ったかもしれない。

これはルール110と呼ばれるセル・オートマトンを完全にHTMLとCSSのみで記述したものである。 このルール110セル・オートマトンは実はチューリングマシンと同等の計算能力を備えていることが示されている。

これを書いた人は "This was the first proof ever that CSS is Turing-complete." と冗談めかして書いているが、実際にこれがチューリング完全であるかどうかは海外のフォーラムでも議論されている。

落とし所がなくなってしまったが最後に、チューリングの伝記が映画になるそうである。 日本での公開は今年の年末になるらしいので、気になる方は見に行ってみてはいかがだろうか？

アラン・チューリングの伝記映画“The Imitation Game”公式トレーラー2種。追記。 新・豆酢館/ウェブリブログ

チューリング