L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}.

Lab 9, due Thurdsay 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

R<M,w> = 1. Define M#(x) 1.a If x = a then accept 1.b Save x 1.c Replace x with w on the input tape 1.d Run M on w 1.e Restore x to the input tape 1.f If x = b accept

2. Return <M#,a>

If there were an Oracle Mₒ that could decide L, the C = Mₒ(R(<M,w>)) = Mₒ(<M#,a>) could decide H.

<M,w> ∈ H: M# accepts a at 1.a, passes through 1.d, and accepts b at 1.f. So L(M#) = {a,b}, and Mₒ accepts <M#,a> because a ∈ L(M#), and |L(M#)| %2 = 0.

<M,w> ∉ H: M# accepts a at 1.a and then loops forever at 1.d Thus L(M#) = {a}, and Mₒ rejects <M#,a> because |L(M#)| % 2 = 1.

But no TM could decide H, so Mₒ could not possibly exist.

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

H3 2. (12.5 points) L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}. As examples, which must not appear in your proof: Let L(M₁) = {b,aa}. Then <M₁,b> ∈ L because b ∈ L(M₁) and a ∉ L(M₁); <M₁,aa> ∉ L because both aa and b are in L(M₁); and <M₁,a> ∉ L because a ∉ L(M₁). Prove that L ∉ D using a reduction from H. Do not Rice's theorem.

L₁ = {<M,s> : M rejects ss, but accepts exactly two other strings ending in s}. Prove that L₁ ∉ D by a reduction from H.

R(<M,w>) = 1. Define M#(x) 1.a if x = aabaab reject 1.b save x 1.c Replace x with w on the the input tape 1.d Run M on w 1.e Restore x 1.f if x = aaab, accept 1.g if x = baab, accept 1.h else reject

2. Return <M#,aab>

if x == "aabaab": print("aabaab ∉ L") sys.exit()

M(w) #stop here if M loops on w

if x == "aaab": print("aaab ∈ L") sys.exit()

if x == "aab": print("baab ∈ L") sys.exit()

If there were an Oracle Mₒ that could decide L, the C = Mₒ(R(<M,w>)) = Mₒ(<M#,aab>) could decide H. <M,w> ∈ H: Mₒ accepts <M#,aab> because M# rejects when x = aabaab. If x != aabaab, then M# passes through step 1.d, and then accepts exactly strings ending aab at steps 1.g and 1.h. <M,w> ∉ H: Mₒ rejects <M#,aab> because L(M#) does not include exactly two strings in aab. L(M#) = {} = Ø 1. Define M#(x) 1.a if x = aabaab reject 1.b save x 1.c Replace x with w on the the input tape 1.d Run M on w LOOP FOREVER, NEVER GET PAST 1.D

But no TM could decidde H, so Mₒ could not possibly exist.

L₂ = {<M> : No string in L(M) ends with ".pdf"}. Prove that L₂ ∉ D by a reduction from H. R(<M,w>): 1. Define M# 1.w Replace x with w on the input tape 1.x Run M on w 1.y Accept 2. Return <M#>

If there were an Oracle Mₒ that decides L₂, then C = ¬Mₒ(<M#>) decides H.

<M,w> ∈ H: L(M#) = ∑*. What does Mₒ think about TMs that accept ∑*? Does it think are elements of L₂ or not? Mₒ accepts if it thinks that there are NO strings in ∑* that end in .pdf; otherwise it rejects. Mₒ REJECTS <M#> because there an infinite number of strings in ∑* that end in .pdf

<M,w> ∉ H: L(M#) = Ø, and so Mₒ ACCEPTS, because Ø contains no strings ending in .pdf

But nothing could decide H,so L₂ is undecdiable as well.

Prove that L₂ ∉ SD by a reduction from ¬H: R(<M,w> = 1. Define M#(x): 1.a Replace x with w on the input tape. 1.b Run M on w 1.c Accept (accepts any x) 2. Return <M#>

If there were an Oracle Mₒ that could semidecide L₂, then C=Mₒ(R(<M,w>)) = Mₒ(M#) could semidecide ¬H: Note that the requirements for a semideciding Mₒ are that Mₒ accept if <M#> ∈ L₂, and either loop or reject if <M#> ∉ L₂.

<M,w> ∈ ¬H: M# loops forever 1.b and thus L(M#) = Ø. Mₒ accepts <M#> because L(M#) contains no strings ending in ".pdf"

<M,w> ∉ ¬H: M# passes through 1.b and accepts any x at 1.c. Thus L(M#) = ∑*, and Mₒ does not accept <M#> because ∑* contains strings ending in ".pdf"

But no TM could semidecide ¬H, so Mₒ could not possibly exist.

L₃ = {<M> : L(M) is an infinite language}. Prove that L₃ ∉ SD using a reduction from ¬H.

Does this proof work? R(<M,w>) = 1. Define M#(x): 1.a Replace x with w on the input tape. 1.b Run M on w 1.c Accept (accepts any x) 2. Return <M#>

If there were an Oracle Mₒ that could semidecide L₂, then C=¬Mₒ(R(<M,w>)) = ¬Mₒ(M#) could semidecide ¬H:

<M,w> ∈ ¬H: M# loops forever 1.b and thus L(M#) = Ø. Mₒ does not accept <M#> because L(M#) = Ø, and Ø is not an infinite language. So C accepts.

<M,w> ∉ ¬H: M# passes through 1.b and accepts any x at 1.c. Thus L(M#) = ∑*, and Mₒ accepts <M#> because ∑ is an infinie language. So C rejects.

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#>.