To prove a language is not recursive

Question

Prove the language $$L_1=\{\sigma\in\{0,1\}^*|\sigma \text{ codes a TM which accepts at least one word }\}$$ is not recursive.

I think it has something to do with $$L=\{\sigma\in\{0,1\}^*|\sigma \text{ codes a TM that does not accept } \sigma\}.$$ We proved $L$ is not recursive.

Here is what I think: We construct a TM that accepts $L$ if $L_1$ is recursive. For any input $\sigma$,

1. Check if $\sigma$ codes a TM $M$, reject if not.

I am not sure about next step, anyone help me?

Answer 1

I am going to expand on the comment of Gareth Rees. We assume that the language $L$ is recursive, towards a contradction- reductio ad absurdum.

Now, if $L$ is recursive, by the very definition of a recursive language, we have a Turing machine- a decider- that can tell us yes/no for every possible binary string indicating whether or not the Turing machine coded by that string accepts at least one input. Negating everything, we can easily use this decider to identify all Turing machines- encoded in this language- that do not accept any input. In other words, we can decide all machines that never halt on any input. We're getting closer to the halting problem, but we're not quite there.

Now, I'll show you that with the power to decide when a machine never halts, we have the power to decide the halting problem for a given machine on a given input. For the halting problem, we need to be able to tell if the machine $M$ halts on input $x$, for any $M, x$. Well, given such an $M, x$, we can define a new machine $C$ such that $C$ ignores its input completely and just behaves as $M(x)$. That is, for all inputs $y$, $C(y) = M(x)$, where I use equality here as semantic or behavioural equality.

OK, so with this new $C(y)$, since it discards its input, it always has the same computation- so either it halts on every input, or it halts on no input, and, furthermore, its halting is equivalent to the halting of $M(x)$. Now, our assumption above tells us that we have the power to decide when a machine halts on no input. So we can decide whether or not $C(y)$ never halts. If $C(y)$ never halts, then we've decided that $M(x)$ never halts. Else we've decided that $M(x)$ halts. So we've solved the halting problem. Since this is known to be impossible, we've arrived at a contradiction, concluding that the language above is not recursive.