Undecidable problems: a sampler
Bjorn Poonen · Cambridge University Press eBooks · 2014
Abstract. After discussing two senses in which the notion of undecidability is used, we present a survey of undecidable decision problems arising in various branches of mathemat-ics. 1. Two notions of undecidability There are two common settings in which one speaks of undecidability: 1. Independence from axioms: A single statement is called undecidable if neither it nor its negation can be deduced using the rules of logic from the set of axioms being used. (Example: The continuum hypothesis, that there is no cardinal number strictly between ℵ0 and 2ℵ0, is undecidable in the ZFC axiom system, assuming that ZFC itself is consistent [Göd40, Coh63, Coh64].) The first examples of statements independent of a “natural ” axiom system were constructed by K. Gödel [Göd31]. 2. Decision problem: A family of problems with YES/NO answers is called unde-cidable if there is no algorithm that terminates with the correct answer for every problem in the family. (Example: Hilbert’s tenth problem, to decide whether a mul-tivariable polynomial equation with integer coefficients has a solution in integers, is undecidable [Mat70].) Remark 1.1. In modern literature, the word “undecidability ” is used more commonly in sense 2, given that “independence ” adequately describes sense 1. To make 2 precise, one needs a formal notion of algorithm. Such notions were introduced by A. Church [Chu36a] and A. Turing [Tur36] independently in the 1930s. From now on, we interpret algorithm to mean Turing machine, which, loosely speaking, means that it is a computer program that takes as input a finite string of 0s and 1s. The role of the finite string is to specify which problem in the family is to be solved. Remark 1.2. Often in describing a family of problems, it is more convenient to use higher-level mathematical objects such as polynomials or finite simplicial complexes as input. This is acceptable if these objects can be encoded as finite binary strings. It is not necessary to specify the encoding as long as it is clear that a Turing machine could convert between reasonable encodings imagined by two different readers.