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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} halts when executed on input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} goes into an infinite loop
• If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} does not halt when executed on input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} halts and outputs 0

What happens if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} is given its own code as input? It should either halt or not halt.

• If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} halts when executed on input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} goes into an infinite loop.
• If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} doesn't halt when executed on input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\mathtt{diag}}} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} of all strings that encode programs and an input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} halts when executed on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
• No program can determine whether a string is in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} or not

More reductions:

• For NP-completeness, we were concerned with the time complexity of problems: reduction from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_1 \le_m L_2} (think Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_2} is at least as hard to compute as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_1}