Theory of compitation

CSC 520 F20 Lab #14 Prove L ∉ SD by a reduction from ¬H:

L = {<M,s>: if t ∈ L(M), s comes before t in a Unicode-based lexicographic ordering of ∑*; and |L(M)| ≥ 1}. For example, if L(M) = {d,ef}, then <M,c> ∈ L because c comes before d or ef; but <M,aaa> ∉ L, since aaa comes after d or ef because it is longer. Complete the proof started below, which shows that L ∉ SD based on a reduction from ¬H:

Let R(<M,w>) be a mapping reduction function from ¬H to L: 1. Define M#(x):

Add any steps needed in the M# definition, before or after the 3 steps listed below. • Save x • Overwrite x with w on the input tape • Run M on w

2. Return <M#,a>

If there were an Oracle Mₒ that could semidecide L, then Mₒ(R<M,w>)=Mₒ(__________) could semidecide ___________:

_______ ∈ ¬H: L(M) = _______. Mₒ accepts _______ because ______________.

________∉ ¬H: L(M) = ______. Mₒ does not accept ______ because _________.

But no TM could ____________, so Mₒ could not possible exist.

CSC 520 F20 Lab #14 — ¬H reduction Page 1