『計算可能性入門』

1980年出版てことでビビってたが、普通に親切でわかりやすい本だった

1章 アルゴリズム

2章 RAM

3章 計算可能性部分関数、決定可能集合、決定可能述語

4章 万能プログラム

5章 計算不能部分関数、決定不能集合、決定不能述語

6章 再帰定理とその応用

7章 枚挙可能集合と枚挙可能述語

8章 語の問題

9章 帰納的関数

10章 Turing機械