CS计算机代考程序代写 Slide 1

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 = { : TM M accepts w}.
A = { : TM M accepts }.
AANY = { : there exists at least one string that TM M accepts}.
AALL = { : TM M accepts all inputs}.

Rice’s Theorem
Any nontrivial property of the SD languages is undecidable.

Any language that can be described as:

{: P(L(M)) = True}

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. { : L(M) contains only even length strings}.
2. { : L(M) contains an odd number of strings}.
3. { : L(M) contains all strings that start with a}.
4. { : L(M) is infinite}.
5. { : L(M) is regular}.
6. { : M contains an even number of states}.
7. { : M has an odd number of symbols in its tape
alphabet}.
8. { : M accepts  within 100 steps}.
9. {: M accepts }.
10. { : L(Ma) = L(Mb)}.

Proof: Let P be any nontrivial property of the SD languages.

H = { : TM M halts on input string w}

(?Oracle) LP = { : P(L(M)) = T }

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 , so M#(x) operates as follows:
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()) decides H:
 H: M halts on w. M# makes it to 1.5.
So it is equivalent to MT.
L(M#) = L(MT) and so P(L(M#)) = P(L(MT)) = T.
Oracle decides P. Oracle accepts.
 H: M does not halt on w. M# gets stuck in 1.4.
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 = { : L(M) is regular} in D?

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 , where M#(x) operates as follows:
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()) decides H:
 H: M# makes it to step 1.5. Then it accepts x iff x  AnBn. So M# accepts AnBn, which is not regular. Oracle rejects. C accepts.
 H: M does not halt on w. M# gets stuck in step 1.4. It accepts nothing. L(M#) = , which is regular. Oracle accepts. C rejects.

But no machine to decide H can exist, so neither does Oracle.

Without Flipping
R() =
1. Construct the description , where M#(x) operates as follows:
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()) decides H:
C is correct: M# immediately accepts all strings AnBn:
 H: M# accepts everything else in step 1.5. So L(M#) = *, which is regular. Oracle accepts.
 H: M# gets stuck in step 1.4, so it accepts nothing else. L(M#) = AnBn, which is not regular. Oracle rejects.

But no machine to decide H can exist, so neither does Oracle.

Any Nonregular Language Works
R() =
1. Construct the description , where M#(x) operates as follows:
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()) decides H:
C is correct: M# immediately accepts all strings WW:
 H: M# accepts everything else in step 1.5. So L(M#) = *, which is regular. Oracle accepts.
 H: M# gets stuck in step 1.4, so it accepts nothing else. L(M#) = WW, which is not regular. Oracle rejects.

But no machine to decide H can exist, so neither does Oracle.

Is L(M) Context-free?

How about: LCF = { : L(M) is context-free}?
R() =
1. Construct the description , where M#(x) operates as follows:
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 =

{ : Pa and Pb are PL programs and L(Pa) = L(Pb)}.

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 = { : Pa and Pb are PL programs and L(Pa) = L(Pb)}.

Theorem: EqPrograms is not in D.

Proof: Reduction from EqTMs = { : L(Ma) = L(Mb)}.

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:

 EqTMs: L(Ma) = L(Mb). So L(P1) = L(P2). Oracle() accepts.
 EqTMs: L(Ma)  L(Mb). So L(P1)  L(P2). Oracle() rejects.

But no machine to decide EqTMs can exist, so neither does Oracle.

{ : M reaches q on some input}
HANY = { : there exists some string on which TM M halts}

(?Oracle) L2 = { : M reaches q on some input}

R() =
1. Build so that M# is identical to M except that, if M has a transition
((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()) decides HANY:
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:
 HANY: There is some string on which M halts. So there is some string on which M# reaches state h. Oracle accepts.
 HANY: There is no string on which M halts. So there is no string on which M# reaches state h. Oracle rejects.

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 = { : TM M does not halt on w}.
{ : L(M) = *}.
{ : TM M halts on nothing}.

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: HANY = { : there does not exist any string on which TM M halts} is not in SD.

Proof: HANY = HANY =
{ : there exists at least one string on which TM M halts}.

We already know:
HANY is in SD.
HANY is not in D.

So HANY 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 = { : TM M does not halt on input string w}

(?Oracle) HANY = { : there does not exist a string
on which TM M halts}
R() =
1. Construct the description of M#(x):
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
2. Return .
Using Reduction for HANY

R() =
1. Construct the description of M#(x):
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()) semidecides H:
C is correct: M# ignores its input. It halts on everything or nothing, depending on whether M halts on w. So:
 H: M does not halt on w, so M# halts on nothing. Oracle accepts.
 H: M halts on w, so M# halts on everything. Oracle does not accept.

But no machine to semidecide H can exist, so neither does Oracle.
Using Reduction for HANY

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 = { : L(M) = AnBn}

H = { : TM M does not halt on w}

(?Oracle) Aanbn = { : L(M) = AnBn}

R() =
1. Construct the description , where M#(x) operates as follows:
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()) semidecides H: !?!?
Aanbn = { : L(M) = AnBn} is not SD

*
If is in H, L(M#) = . If is not in H, L(M#) is AnBn. So Oracle gets it backwards.

R() reduces H to Aanbn:
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()) semidecides H:
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:
 H: M does not halt on w, so M# accepts strings in AnBn in step 1.1. Then it gets stuck in step 1.4, so it accepts nothing else. It is an AnBn acceptor. Oracle accepts.
 H: M halts on w, so M# accepts everything. Oracle does not accept.

But no machine to semidecide H can exist, so neither does Oracle.
Aanbn = { : L(M) = AnBn} is not SD

H = { : TM M does not halt on w}
R

(?Oracle) HALL = { : TM halts on *}

Reduction Attempt 1: R() =
1. Construct the description , where M#(x) operates as follows:
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()) semidecides H:
 H: M does not halt on w, so M# gets stuck in step 1.3 and halts on nothing. Oracle does not accept.
 H: M halts on w, so M# halts on everything. Oracle accepts.

Problem: cannot flip the answer.
HALL = { : TM halts on *}

R() reduces H to HALL:
1. Construct the description , where M#(x) operates as follows:
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()) semidecides H:
 H: No matter how long x is, M will not halt in |x| steps. So, for all inputs x, M# makes it to step 1.6. So it halts on everything. Oracle accepts.
 H: M halts on w in n steps. On inputs of length less than n, M# makes it to step 1.6 and halts. But on all inputs of length n or greater, M# will loop in step 1.5. Oracle does not accept.

HALL = { : TM halts on *}

EqTMs = { : L(Ma) = L(Mb)}
We’ve already shown it’s not in D.

Now we show it’s also not in SD.

EqTMs = { : L(Ma) = L(Mb)}
H = { : TM M does not halt on w}
R

(?Oracle) EqTMs = { : L(Ma) = L(Mb)}

R() =
1. Construct the description :

2. Construct the description :

3. Return .

If Oracle exists, C = Oracle(R()) semidecides H:
 H:
 H:

EqTMs = { : L(Ma) = L(Mb)}
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()) semidecides H: M? halts on nothing.
 H: M does not halt on w, so M# gets stuck in step 1.3 and halts on nothing. Oracle accepts.
 H: M halts on w, so M# halts on everything. Oracle does not accept.

L1 = {: M has an even number of states}.

L2 = {: || is even}.

L3 = {: |L(M)| is even}.

L4 = {: M accepts all even length strings}.
The Details Matter

L3 = {: |L(M)| is even}.

H M L3: R() =
1. Construct the description , where M#(x) operates as follows:
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 .

 H:
 H:

The Details Matter

L4 = {: M accepts all even length strings}

H M L4: R() =
1. Construct the description , where M#(x) operates as follows:
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 .

 H:
 H:

The Details Matter

Consider :

L1 = {: M rejects w}.

L2 = {: M does not halt on w} (H)

L3 = {: M is a deciding TM and rejects w}.
Accepting, Rejecting, Halting, and Looping

{: M is a Deciding TM and Rejects w}
H = { : TM M does not halt on w}
R

(?Oracle) {: M is a deciding TM and rejects w}

R() =
1. Construct the description , where M#(x) operates as follows:
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()) semidecides H:
 H:
 H:

Problem:

*
If  H, then M# isn’t a decider. So Oracle fails to accept.

{: M is a Deciding TM and Rejects w}
HALL = { : TM M halts on *}
R

(?Oracle) {: M is a deciding TM and rejects w}

R() =
1. Construct the description , where M#(x) operates as follows:
1.1 Run M on x.
1.2 Reject.
2. Return .

If Oracle exists, C = Oracle(R()) semidecides HALL:
 HALL: M# halts and rejects all inputs. Oracle accepts.
 HALL: There is at least one input on which M doesn’t halt. So M# is not a deciding TM. Oracle does not accept.

No machine to semidecide HALL can exist, so neither does Oracle.

What About These?
L1 = {a}.

L2 = { : M accepts a}.

L3 = { : L(M) = {a}}.

H M L3: R() =
1. Construct the description , where M#(x) operates as follows:
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 .

 H:
 H:

*
 H: L(M#) = {a}.
 H: L(M#) = *.

{ :   L(Ma) – L(Mb)}
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:

 H: L(M?) – L(M#) =

 H: L(M?) – L(M#) =

*
 H: L(M?) – L(M#) = * –  = *.
 H: L(M?) – L(M#) = * – *= .

The Problem View The Language View Status
Does TM M have an even number of states? { : M has an even number of
states} D
Does TM M halt on w? H = { : M halts on w} SD/D
Does TM M halt on the empty tape? H = { : M halts on } SD/D
Is there any string on which TM M halts? HANY = { : there exists at least one string on which TM M halts } SD/D
Does TM M halt on all strings? HALL = { : M halts on *} SD
Does TM M accept w? A = { : M accepts w} SD/D
Does TM M accept ? A = { : M accepts } SD/D
Is there any string that TM M accepts? AANY { : there exists at least one string that TM M accepts } SD/D

Does TM M accept all strings? AALL = { : L(M) = *} SD
Do TMs Ma and Mb accept the same languages? EqTMs = { : L(Ma) = L(Mb)} SD

Does TM M not halt on any string? HANY = { : there does not exist any string on which M halts} SD
Does TM M not halt on its own description? { : TM M does not halt on input } SD
Is the language that TM M accepts regular? TMreg = { : L(M) is regular} SD
Does TM M accept the language AnBn? Aanbn = { : L(M) = AnBn} SD

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

Related Posts