# 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

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