ついったーで「HTMLでチューリング機械は作れるか?」といふ話題があったので考察。
チューリング機械と計算能力
チューリング機械 とは、イギリスの数学者 アラン・チューリング (Alan Mathison Turing) が計算可能性の定義のために提唱した想像上の装置。 ja.Wp の チューリングマシン、チューリング完全、チャーチ＝チューリングのテーゼ あたりを参照のこと。
チューリング機械はそのシンプルな構造にも拘らず、割といろんな計算を実装することが可能で、2 + 3 みたいな単純な計算は云ふまでもなく、高度な条件判断を伴ふ複雑なプログラム(計算)を記述することもできる。このチューリング機械と同じ計算をすることができることを「チューリングマシンと等価の計算能力を持つ」「チューリング完全である」といふ。計算能力 とは計算時間や効率とはまったく関係がなく、 計算することができるか、できないか といふ問題。C言語や Lisp, Ruby, JavaScript と言ったメジャーなプログラミング言語は、ほとんど漏れなくチューリング完全であると言ふことができる*1。
単純には「無限長のテープを摸倣できるリスト(配列)」「条件分岐」「無限ループまたはリストに対する再帰的な操作」なんかができればチューリング完全と呼べさうですね。実用的なプログラミング言語なら、チューリング完全でないやうにする方が難しいよねー、って感じです。繰り返しますが、速度や効率はまったく別問題＞＜
HTMLとCSSはプログラミング言語か?
まづ、 HTML と CSS についておさらひ。HTML は マークアップ言語で、 CSS は スタイルシート 。どっちもプログラミング言語じゃないです！ はいをはり！
これでとは言っても、プログラミング言語ではないものに計算をさせてみるのもなかなか楽しいものなので、こんなことを考へてみまして。
2012-06-14 1st - jsdo.it - share JavaScript, HTML5 and CSS
何をやってるのかはソースコードを読んでもらへればばればれなんだけど、これで CSS にも計算能力があるぜやったー！ ってことで良いのか……?
(- 5 5) とか Lisp っぽい記述がありますが、これは表示するのにわかりやすく書いてるだけなので、本質的には無視して良いものです。
<div class="add"><span class="n6">(+ 6 9)<span class="m9"></span></span></div> <div class="add"><span class="n1">(+ 1 2)<span class="m2"></span></span></div>
肝腎なのは、これの div > span > span の入れ子ですね。これ重要。
それじゃ、該当するセレクタのスタイル定義をば。
... .add > .n6 > .m8:after { content: "14" } .add > .n6 > .m9:after { content: "15" } .add > .n6 > .m10:after { content: "16" } ... .add > .n1 > .m0:after { content: "1" } .add > .n1 > .m1:after { content: "2" } .add > .n1 > .m2:after { content: "3" } ...
はい、すべての計算結果が定数で書いてありますね。しかもこのスタイルシートで対応してるのは 0〜20 までの二項の整数の四則演算のみ。いえーい。
hoge > fuga は、「hoge の直下にある fuga」 を意味します (子セレクタ) 。 .foo は、 HTML の <span class="foo">< にマッチ。 piyo:after と content: "fugafuga" はセットで、 piyo にマッチした要素の内容の後に content で指定した 文字列が付け足される。
先の HTML コードは、本質的には次のやうな S式で表現することができる。
'(add 6 9) ; <div class="add"><span class="n6"><span class="m9"></span></span></div> '(add 1 2) ; <div class="add"><span class="n1"><span class="m2"></span></span></div>
あるいはまとめてこんな感じ。
(define exprlist '( (add 6 9) (add 1 2) (sub 5 5) (sub 8 16) (mul 20 20) (mul 9 0) (div 3 0) (div 6 3) (div 100 10) (div -5 3)))
せっかくなので最近ちょっと勉強してる Scheme でこんなふうに書けると良いですね！
(define (html lst) (let ((v (assoc lst known-expr))) (if v v '(lst . "undefined"))))
おまけに、こんな感じに既知の計算結果を定義しておきます。
(define known-expr '( ((add 6 9) . 13) ((add 1 2) . 3) ((sub 5 5) . 0) ((sub 8 16) . -8) ((mul 20 20) . 400) ((mul 9 0) . 0) ((div 3 0) . "NaN") ((div 6 3) . 2)))
この known-expr は上に引用した CSS のコードに相当します。
そいでもって、これで出力できると良いかな、って。
(for-each (lambda (x) (print (format "~a ; => ~a" x (cdr (html x))))) exprlist)
これを評価すると、こんな出力。
(add 6 9) ; => 13 (add 1 2) ; => 3 (sub 5 5) ; => 0 (sub 8 16) ; => -8 (mul 20 20) ; => 400 (mul 9 0) ; => 0 (div 3 0) ; => NaN (div 6 3) ; => 2 (div 100 10) ; => undefined (div -5 3) ; => undefined
はい、 HTML と CSS がこの一連の Scheme のプログラムとまったく同じ計算能力があることは證明できましたね！
それだけ?
うん。それだけ。
HTML をチューリング完全と呼ぶには何が足りないか
HTML は紙です。紙に計算を書き込むことはできますが、紙に計算能力はありません＞＜
チューリングマシンでいへば、テープの役割をすることはできます。
CSS をチューリング完全と呼ぶには何が足りないか
CSS はインクです。インクに計算能力は…と言ひたいところではあるのですが、実際には紙に書かれてる内容によって色が変ってねるねるねるね……もとい、程度の条件分岐をすることは可能です。
でも、再帰もできない、無限ループもできない。足りないものだらけ＞＜
