Some Unsolvable Problems

In Chapter 1.9 we have proved that the halting problem and the self applicability problem for φ are (recursively) unsolvable (Theorem 1.9.16(2)). In Part 2 of this book several other problems which can be derived from φ will be shown to be unsolvable, and we shall study “degrees of unsolvability”. The discussion at the end of Chapter 1.9 indicates that there are fundamental applications of recursion theory in logic. A special chapter in Part 2 will be devoted to some of these questions. In this chapter some decision problems from other parts of mathematics will be considered. A decision problem is defined by a set M and a subset $$ {M_o} \subseteq M. $$. The problem is to decide for any m ∈ M whether m belongs to M_o or not. In the case of the halting problem M = ℕ and M_o = K_φo. If M is not a set of the numbers or of the words over some alphabet then it is not clear what “decide” means. In this case more information has to be supplied to specify the decision problem. Usually a notation ν of M, i.e. a surjective function ν : W(∑)→M, is given. Also a numbering ν : ℕ→M could be used. W.l.g. we consider the case of a notation here. By Theorem 1.8.9 both approaches yield the same decidability results.