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.