内容
帰納的関数や帰納的述語の概念は、1930年代に、ゲーデルの不完全性定理における算術化の手法や古来からある決定手続き、あるいは計算可能関数についての思考実験など、いわゆる“アルゴリズム”の概念と関わって登場した。そして、帰納的関数の理論は、数学や情報科学におけるさまざまな理論と、きわめて多くの接点をもった分野である。本書は、帰納的関数の理論の本格的な入門書である。
まず、帰納的関数の数学基礎論における立場について述べる。次に、帰納的関数と帰納的述語の基本的性質を示し、後に用いられる具体的な帰納的関数や帰納的述語をあげる。そして、ゲーデルの原論文に沿った形で不完全性定理の証明と解説を行う。さらに、ある形式的体系を定義し、その体系で形式的に計算可能な関数のクラスを定める。その後で、算術的階層の様子を調べ、また“決定不可能次数の理論”について基本的結果を紹介する。そして最後に、決定問題についての概略を説明し、“ヒルベルトの第10問題”について、その否定的解決に至るまでの歴史的経緯を詳しく解説する。
『共立講座 現代の数学3 帰納的関数』として1989年初版発行後、以来、長年にわたり多数の読者にご愛読いただいてまいりました。この度、多くの読者からの要望を受け単行本に改装し発行するものです。
