Slide 1
Undecidability
Sections 21.1 – 21.3
*
Problems / Languages
The Problem View The Language View
Does TM M halt on w? H = {
M halts on w}
Does TM M not halt on w? H = {
M does not halt on w}
Does TM M halt on the empty tape? H = {
Is there any string on which TM M halts? HANY = {
Does TM M accept all strings? AALL = {
Do TMs Ma and Mb accept the same languages? EqTMs = {
Is the language that TM M accepts regular? TMREG = {
Reduction
Example: Computing a function
multiply(x, y) =
1. answer := 0.
2. For i := 1 to y do:
answer = sum(answer + x).
3. Return answer.
Computing multiply reduces to computing sum.
or
If we can do sum then we can do multiply.
Using Reduction for Undecidability
Theorem: There exists no general procedure to solve the following
problem:
Given an angle A, divide A into sixths using only a straightedge and a compass.
Proof: Suppose that there were such a procedure, which we’ll call
sixth. Then we could trisect an arbitrary angle:
trisect(a: angle) =
1. Divide a into six equal parts by invoking sixth(a).
2. Ignore every other line, thus dividing a into thirds.
trisect(a)
sixth(a) ignore lines
sixth exists trisect exists.
But we know that trisect does not exist. So, sixth cannot exist either.
Turing Reduction
A reduction R from L1 to L2 is one or more Turing
machines such that:
If there exists a Turing machine Oracle that decides (or
semidecides) L2, then the Turing machines in R can be
composed with Oracle to build a deciding (or a
semideciding) Turing machine for L1.
L1 L2 means that L1 is reducible to L2.
Assume:
(L1 L2 ) (L2 is in D) (L1 is in D)
If (L1 is in D) is false, then at least one of the two antecedents of that implication must be false. So:
If (L1 L2) is true,
then (L2 is in D) must be false.
Using Reduction for Undecidability
Showing that L2 is not in D:
L1 (known not to be in D) L1 in D But L1 not in D
R
L2 (a new language whose if L2 in D So L2 not in D
decidability we are
trying to determine)
Using Reduction for Undecidability
L1
L2
Hard
(known)
“hard” = difficult,
e.g., not in D or SD
Harder
(unknown)
“harder” = more difficult,
because L1 reduces to it
(may be equally difficult)
0. Assume Oracle that decides L2 exists
1. Choose a language L1:
that is already known not to be in D, and
that can be reduced to L2.
2. Define the reduction R.
3. Describe the composition C of R with Oracle:
C(x) = Oracle(R(x))
4. Show that C does correctly decide L1 if Oracle exists. We
do this by showing:
R can be implemented by Turing machines,
C is correct:
If x L1, then C(x) accepts, and
If x L1, then C(x) rejects.
To Use Reduction for Undecidability
Mapping Reductions
L1 is mapping reducible to L2 (L1 M L2) iff there exists
some computable function f such that:
x* (x L1 f(x) L2).
To decide whether x is in L1, we transform it, using f,
into a new object and ask whether that object is in L2.
Note: mapping reduction is a particular case of Turing reduction.
H is in SD. T semidecides it:
T(
1. Run M on .
2. Accept.
T accepts
H = {
Theorem: H = {
Proof: by reduction from H:
H = {
R
(?Oracle) H = {
R is a mapping reduction from H to H:
R(
1. Construct
1.1. Erase the tape (ignore its input)
1.2. Write w on the tape.
1.3. Run M on w.
2. Return
H = {
R(
1. Construct
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
2. Return
If Oracle exists, C = Oracle(R(
C is correct: M# ignores its own input. It halts on everything or nothing. So:
Proof, Continued
A Block Diagram of C
R must construct
M# will be:
So the procedure for constructing M# is:
1. Write:
2. For each character x in w do:
2.1. Write x.
2.2. If x is not the last character in w, write R.
3. Write Lq M.
R Can Be Implemented as a Turing Machine
R can be implemented as a Turing machine.
C is correct.
So, if Oracle exists:
C = Oracle(R(
But no machine to decide H can exist.
So neither does Oracle.
Conclusion
If we could decide whether M halts on the specific string , we
could solve the more general problem of deciding whether M
halts on an arbitrary input.
Clearly, the other way around is true: If we could solve H we
could decide whether M halts on any one particular string.
But doing a reduction in that direction would tell us nothing
about whether H was decidable.
The significant thing that we just saw in this proof is that there
also exists a reduction in the direction that does tell us that H is
not decidable.
We proved that H is “harder” than H. Clearly, H is also “harder” than H (H is a subproblem of H), so they are equally “hard”.
This Result is Somewhat Surprising
A clear declaration of the reduction “from” and “to” languages.
A clear description of R.
If R is doing anything nontrivial, argue that it can be implemented as a TM.
Run through the logic that demonstrates how the “from” language is being decided by the composition of R and Oracle. You must do both accepting and rejecting cases.
Declare that the reduction proves that your “to” language is not in D.
Important Elements in a Reduction Proof
Right way: to show that L2 is not in D:
Reduce a known hard one, L1, to L2: L1 L2
Given that L1 is not in D,
Reduce L1 to L2, i.e., show how to solve L1
(the known one) in terms of L2 (the unknown one)
Wrong way: reduce L2 (the unknown one) to L1 (the known hard):
Example (wrong):
If there exists a machine MH that solves H, then we could build a
machine that solves H as follows:
1. Return (MH(
This proves nothing. It’s an argument of the form:
If False then …
(We show that a known hard one is harder than our language …)
The Most Common Mistake:
Doing the Reduction Backwards
Theorem: HANY is in SD.
Proof: by exhibiting a TM T that semidecides it.
What about simply trying all the strings in * one at a time
until one halts?
HANY = {
T(
1. Use dovetailing to try M on all of the elements of *:
[1]
[2] a [1]
[3] a [2] b [1]
[4] a [3] b [2] aa [1]
[5] a [4] b [3] aa [2] ab [1]
2. If any instance of M halts, halt and accept.
T will accept iff M halts on at least one string. So T
semidecides HANY.
HANY is in SD
H = {
R
(?Oracle) HANY = {
R(
1. Construct
1.1. Examine x.
1.2. If x = w, run M on w, else loop.
2. Return
If Oracle exists, then C = Oracle(R(
R can be implemented as a Turing machine.
C is correct: The only string on which M# can halt is w. So:
But no machine to decide H can exist, so neither does Oracle.
HANY is not in D
HANY is not in D: another reduction
Proof: We show that HANY is not in D by reduction from H:
H = {
R
(?Oracle) HANY = {
R(
1. Construct the description
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
2. Return
If Oracle exists, then C = Oracle(R(
C is correct: M# ignores its own input. It halts on everything or nothing. So:
But no machine to decide H can exist, so neither does Oracle.
Assume Oracle exists.
Choose an undecidable language to reduce from.
Define the reduction R.
Show that C (the composition of R with Oracle) is correct.
The Steps in a Reduction Proof
We show that HALL is not in D by reduction from H.
H = {
R
(?Oracle) HALL = {
R(
1. Construct the description
1.1. Erase the tape.
1.2. Run M.
2. Return
If Oracle exists, then C = Oracle(R(
R can be implemented as a Turing machine.
C is correct: M# halts on everything or nothing, depending on whether M halts on . So:
But no machine to decide H can exist, so neither does Oracle.
HALL = {
We next define a new language:
A = {
Note that A is different from H since it is possible that M
halts but does not accept. An alternative definition of A is:
A = {
The Membership Question for TMs
We show that A is not in D by reduction from H.
H = {
R
(?Oracle) A = {
R(
1. Construct the description
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept
2. Return
If Oracle exists, then C = Oracle(R(
R can be implemented as a Turing machine.
C is correct: M# accepts everything or nothing. So:
But no machine to decide H can exist, so neither does Oracle.
A = {
Theorem: A = {
Proof: Analogous to that for H.
Theorem: AANY = {
Proof: Analogous to that for HANY.
Theorem: AALL = {
Proof: Analogous to that for HALL.
A, AANY, and AALL
AALL = {
R
(Oracle) EqTMs = {
R(
1. Construct the description of M#(x):
1.1. Accept. (M# accepts everything)
2. Return
If Oracle exists, then C = Oracle(R(
C is correct: M# accepts everything. So if L(M) = L(M#), M must also accept everything. So:
But no machine to decide AALL can exist, so neither does Oracle.
EqTMs={
Recall that a mapping reduction from L1 to L2 is a computable function f where:
x* (x L1 f(x) L2).
When we use a mapping reduction, we return:
Oracle(f(x))
Sometimes we need a more general ability to use Oracle
as a subroutine and then to do other computations after it
returns.
Sometimes Mapping Reducibility Isn’t Right
H = {< M, w> : TM M halts on input string w}
R
(?Oracle) L2 = {
R(
1. Construct the description
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Return
If Oracle exists, then C = Oracle(R(
C is correct: M# ignores its own input. It accepts everything or nothing, depending on whether it makes it to step 1.4. So:
Problem:
{
H = {< M, w> : TM M halts on input string w}
R
(?Oracle) L2 = {
R(
1. Construct the description
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Return
If Oracle exists, then C = Oracle(R(
R and can be implemented as Turing machines.
C is correct:
But no machine to decide H can exist, so neither does Oracle.
{
L = {
Are All Questions about TMs Undecidable?
L = {
Lq = {