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}*}.

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

R(<M,w>) = 1. Define M#(x): 1.a If x = a or x = b accept 1.b Save x 1.b Replace x with w 1.c Run M on w 1.d Restore x 1.e Accept x

2. Return <M#,a>

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

<M,w> ∈ ¬H: M# would accept a and b at 1.a, and then loop forever at 1.c. Thus L(M#) = {a,b}, and Mₒ would accept <M#,a> because a ∈ {a,b}, and |{a,b}| = 2

<M,w> ∉ ¬H: M# would accept a and b at 1.a, proceed through 1.c, and accept everything else at 1.e. Thus L(M#) = ∑*, and Mₒ would not accept <M#,a> because |∑*| != 2.

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