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