1

For each of the following set, show that they are undecidable. Do not use Rice theorem.
a. $L_{1} = \{M |M$ accepts w if w contains the substring 10 $\}$
b. $L_{2} = \{M| M$ accepts an odd number of strings $\}$

I have tried proving using aTM because it is known undecidable, but I do not know how to create the argument formally.

ml0105
  • 14,674
bccurry
  • 135
  • 3
    The usual way to prove languages undecidable is to show that if you had a magic TM that could decide them, you could use it to determine whether an arbitrary TM halts. – Paul Z Mar 26 '14 at 16:32

2 Answers2

0

In both cases, you can assume the TM $T$ exists that decides the language of TMs, and have a Turing machine $T_2$ that calls $T$ on itself and then does the opposite of what is predicted by $T$, contradicting the correctness of $T$.

user2566092
  • 26,142
0

Suppose $L_{1}$ is decidable. Let $T$ be a TM that decides $L_{1}$. Let $M$ be a Turing Machine and $s$ be an arbitrary string. We construct $M_{s}$ which first simulates $M$ on $s$. $M_{s}$ halts if and only if $M$ accepts $s$.

We now consider $M^{\prime}$ as a Turing Machine. If $M^{\prime}$ operates by simulating $M_{s}$. $M^{\prime}$ accepts strings with $10$ as a substring if and only if $M_{s}$ halts. This implies undecidability.

Take the same approach for $L_{2}$, basically.

ml0105
  • 14,674
  • Is this implying that T decides Atm, which we know is undecidable. Therefore T can't exist? Or does T decide HALTtm? – bccurry Mar 26 '14 at 17:13
  • Either will work. $T$ decides if $M_{s}$ halts, which is the halting problem. $T$ also decides if $M$ accepts $s$. – ml0105 Mar 26 '14 at 17:17
  • Oh, ok thanks! I was trying to figure this out because the answer seems so trivial and I was trying to make it problem specific. – bccurry Mar 26 '14 at 17:20