計算不可能
「現実に存在する計算機が遅いから」とかいう次元の話ではない
量子コンピュータが出ようが、さいきょうのスパコンが出ようが、1億年経って爆速計算機能力の機械が出ようが、計算不可能である
ある関数が
計算可能であることを示すためには、それを計算するプログラムを書いて示せばよいが、
計算不可能であることを示すためには、それを計算するプログラムが存在しないことを厳密に証明しないといけないので難しい
計算不可能なプログラムの例と、それが表す意味
compPlus(p,x)
万能関数 comp(p,x)
が未定義の場合は0を返す
そうでない場合は comp(p,x)
の値を返す
total(p)
プログラム p
を引数に取る
出力
1
引数 p
が何かしらのプログラムのコード(一つの自然数)であり、
かつ、 p
が有限時間で終了するような全域関数であるとき
0
それ以外
p
がプログラムのコードでないとき
p
が真部分関数であるとき
equalQ(p)
プログラム p
を引数に取る
確実に動くことがわかっているプログラムQと全く同等の挙動をするかどうか
出力
1
引数 p
が何かしらのプログラムのコード(一つの自然数)であり、
かつ、任意に固定されたプログラムQが計算する部分関数と、 p
が計算する部分関数が等しいとき
0
それ以外
p
がプログラムのコードでないとき
p
とQが異なる部分関数を計算するとき
Zeno machine
可算無限個のアルゴリズム手順を有限の時間で実行できる
参考