2017今年はじめから、コンピュータをボトムアップ的に理解したいという動機で計算論を独学しています。計算とは何かということを考えたり、チューリングマシンやラムダ計算のような計算モデルを知るのは中々面白いのですが、それを具体的な対象として考えたとき、計算可能な関数というものをうまく捉えられていないことに気づきました。個人的にはしっくり来る説明に感じたので、それをベースにしながら箇条書き感覚で計算可能な関数をどう表現できるのかを整理してみようと思います。(1)帰納的関数、ラムダ計算、チューリングマシンといった計算モデルで計算可能とされる関数のクラスである。(2)その計算を実行できるようなアルゴリズムが存在する関数である。(3)定義域内の入力を渡された場合、有限時間内に計算が終了して正しい出力を返す。(ただ下記で疑問に挙げているように少し理解が怪しい)。帰納的関数は部分関数であり、定義域外の入力に対しては未定義とされます。個人的に疑問なのはあらゆる入力に対して未定義となる帰納的関数を考えたら、それは計算可能な関数と呼んでよいのかということがあるのですが、これは未定義が許される以上、計算可能ということになるのでしょうか。(5)一般的なプログラミング言語で書ける関数とみてもよいはず。(6)数多くあるけれど、単純な例として以下のものが挙げられる。