CSCE 222 Lecture 32

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

More about cardinality

$|A|\leq |B|$ iff injective function from A to B.

Cantor's Theorem

$|S|<|P(S)|$

Function $i:S\to P(S)$ given by $i(s)=\{s\}$ is injective, therefore $|S|\leq |P(S)|$

Claim that there does not exist any surjective function $f:S\to P(S)$

Indeed, $T=\{s\in S:s\notin f(s)\}$ is not contained in $f(S)$

Countability vs. Uncountability

A set X is countable iff $|X|\leq |\mathbb {N} |$

Function $f:\mathbb {N} \to \mathbb {N}$ is not countable since $|\mathbb {N} |<|P(\mathbb {N} )|$, which is equivalent to $|\mathbb {N} |<|2^{\mathbb {N} }|$ Therefore, the function's cardinality is not countable

Diagonalization

Given a function that maps an input to a given value, define a function $f^{d}(n)=f_{n}(n)+1$, therefore $f^{d}(n)\neq f_{n}(n)$

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.