Solvable Problems

 

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*.

 

Unsolvable Problems

 

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.

 

** (believe me!)


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