Slide 1
Undecidability II
Sections 21.4 – 21.7
*
Is There a Pattern?
Does L contain some particular string w?
Does L contain ?
Does L contain any strings at all?
Does L contain all strings over some alphabet ?
A = {
A = {
AANY = {
AALL = {
*
Rice’s Theorem
Any nontrivial property of the SD languages is undecidable.
or
Any language that can be described as:
{
for any nontrivial property P, is not in D.
A nontrivial property is one that is not simply:
True for all languages, or
False for all languages.
*
Applying Rice’s Theorem
To use Rice’s Theorem to show that a language L is not in D we must:
Specify property P.
Show that the domain of P is the SD languages.
Show that P is nontrivial:
P is true of at least one language
P is false of at least one language
*
Examples
1. {
2. {
3. {
4. {
5. {
6. {
7. {
alphabet}.
8. {
9. {
10. {
*
Proof: Let P be any nontrivial property of the SD languages.
H = {
R
(?Oracle) LP = {
Either P() = T or P() = F.
Assume it is P() = F (a matching proof exists if it is T).
Since P is nontrivial, there is some SD language LT such that P(LT) = T. Let MT be a Turing machine that semidecides LT.
Proof of Rice’s Theorem
*
R(
1. Construct
1.1. Copy its input x to another track for later.
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5 Put x back on the tape and run MT on x.
2. Return
C = Oracle(R(
So it is equivalent to MT.
L(M#) = L(MT) and so P(L(M#)) = P(L(MT)) = T.
Oracle decides P. Oracle accepts.
So it accepts nothing.
L(M#) = and so P(L(M#)) = P() = F.
Oracle decides P. Oracle rejects.
Proof (cont’d)
*
Given a TM M, is L(M) Regular?
The problem: Is L(M) regular?
The language: Is LREG = {
Rice’s Theorem says no:
P = True if L is regular and False otherwise.
The domain of P is the set of SD languages since it is the set of languages accepted by some TM.
P is nontrivial:
P(a*) = True.
P(AnBn) = False.
*
Reduction from H
R(
1. Construct the description
1.1. Save x for later.
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Put x back on the tape.
1.6. If x AnBn then accept, else reject.
2. Return
If Oracle decides LREG, then C = Oracle(R(
But no machine to decide H can exist, so neither does Oracle.
*
Without Flipping
R(
1. Construct the description
1.1. If x AnBn then accept, else:
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Accept
2. Return
If Oracle exists, C = Oracle(R(
C is correct: M# immediately accepts all strings AnBn:
But no machine to decide H can exist, so neither does Oracle.
*
Any Nonregular Language Works
R(
1. Construct the description
1.1. If x WW then accept, else:
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Accept
2. Return
If Oracle exists, C = Oracle(R(
C is correct: M# immediately accepts all strings WW:
But no machine to decide H can exist, so neither does Oracle.
*
Is L(M) Context-free?
How about: LCF = {
R(
1. Construct the description
1.1. If x AnBnCn then accept, else:
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Accept
2. Return
*
1. Does P, when running on x, halt?
2. Might P get into an infinite loop on some input?
3. Does P, when running on x, ever output a 0? Or anything at
all?
4. Are P1 and P2 equivalent?
5. Does P, when running on x, ever assign a value to n?
6. Does P ever reach a coding segment S on any input (in other words, can we chop it out?
7. Does P reach S on every input (in other words, can we
guarantee that S happens)?
Practical Implications on Programs
*
Turing Machine Questions Can be Reduced to Program Questions
EqPrograms =
{
We can build, in any programming language PL, SimUM:
that is a PL program
that implements the Universal TM U and so can simulate an arbitrary TM.
*
TM Questions and Program Questions
EqPrograms = {
Theorem: EqPrograms is not in D.
Proof: Reduction from EqTMs = {
R(
1. Build P1, a PL program that, on w, returns SimUM(Ma, w).
2. Build P2, a PL program that, on w, returns SimUM(Mb, w).
3. Return
If Oracle exists and decides EqPrograms, then C = Oracle(R(
decides EqTMs. C is correct. L(P1) = L(Ma) and L(P2) = L(Mb). So:
But no machine to decide EqTMs can exist, so neither does Oracle.
*
{
HANY = {
R
(?Oracle) L2 = {
R(
1. Build
((q1, c1), (q2, c2, d)) and q2 is a halting state other than h, replace that
transition with:
((q1, c1), (h, c2, d)).
2. Return
If Oracle exists, then C = Oracle(R(
R can be implemented as a Turing machine.
C is correct: M# will reach the halting state h iff M would reach some halting state. So:
But no machine to decide HANY can exist, so neither does Oracle.
*
How many Turing machines does it take to change a light bulb?
One.
How can you tell whether your Turing machine is the one?
You can’t.
– Tim Nodine
*
There is an uncountable number of non-SD languages, but only a
countably infinite number of TM’s (hence SD languages).
The class of non-SD languages is much bigger than that of SD languages!
Non-SD Languages
*
Intuition: Non-SD languages usually involve either infinite
search or knowing a TM will go to an infinite loop.
Examples:
H = {
{
{
Proving a language is not in SD:
L is the complement of an SD\D Language.
Recall that L,L SD => L,L D
Reduction from a known non-SD language
Non-SD Languages
*
Theorem: HANY = {
Proof: HANY = HANY =
{
We already know:
HANY is in SD.
HANY is not in D.
So HANY is not in SD because, if it were, then HANY would be in D but it isn’t.
Complement is in SD/D
*
Theorem: If there is a reduction R from L1 to L2 and L1 is
not SD, then L2 is not SD.
So, we must:
Choose a language L1 that is known not to be in SD.
Hypothesize the existence of a semideciding TM Oracle.
Note: R may not swap accept for loop!
Using Reduction
*
H = {
R
(?Oracle) HANY = {
on which TM M halts}
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
Using Reduction for 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 input. It halts on everything or nothing, depending on whether M halts on w. So:
But no machine to semidecide H can exist, so neither does Oracle.
Using Reduction for HANY
*
Aanbn contains strings that look like:
(q00,a00,q01,a00,),
(q00,a01,q00,a10,),
(q00,a10,q01,a01,),
(q00,a11,q01,a10,),
(q01,a00,q00,a01,),
(q01,a01,q01,a10,),
(q01,a10,q01,a11,),
(q01,a11,q11,a01,)
It does not contain strings like aaabbb.
But AnBn does.
Aanbn = {
*
H = {
R
(?Oracle) Aanbn = {
R(
1. Construct the description
1.1 Copy the input x to another track for later.
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Put x back on the tape.
1.6. If x AnBn then accept, else loop.
2. Return
If Oracle exists, C = Oracle(R(
Aanbn = {
*
If
R(
1. Construct the description
1.1. If x AnBn then accept. Else:
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Accept.
2. Return
If Oracle exists, then C = Oracle(R(
M# immediately accepts all strings in AnBn. If M does not halt on
w, those are the only strings M# accepts. If M halts on w,
M# accepts everything:
But no machine to semidecide H can exist, so neither does Oracle.
Aanbn = {
*
H = {
R
(?Oracle) HALL = {
Reduction Attempt 1: 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, C = Oracle(R(
Problem: cannot flip the answer.
HALL = {
*
R(
1. Construct the description
1.1. Copy the input x to another track for later.
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w for |x| steps or until M naturally halts.
1.5. If M naturally halted, then loop.
1.6. Else halt.
2. Return
If Oracle exists, C = Oracle(R(
HALL = {
*
EqTMs = {
We’ve already shown it’s not in D.
Now we show it’s also not in SD.
*
EqTMs = {
H = {
R
(?Oracle) EqTMs = {
R(
1. Construct the description
2. Construct the description
3. Return
If Oracle exists, C = Oracle(R(
*
EqTMs = {
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. Construct the description
1.1 Loop.
3. Return
If Oracle exists, C = Oracle(R(
*
L1 = {
L2 = {
L3 = {
L4 = {
The Details Matter
*
L3 = {
H M L3: R(
1. Construct the description
1.1 Copy the input x to another track for later.
1.2 Erase the tape.
1.3 Write w on the tape.
1.4 Run M on w.
1.5 If x = then accept. Else loop.
2. Return
The Details Matter
*
L4 = {
H M L4: R(
1. Construct the description
1.1 Copy the input x to another track for later.
1.2 Erase the tape.
1.3 Write w on the tape.
1.4 Run M on w for |x| steps or until M naturally halts.
1.5 If M halted naturally, then loop.
1.6 Else accept.
2. Return
The Details Matter
*
Consider :
L1 = {
L2 = {
L3 = {
Accepting, Rejecting, Halting, and Looping
*
{
H = {
R
(?Oracle) {
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 Reject.
2. Return
If Oracle exists, C = Oracle(R(
Problem:
*
If
{
HALL = {
R
(?Oracle) {
R(
1. Construct the description
1.1 Run M on x.
1.2 Reject.
2. Return
If Oracle exists, C = Oracle(R(
No machine to semidecide HALL can exist, so neither does Oracle.
*
What About These?
L1 = {a}.
L2 = {
L3 = {
H M L3: R(
1. Construct the description
1.1 If x = a, accept.
1.2 Erase the tape.
1.2 Write w on the tape.
1.3 Run M on w.
1.4 Accept.
2. Return
*
{
R is a reduction from H. R(
1. Construct the description of M#(x) that operates as follows:
1.1. Erase the tape.
1.2. Write w.
1.3. Run M on w.
1.4. Accept.
2. Construct the description of M?(x) that operates as follows:
2.1. Accept.
3. Return
If Oracle exists and semidecides L, C = Oracle(R(
semidecides H: M? accepts everything, including . So:
*
The Problem View The Language View Status
Does TM M have an even number of states? {
states} D
Does TM M halt on w? H = {
Does TM M halt on the empty tape? H = {
Is there any string on which TM M halts? HANY = {
Does TM M halt on all strings? HALL = {
Does TM M accept w? A = {
Does TM M accept ? A = {
Is there any string that TM M accepts? AANY {
*
Does TM M accept all strings? AALL = {
Do TMs Ma and Mb accept the same languages? EqTMs = {
Does TM M not halt on any string? HANY = {
Does TM M not halt on its own description? {
Is the language that TM M accepts regular? TMreg = {
Does TM M accept the language AnBn? Aanbn = {
*
IN SD OUT
Semideciding TM H Reduction
Enumerable
D
Deciding TM AnBnCn Diagonalize
Lexico. enum Reduction
L and L in SD
Context-Free
CF grammar AnBn Pumping
PDA Closure
Closure
Regular
Regular Expression a*b* Pumping
FSM Closure
Language Summary
*