万能チューリングマシン
universal Turing machine
ざっくりイメージ
そもそもチューリングマシンでは、マシン内で扱う言語を01列にコード化して使う
関数やプログラム自体も01列にコード化できる
すなわち、あるチューリングマシン$ Mも、01列にコード化できる
これを$ \llbracket M\rrbracketと書く
$ Mに対する引数$ \alphaも、もちろん01列にコード化できる
これを$ \llbracket \alpha \rrbracketと書く
この$ \llbracket M\rrbracketと$ \llbracket \alpha \rrbracketは、共に01列なので
この2つの01列を入力にとって、$ M(\alpha)の結果を返すチューリングマシンを作ることができる
これが万能チューリングマシン
ちょっと違うけどイメージとしてはセルフホストも近いmrsekut.icon 万能チューリングマシン以前は、
やりたい計算ごとに一つの機械を作る、というのをやっていたが、
万能チューリングマシンが1台あれば、
機械の設計図$ \llbracket M\rrbracketと、その引数$ \llbracket \alpha \rrbracketを用意すればなんでも計算できる
うれしい！