Recall that a problem is defined by an infinite set of instances (encoded perhaps as strings of bits) and the correspondence with solutions. I.e. we can solve any problem by enumeration.
A problem is solvable if there is a Turing machine that solves it.
Observation: Any Turing machine can be encoded as a finite string over some finite alphabet.
The encoding of a Turing machine T is called T*.
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