L {<M,s> : s ∈ L(M), |L(M)| = 2}. Prove that L ∉ SD by a reduction from ¬H}

Busy week

• Lab 9 due Thursday at 5 pm: L = { <M,s> : s ∈ L(M) and |L(M)| % 2 = 0}. For example, suppose that L(M) = {aa}. Then <M,aa> ∉ L because |L(M)| = 1, 1 % 2 = 1; If L(M) {a,aaa} then <M,ℇ> ∉ L because ℇ ∉ L(M), but <M,aaa> ∈ L. Prove that L ∉ D by reduction from H.

Your proof could implement R, the mapping reduction function, as a Java or Python program in the form demonstrated, which allows the user to configure whether M halts on w.

We start the proof by creating R. We start are by thinking of the input to ouput. What's the input to the function R? Remember that R is a mapping reduction from H to L. So the input to R must be something that could be in H. <M,w> has the correct syntactic form. Could R return this: <M#,aaa>? think of terms of whether the output of R could possible be in L.

R(<M,w>) = 1. Define M#:

1.a

1.x Run M on w

2. Return M#,aaa>

M halts on w, <M#,aaa> is in L. So if you make it through step 1.x, then M#,aaa satisfies the characteristic function of L. and if M does not halt on w, <M#,aaa> is not in L. If you don't get through 1.x, then you lack some component of the characteristic function.

• Online Pumping Theorem workshop Thursday at 9 pm: (10 extra credit points for full participation)

• Lab 10 due Monday at noon: L {<M,s> : s ∈ L(M), |L(M)| = 2}. Prove that L ∉ SD by a reduction from ¬H}

• HW #3 due Friday May 8 at 2 pm.

• Midterm #3 Tuesday May 12

Rice Theorem and Semidecidability Page 1

Rice's Theorem and Semidecidability Mapping Reducibility

Recall that a mapping reduction function ƒ transforms an L₁ membership question into an L₂ membership question:

∀x∈Σ* (x ∈ L₁ iff ƒ(x) ∈ L₂)

H = { <M,w> : M halts on w>

Hε = {<M> : M halts on ε}. That is the strings in the language Hε are encodings of TMs such tht the encoded TM halts when started on an empty input tape.

if H ≤M Hε then if Hε ∈ D then H ∈ D; But we know that H is not decidable. And so by applying the modus tollens logic rule to the implicaion, Hε ∉ D If there's a target langauge that we want to show is not decidable, than we show that by showing that a not decidable langauge, like H, is mapping reducible to the target language.

It seems more natural to go in the other direction, H ≤M Hε: Reduce the problem of whether you can decide if M will halt on some particular string to, whether you can decide if M will halt on any string. But we already know that H ∈ SD/D, and we are using that knowlege to prove something about Hε.

This proof is confusing at first because it uses two languages, H and Hε, five different TMs, and two string variables:

TM 1: Mₒ (the "Oracle"), the hypothetical machine that could decide Hε. It may be helpful to think of it as a source code analyzer, which claims to be able to inspect any high-level TM description and tell whether the machine would be an element of the target language.

TM 2: R, which implements the mapping reduction function from H to Hℇ: <M,w> → <M#>. Note well: R maps <M,w>, a TM/string pair which has correct syntax for an element of H, to <M#>,which has correct syntax for an element Hε. Compare this with ƒ in the definition of a mapping reduction function. ∀x∈Σ* (x ∈ L₁ iff ƒ(x) ∈ L₂

R(<M,w>): i. Define M#(x) i.a Simulates M on w i.b Enter a halting state ii. Return <M#>

TM 3: M# The TM created by the mapping reduction function R. Note that M# is analyzed by Mₒ, but never run. This can be a very confusing point.l

TM 4: C is short for Composition, Mₒ + R. C = Mₒ(R<M,w>) = Mₒ(<M#>). Mₒ, which hypothetically can decide Hε, decides if the output of R is in Hε. If Mₒ could do that, it could also decide H.

TM 5: M The TM encoded as the first part of the <M,w> pair, the input to R that has the correct syntax for an element of H. It has no necessary relation to M#.

Rice Theorem and Semidecidability Page 2

String 1: w The second part of the <M,w> pair. Could be any string in ∑*.

String 2: x The contents of the M# input tape. Could be any string in ∑*. x has no necessary relationship to w.

H = { <M,w> : M halts on w>

Hε = {<M> : M halts on ε}. That is the strings in the language Hε are encodings of TMs such tht the encoded TM halts when started on an empty input tape.

R is a mapping reduction from H to H_e.

R(<M,w>): i. Define M#(x) i.a Simulates M on w i.b Enter a halting state ii. Return <M#>

if there were an Oracle Mₒ that could decide H_e, then Mₒ(M#) could decide H.

• <M,w> is in H: Mₒ accept/reject M#, and why? What would M# do if M halts on w? 
 M# would proceed directly to i.b and halt. So, if M halts on w, M# halts on everything. Everything includes epsilon, so Mo accepts M# so because M# halts on epsilon.

R(<M,w>): i. Define M#(x) i.a Simulates M on w i.b Enter a halting state ii. Return <M#>

• <M,w> is not in H:

i. Define M#(x) i.a Simulates M on w -- loops forever, and never gets to 1.b i.b Enter a halting state ii. Return <M#>

in this case what happens when x = epsilon. Will M# halt or not?

However, no TM could decide H, so a TM such as Mₒ could not possible exist.

Rice Theorem and Semidecidability Page 3

C++

Sometimes C needs to do a little more work to use the verdict of Mₒ to decide H.

Consider L₂ = { <M> : M accepts no even length string}, and this proof using a reduction from H to try to show that L₂ ∉ D.

R(<M, w>) = 1. Construct the description M#: 1.1. Erase the tape. 1.2. Write w on the tape. 1.3. Run M on w. 1.4. Accept. 2. Return <M#>

If Mₒ exists, then C = Mₒ(R(<M, w>)) = Mₒ(<M#>) decides H:

• <M, w> ∈ H: M halts on w. L(M#) = ∑*; ∑* contains an infinite number of even length strings, so Mₒ which can somehow tell if L(M) contains any even length strings, would reject.

• <M, w> ∉ H: M does not halt on w. L(M#) = Ø, and Ø contains no even length so Mₒ accepts. 
 The problem is that ¬C= ¬ Mₒ(<M#>) decides H: We need to invert the verdict of Mₒ.

Rice Theorem and Semidecidability Page 4

Rice's Theorem

In chapter 21, Rich considers a suite of languages which she proves are not in D using a reduction from H: Hε, HANY, HALL, A, Aε, AANY, AALL.

There's a pattern. According to Rice's theorem, no non-trivial property of a language semi- decided by a TM, such as whether ℇ ∈ L, is decidable.

A non-trivial property: not true or false for all SD languages.

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

Ø is the language containing no strings. Either P(Ø) = True or P(Ø) = False. Assume it is False (a similar proof exists if it is True).

P(L) = { L contains an even length string} P(Ø) = false P'(L) = { |L| %2 = 0} P'(Ø) = true Since P is nontrivial, there is some SD language LT such that P(LT) is True. Let MT be a Turing machine that semidecides LT.

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

this is equivalent, in terms of our example property P, to saying L = { <M> : L(M) contains an even length string }

LT = {aa}

R(<M, w>) = is a mapping reduction from H to L 1. Define M#: 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 simulate MT on x. 2. Return <M#>.

<M,w> ∈ H L(M#) = … Mₒ accepts/rejects <M#> because …

<M,w> ∉ H L(M#) = … Mₒ accepts/rejects <M#> because …

Rice Theorem and Semidecidability Page 5

Appying Rice's Theorem

To use Rice’s Theorem to prove L ∉ D, all that's required is:

• Specify property P.

• The domain of P must be the set of languages that can be semidecided by a TM (i.e, the SD languages).

• Show that P is nontrivial (true for at least one SD language, and false for at least one SD language).

So, can Rice's Theorem be used to prove these languages are not decidable?

1. {<M> : L(M) contains only even length strings}. 2. {<M> : L(M) contains an odd number of strings}. 3. {<M> : L(M) contains all strings that start with a}. 4. {<M> : L(M) is infinite}. 5. {<M> : L(M) is regular}. 6. {<M> : M contains an even number of states}. 7. {<M> : M has an odd number of symbols in its tape alphabet}. 8. {<M> : M accepts ε within 100 steps}. 9. {<M>: M accepts ε}. 10. {<Ma, Mb> : L(Ma) = L(M1)}. 11. L¬R = { <M,s> : s ∈ L(M) and sR ∉ L(M) }. (The HW #3) language.

Rice Theorem and Semidecidability Page 6

Three Languages that look similar but are in different categories

L 1 = {a}.

L 2 = {<M> : a ∈ L(M)}.

L

3 = {<M> : L(M) = {a}

Proving that L ∉ SD

One way is to exploit the fact that if L ∈ SD/D then ¬L ∈ ¬SD, where ¬L is the complement of L. (If L and ¬D are both in SD, then both are also in D).

Another is to a reduction from ¬H. There is a wrinkle in that we cannot use ¬C, as we did with reductions from H to show that a language is not decidable. That is because a semideciding Mₒ could loop and there is no way to take the compliment of a loop.

L = {<M> : L(M) = {a} }. Complete the proof below that uses a reduction from ¬H to show that L ∉ SD.

R(<M, w>) is a reduction from ¬H to L. That is, <M, w> are R's parameters, and R outputs M#, which could be an element in L: 1. Define M#(x): 1.a If x = a, accept. 1.b Erase the tape. 1.c Write w. 1.d Run M on w. 1.e Accept x. 2. Return <M#> If an Oracle Mₒ exists and semidecides L, then Mₒ(<M#>) semidecides ¬H:

• <M,w> ∈ ¬H: Mₒ accepts <M#> because … L(M#) ={a}, because M will not halt on w, so the only string that M# will accept is a at step 1.

• <M,w> ∉ ¬H: Mₒ does not accept <M#> because … L(M#) = ∑*, and ∑* contains other strings besides a. The reason why L(M#) = ∑* is that M will not halt on w, so M# will either accept at step 1 if x = a, or at step 5 for all other strings in ∑*.

But no machine to semidecide ¬H can exist, so neither does Mₒ

Rice Theorem and Semidecidability Page 7

L = {<M a , M

b > : ε ∈ L(M

a ) – L(M

b )}. That is, the strings in L are pairs of TM string encodings, such that ε is in

the language accepted by the first encoded TM, but not the second.

We can prove L ∈ ¬SD by a reduction from ¬H. R( <M, w> ) is a reduction from ¬H to L: 1. Define M#1 1.a Accept

2. Define M#2 2.a Erase the tape. 2.b Write w on the tape. 2.c Simulate M on w. 2.d …

Return <M#1,M#2>.

Let Mₒ be an Oracle that semidecides L. Then Mₒ( <M#1,M#2>) semidecides ¬H:

<M, w> ∈ ¬H: L(M#1) - L(M#2) = …, and Mₒ accepts <M#1,M#2> because …

<M, w> ∉ ¬H: L(M#1) - L(M#2) = …, and Mₒ does not accept <M#1,M#2> because …

L = {<M> : L(M) is context-free}. Prove that L ∉ SD using a reduction from ¬H R (<M,w>) = 1. Define M# 1.a Save x. 1.b Erase the input tape. 1.c Write w on the input tape. 1.d Simulate M on w. 1.e If x ∈ aⁿbⁿcⁿ, accept. 1.f Else loop. 2. Return <M#>.

What is the reasoning?

Rice Theorem and Semidecidability Page 8

L = {<M> : L(M ) is infinite}. ¬H = {<M,w> : M does not halt on w} R(<M,w>) is a reduction from ¬H to L: 1. Define M#(x) 1.a Save x. 1.b Erase the tape. 1.c Write w on the tape. 1.d Run M on w for a maximum of |x| steps. 1.e If M halted by step |x| then loop. 1.f Else accept x. 2. Return <M#> If an Oracle Mₒ exists and semidecides L, then C = Mₒ(R(<M,w>)) = Mₒ(<M#>) semidecides ¬H: • <M,w> ∈ ¬H: M does not halt on w, so M# always makes it to step 1.f and accepts ∑*. ∑* is an infinte language, so Mₒ accepts <M#>. • <M,w> ∉ ¬H: M halts on w. Suppose it does so in k steps. Then M# loops on all strings of length k or greater. It accepts strings of length less than k. But that set is finite. So Oracle does not accept. But no machine to semidecide ¬H can exist, so neither does Oracle.

Note that M# could be very simple if we just inverted the verdict of Mₒ: 1.a Save x. 1.b Erase the tape. 1.c Write w on the tape. 1.d Run M on w. 1.e Accept x.

Rice Theorem and Semidecidability Page 9