再帰的関数論、再帰理論とも言う

帰納的関数など再帰的な関数を扱う

帰納的関数論の研究分野の4つの大別

「計算」とはなにか

計算不可能性の証明

「計算不能」であることの最も基本的な証明方法が対角線論法

帰納的還元性は計算不能の証明によく用いられる

還元可能性とは別物 #??

計算不可能な関数のクラスの構造

クラスPとかクラスNPなどの階層的な構造の研究

他の数学との関連

参考

『(理論)12 計算モデルの基礎理論』 3章