CODEWITHSUNDEEP
proofcomputation-theoryturing-machinesdecidable
kmoney22z
kmoney22z

Reputation: 11

Proving A Language Is Undecidable Using Turing Reductions

I need to prove that the language L(EVEN) = { M : |L(M)| is even } is undecidable.

In other words, the language L(EVEN) is the set of all Turing Machines which accept some language of even cardinality.

Here, M is the encoding of some Turing Machine which would be passed in as input if there existed a decider for L(EVEN).

I've completed other problems similar to this one using Turing Reductions, one example can be seen here:

Undecidability Reduction Proof

My issue is that I am unable to come up with some previously proved undecidable language that would be useful to show L <= L(EVEN).

The undecidable languages weve covered so far in class are as follows: 

- L(emptyset) = { M | M is a TM and |L(M)| = emptyset}  
- L(ACC) = { (M, x) | M is a TM, and M accepts input x}  
- L(HALT) = { (M, x) | M is a TM, and M halts on input x}  
- L(EQ) = { (M1, M2) | M1, M2 are TMs, and L(M1) == L(M2) }  
- L(∈ - HALT) = { M | M is a TM, M halts on input ∈ }

I could also possibly use the complements of these languages as decidability is closed under complementation. How could I use one of these undecidable languages to prove that L(EVEN) is also undecidable, using a similar setup to the example problem I included?

Upvotes: 1

Views: 2162

Answers (1)

Patrick87
Patrick87

Reputation: 28302

Suppose we had a decider for L(EVEN). Then, we can decide L(ACC) as follows:

From input M to the TM for L(ACC), construct a TM M' which first verifies the input tape is the input x to M, and then runs M on x. M' so constructed either accepts the language {x}, if M accepts x, or the empty language if M does not.

By using our decider for L(EVEN) on the encoding of M', we can tell if |L(M')| is even (in which case L(M') is empty and M does not accept x) or odd (in which case L(M') = {x} and M accepts x).

Upvotes: 2

Related Questions