# CSCE 222 Lecture 32

« previous | *Monday, April 25, 2011* | next »

## More about cardinality

iff injective function from *A* to *B*.

### Cantor's Theorem

Function given by is injective, therefore

Claim that there does not exist any surjective function

Indeed, is not contained in

## Countability vs. Uncountability

A set *X* is countable iff

Function is not countable since , which is equivalent to Therefore, the function's cardinality is not countable

## Diagonalization

Given a function that maps an input to a given value, define a function , therefore

## The Halting Problem

Input for Halt program: Program *P* and input *X* for *P*
Output: 1 if *P* terminates (halts) when executed on *X*, and 0 if *P* goes into an infinite loop on input *X*.

**Note:**A compiler is a program that takes as input the code for another program.

*X* could be the program for *P* itself.

What if we call Halt(*P*, *P*) and modify it a little? (diagonalize) This result leads to a paradox and is undecidable.

```
bool halt(Program P, void* Input X)
if (P.run(X).terminates()) return true;
else return false;
}
bool pSelf(Program P) {
return halt(P,P)
}
bool pDiag(Program P) {
if (pSelf(P)) while(true) {}
else return false;
}
```

## ???

If an input from Language 1 returned YES for the Halting problem, than a slight modification (Language 2) must also return YES

**Functional** property: a property that refers to the language accepted by the program and not the specific code of the program.

EX: Program terminates in 10 steps: (not functional); the program accepts 0 or more inputs (functional).

**Nontrivial** property: functional property about programs if some programs have the property and some do not.

### Rice's Theorem

Every nontrivial functional property about programs is undecidable.