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