であることの証明
ある処理系がチューリング完全「でない」ことを示すにはどうすればいいんだろう。
http://d.hatena.ne.jp/gnarl/20080222/1203683751
「ある」ことの証明であればチューリングマシン実装して終わりだが。
そうか！少なくともチューリング完全で「ある」ことの証明方法はわかった。
いわれてみればそのとおりだよなあ。
遷移規則をうまく構成することで、驚くべきことにすべてのチューリング機械の動作を再現するチューリング機械（万能チューリング機械）を組み立てることが可能である。
http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
また全てのチューリングマシンは万能チューリングマシンであることも証明されている。
すなわち究極的にはひとつのコンピュータアーキテクチャだけで事足りるということである。
別にいわゆるチューリングマシンそのものじゃなくて、チューリング完全であることが証明されている他の処理系を実装することによっても、
チューリング完全であることの証明になるか。
「2つの状態と3つの色を持つ装置は（現時点で知られる限り最小の）万能チューリングマシンである」
http://slashdot.jp/science/article.pl?sid=07/10/29/0244230
これが一番実装するのが楽なチューリングマシンか。
追記
状態が機械の内部状態、色がテープに読み書きされる記号のことだった。
なのでチューリングマシンのシステム自体は変わらなくて、その使い方が内部状態は2値だけ、テープに書き込む記号が3値だけという意味だ。
絵の内容のおぼえがき
矢印がヘッドで、↓がstateが1、↑がstateが2、の意味。
箱がテープの１マスで、白が0、黄色が1、オレンジが2の意味。
上が動作前の状態、下が動作後の状態で、矢印の位置の変化がヘッドの動き、色の変化がテープへの書き込みを表す。
Wolfram 2,3 Turing Machine Research Prize: Technical Details
http://www.wolframscience.com/prizes/tm23/technicaldetails.html
