今年はじめから、コンピュータをボトムアップ的に理解したいという動機で計算論を独学しています。計算とは何かということを考えたり、チューリングマシンやラムダ計算のような計算モデルを知るのは中々面白いのですが、それを具体的な対象として考えたとき、計算可能な関数というものをうまく捉えられていないことに気づきました。

色々手持ちの資料を読みましたが、Wikipedia の Computable function が個人的にはしっくり来る説明に感じたので、それをベースにしながら箇条書き感覚で計算可能な関数をどう表現できるのかを整理してみようと思います。

計算可能な関数は (1)

帰納的関数、ラムダ計算、チューリングマシンといった計算モデルで計算可能とされる関数のクラスである。

  • 1930年代に計算についての考察が進み、様々な計算モデルが作られた
    • 帰納的関数
    • ラムダ計算
    • チューリングマシン
  • これらでそれぞれ定義される計算可能な関数のクラスは一致することが証明されている
  • Church-Turing thesis でその関数のクラスを計算可能な関数としてみなそうという主張がされている

計算可能な関数は (2)

その計算を実行できるようなアルゴリズムが存在する関数である。

  • 具体的な計算モデルを想定するほうがイメージしやすいかも
  • 何かチューリング完全な計算モデルを想定したときに、目的とする関数に対する入力や出力等が計算モデルに合わせた形でエンコーディングでき、計算が有限ステップで表現できればよいということ
  • ただ アルゴリズム - Wikipedia ではアルゴリズムの定義を (1) で挙げている関数のクラスを計算する手続きとしているので、計算可能な関数としてこの考えを挙げるのは多分よろしくない

計算可能な関数は (3)

定義域内の入力を渡された場合、有限時間内に計算が終了して正しい出力を返す。

  • 計算が終了するならばいくら時間がかかってもよい
  • 計算が終了するならばいくらスペース (的確な表現がわからないがコンピュータでいうメモリ) を使ってもよい
  • 結果が返ってくるならば、その出力は正しいということが保証される

計算可能な関数は (4)

定義域外の入力を渡された場合、計算が停止しないか、あるいは 計算途中で stuck する。

  • stuck とはチューリングマシンでいえば計算途中で適用できる規則が無くなるような状態

計算可能な関数だからといって全ての入力に対して結果が返せるとは限らないということです (ただ下記で疑問に挙げているように少し理解が怪しい)。

原始再帰関数は全域関数で全ての入力に対して定義されるのですが、 (計算可能な関数のクラスである) 帰納的関数は部分関数であり、定義域外の入力に対しては未定義とされます。

個人的に疑問なのはあらゆる入力に対して未定義となる帰納的関数を考えたら、それは計算可能な関数と呼んでよいのかということがあるのですが、これは未定義が許される以上、計算可能ということになるのでしょうか。

計算可能な関数は (5)

一般的なプログラミング言語で書ける関数とみてもよいはず。

  • チューリング完全と言われているような言語であれば、いくら複雑な構文を持っていたとしてもチューリングマシンやラムダ計算で表すことができるはず
  • これを少し計算モデルとして考えやすくした形が while プログラムとかになる
  • (4) の疑問はこちらでは 「while の無限ループのみを含む関数」 のような形で表されるのかなと

計算可能な関数は (6)

数多くあるけれど、単純な例として以下のものが挙げられる。

  • 文脈自由言語の認識
  • 自然数上の加減乗除

計算不可能な関数は (1)

よく有る例として 停止性問題 が挙げられる。

  • 最近少し考えている例だけど、ある自然数解が存在するか否かを求めるような問題に対して一つずつひたすら自然数を試していくというのをどう捉えればよいのか
    • 有限時間で解ける保証が無いのでこれを対象とする問題に対するアルゴリズムとは言えない
    • ただこのやり方自体は一般的なプログラミング言語で書けるし帰納的関数なんかでも書けるはず
    • 目的とする計算ではないけど、これ自体は計算可能な関数になる?

理解できていないけど計算可能性として恐らく重要な単語

  • 決定可能集合 (帰納的集合)
  • 枚挙可能集合 (帰納的可算集合)