帰納的関数の入門から、ゲーデルの不完全性定理や、 ヒルベルトの第 10 問題の証明までを述べる。
当たり前だが、難しい。 ヒルベルトの第10 問題を解いた数学者、マチャセビッチが Матиясевич と綴られていることからして、難しい。
ヒルベルトの第10問題とは次の通りである。
任意個数の未知数を含んだ有理整数を係数とする不定方程式が，
有理整数の解をもつか否かを有限回の演算で判定する一般的な方法を見つけよ
この問題に対しては、否定的に解決されると予想され、事実 Матиясевич が否定的解決を証明している。
原始帰納的関数の例 2.6 は次のようになっている。
`a ∸ b` を，
`a ∸ b = {(a-b, a ge 0, のとき),(0, a lt b, のとき ):}`
なる関数とする．
`{(a ∸ 0 = a), (a ∸ b' = pd(a∸b)):}`
これを最初見たときに、`a ∸ b` の説明にまだ使っていない `a - b` を使っているのはおかしいと思った。 しかし、これは意味での話で実際の定義は次の式だということで納得したのだった。
それから、同じく例 2.16 で、`j(a,b)` を次の定義式による関数とする、という例が出ている。
`j(a,b) = [(a+b)(a + b 1)//2] + a`
が定義されている。ちなみに、`[a // b]` は前の例2.17 で定義されている。
（この関数 `j` は `NN xx NN` から `NN` の上への１対１写像となることから，しばしば，対関数（pairing function）とよばれる）
このページの数式は MathJax で記述している。
| 書名 | 帰納的関数 |
| 著者 | 廣瀬 健 |
| 発行日 | 1989 年 2 月 1 日 |
| 発行元 | 共立出版 |
| 定価 | 3600 円（本体） |
| サイズ | A5 判 211 ページ |
| ISBN | 4-320-01120-1 |
まりんきょ学問所 ＞ 数学の部屋 ＞ 数学の本 ＞ 廣瀬 健：帰納的関数
