万能関数のチューリングマシン版

ざっくりイメージ

そもそもチューリングマシンでは、マシン内で扱う言語を01列にコード化して使う

関数やプログラム自体も01列にコード化できる

すなわち、あるチューリングマシンMも、01列にコード化できる

これを\llbracket M\rrbracketと書く

Mに対する引数\alphaも、もちろん01列にコード化できる

これを\llbracket \alpha \rrbracketと書く

この\llbracket M\rrbracketと\llbracket \alpha \rrbracketは、共に01列なので

この2つの01列を入力にとって、M(\alpha)の結果を返すチューリングマシンを作ることができる

これが万能チューリングマシン

ちょっと違うけどイメージとしてはセルフホストも近い

万能チューリングマシン以前は、

やりたい計算ごとに一つの機械を作る、というのをやっていたが、

万能チューリングマシンが1台あれば、

機械の設計図\llbracket M\rrbracketと、その引数\llbracket \alpha \rrbracketを用意すればなんでも計算できる

うれしい！