- 740 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 23:26:48 ]
- >>731
計算可能な関数には３つの系譜があるようだ。
○ゲーデル〜クリーニ 一般帰納的関数
○チャーチ λ−定義可能な関数
○チューリング チューリングマシンで実行できる関数
ゲーデルの流れだと原始帰納的関数は計算可能関数。
Lispの本の例題に登場するアッカーマン関数は原始帰納的関数ではないのだけど
帰納的関数であり計算可能関数らしい。階乗計算とかフィボナッチ数とかは
原始帰納的関数なんだと思う。詳しい方、間違ってたら補正してください。
