計算モデルとプログラミング
状態機械、有限オートマトンの限界
状態を区別して保つ必要がある計算は出来ない
上限を設定しない限り、状態数が無限に必要になるため
ある関数一つを計算する機械
計算可能な関数とは
あるxのf xが定義されているときに停止する
未定義のときに停止しない
万能チューリング機械
あるチューリング機械を実現できるチューリング機械
チューリング機械の定義をプログラムとするインタープリタ、言語処理系とも言える
任意のプログラムと任意のデータを与えたとき、停止するかを判断するプログラムは存在しない
レジスタ機械
何種かある
突き詰めると4命令でチューリング機械と同等の計算能力を持つ
ZERO, SUCC, JZDEC, HALT
逐次処理、条件分岐、繰り返しの3種の命令からなる計算モデル
関数型計算モデル 帰納的関数
前者関数、後者関数のみで加減算を定義できる
ここでは Haskell を利用
原始帰納的関数 (原始再帰関数, Primetive Recursive Function, PRF) を導入して
3つの基本関数と2つの構成方法で多様な関数を実現する
if や AND, OR, NOT などの論理演算に相当する関数も定義出来る
クラス(関数の集合)の一つでもある
基本的に全域関数が属する
部分関数は表現できない
ただし、アッカーマン関数など一部の全域関数は定義を満たさないためこのクラスに属さない
有限回の繰り返ししかできないのが欠点…？
最小化を使って、原始的帰納的関数を帰納的関数に拡張する
チャーチの提唱:
すべての計算可能な関数は帰納的関数である
命令型計算モデルと関数型計算モデルの相違点はデータの扱い方
前者はレジスタ、後者は引数、によりデータを取り扱う
ラムダ計算における計算とはβ変換のこと
数値計算ではなく、数式計算
という印象
mathmatica がこっちだったか？
α変換 → 変数名の置き換え
β変換 → 数式の組換え(簡約)
簡約は計算式を簡単化すること
定数値計算の式変形でも言う
β変換の性質を表す Church-Rosserの定理が成り立つ
β変換の経路に関わらず、正規形にたどり着く、という意味(のはず)
ここから任意のラムダ式はもつとすれば1つだけの正規形を持つ
ラムダ式を使って、論理演算、自然数、自然数の演算を定義することが出来る
自然数の表し方はチャーチ数と言われる
再帰関数と似ている
ラムダ計算において、繰り返しは不動点演算子Yによって実現される
全ての帰納関数はラムダ定義可能
逆も成り立つ
計算順序の制御は継続により実現される
あるラムダ式Mの結果を受け取って、続いて評価される残りのラムダ式をMの継続という
不動点演算子Yは、継続にラムダ式の複製を埋め込む役割を果たしている