By looking at the cardinality of sets, we find that

1. The number of Turing machines is countable (same as the number of integers).
2. The number of problems is uncountable (same as the number of real numbers).

Hence there are far more problems than there are Turing machines to solve them.

We must conclude that there exist unsolvable problems.

We will present some actual examples of unsolvable problems, not just demonstrate their existence.

CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000