計算不可能
「現実に存在する計算機が遅いから」とかいう次元の話ではない
量子コンピュータが出ようが、さいきょうのスパコンが出ようが、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
可算無限個のアルゴリズム手順を有限の時間で実行できる
参考