目次

1.　簡単なプログラムによる計算の表現
1.1　Nプログラム
1.2　whileプログラム
1.3　Nプログラムとwhileプログラムの表現力
1.4　whileプログラムの第一標準形定理

2.　初等関数とNプログラム
2.1　再帰的定義
2.2　初等関数と初等述語
2.3　初等関数とNプログラム
2.4　自然数列のコード化
2.5　whileプログラムの第二標準形定理
2.6　反復関数と最小解関数

3.　原始再帰的関数と再帰的関数
3.1　原始再帰法と原始再帰的関数
3.2　初等関数と原始再帰的関数
3.3　再帰的関数とNプログラム
3.4　クリーネの標準形定理とその応用

4.　万能関数と再帰定理
4.1　Nプログラムのインタプリタと万能関数
4.2　計算不可能な関数と決定不能な問題
4.3　再帰定理とその応用
4.5　漸化式による関数の定義とその計算可能性について

5.　原始再帰的関数の階層{Fj}
5.1　限定原始再帰法と初等関数
5.2　関数列{hj}
5.3　関数の階層{Fj}
5.4　階層{Fj}と原始再帰的関数
5.5　階層{Fj}と初等関数
5.6　階層{Fj}とアッカーマン関数

6.　loopプログラムと階層{Fj}
6.1　諸定義
6.2　loopプログラムの深さ vs. 計算時間
6.3　階層{Lj}と{Fj}

あとがき
文献
演習問題略解
索引