CSCE 222 Lecture 31

« previous | Wednesday, April 20, 2011 | next »

Undecidability

Limits of computing

Church-Turing Thesis: Anything we reasonably think of as an algorithm can be computed by a Turing Machine (specific formal model)

Short Review of Set Theory

Set of all functions from A to B denoted by B^A

P(A) denotes the power set: a set of all subsets of A (2^|A|)

Two sets have the same cardinality (|A|=|B| iff there exists a bijective function (one-to-one) from A onto B

|A| ≤ |B| iff there exists an injective function from A to B.

|A| < |B| iff there exists an injective function from A to B.

How to Count

• 0 = {}
• 1 = {0} = {{}}
• 2 = {0,1} = { {}, {{}} }

Include all previous sets in the next set

Cantor's Theorem

Let S be any set, then |S|<|P(S)|

Countable Sets

Let N be the set of Natural Numbers

A set is called countable if there exists a surjective function from N to X

Uncountable Sets

The set N^N = {f | f:N→N} is not countable.

Proof: We have |N|<|P(N)| by Cantor's theorem. Since |P(N)|=|2^N| and 2^N is a subset of N^N, we can conclude that $|N|<|P(N)|=|2^{N}|<=|N^{N}|$

Uncomputable functions exist

Consider all programs (e.g. in the Turing Machine model) that compute functions in N^N

The set N^N is uncountable*, and cannot be enumerated. However, the set of all programs can be enumerated (i.e. is countable)

Thus there must exist some functions in N^N that cannot be computed by a program.

* Every program is of finite length (i.e. |N|), which is countable.