CSCE 411 Lecture 35

Lecture Slides

« previous | Monday, November 19, 2012 | next »

Cardinality

Alternate Proof of Uncountability

Seeking a contradiction, assume $f:\mathbb {N} \to \mathbb {N}$ is countable.

Enumerate these function $f_{0}$, $f_{1}$, etc.

Obtain contradiction by defining $f^{d}$ using "diagonalization" that should be in set, but is not equal to any $f_{i}$'s: Let $f^{d}(n)=f_{n}(n)+1$.

The Halting Problem

Consider a function halt:

• input: code for program $P$ and an input $x$ for $P$
• output: 1 if $P$ terminates (halts) when executed on input $x$ and 0 if $P$ doesn't terminate (goes into an infinite loop) when executed on input $x$

By the way, a compiler is a program that takes as input the code for another program.

This problem would be the ultimate debugging tool of all time!, but... what if we give halt itself?

View halt as a function from $\mathbb {N}$ to $\mathbb {N}$:

• $P$ and $x$ can be represented in ASCII, which is a string of bits
• Any string of bits can be interpreted as a natural number.

Suppose there is a program $P_{\mathtt {halt}}$ that computes halt.

Use $P_{\mathtt {halt}}$ as a subroutine in another program $P_{\mathtt {self}}$:

• input: code for any program $P$
• constructs pair $(P,P)$ and calls $P_{\mathtt {halt}}$ on $(P,P)$
• returns same answer as $P_{\mathtt {halt}}$.

Use $P_{\mathtt {self}}$ as subroutine in another program $P_{\mathtt {diag}}$:

• input: code for any program $P$
• call $P_{\mathtt {self}}$ on $P$
• if $P_{\mathtt {self}}$ returns 1 (i.e. does not go into an infinite loop), then go into an infinite loop.
• if $P_{\mathtt {self}}$ returns 0 (i.e. goes into an infinite loop), then output 0.

In effect, $P_{\mathtt {diag}}$ does the opposite of what program $P$ does on input $P$:

• If $P$ halts when executed on input $P$, then $P_{\mathtt {diag}}$ goes into an infinite loop
• If $P$ does not halt when executed on input $P$, then $P_{\mathtt {diag}}$ halts and outputs 0

What happens if $P_{\mathtt {diag}}$ is given its own code as input? It should either halt or not halt.

• If $P_{\mathtt {diag}}$ halts when executed on input $P_{\mathtt {diag}}$, then $P_{\mathtt {diag}}$ goes into an infinite loop.
• If $P_{\mathtt {diag}}$ doesn't halt when executed on input $P_{\mathtt {diag}}$, then $P_{\mathtt {diag}}$ halts.

contradiction!

What went wrong? Our assumption that there is an algorithm to compute halt was incorrect.

Undecidability

Analog of uncomputable function is an undecidable set.

Theory of what can and can't be computed focuses on identifying strings:

• algorithm is required to "decide" if a gived input string is in the set of interest
• similar to deciding if the input to some NPC problem is a YES or NO instance

Formal language is set of strings, assuming some encoding.

• Analogous to halt is set $H$ of all strings that encode programs and an input $X$ such that $P$ halts when executed on $X$
• No program can determine whether a string is in $H$ or not

More reductions:

• For NP-completeness, we were concerned with the time complexity of problems: reduction from $P_{1}$ to $P_{2}$ had to be in poly time
• now concerned with computability of problems: reduction just has to be computable, no matter how slow it is.

Many-One Reduction

Similar to NPC reductions:

• YES map to YES
• NO map to NO
• computable
• notation: $L_{1}\leq _{m}L_{2}$ (think $L_{2}$ is at least as hard to compute as $L_{1}$