Turing machine question

Question

I saw question where I saw this format being used:

L1 = {<M> | L(M) = ϕ}

What does exactly <M> mean and why is L(M) = ϕ, mentioned afterwards. Isn’t L() stands for language for something? If the language is equivalent to null, it contains nothing. Then what does it exactly mean?

Answer 1

Here,  $<M>$ is referring to the encoding of a Turing machine, And   $L(M) = ϕ$ , means the language accepted by turning machine M is empty.

Comments

Turing machines can not generate any language.

---

raja11sep ,

Yes, my bad

I mean’t by TYPE-0 grammar.

Answer 2

Given a C program can you say whether it’ll give output as “1” for any input? For simplicity assume that only 10 possible inputs are there. How will you do this?

The given question is pretty similar. Replace the ‘C program’ by a Turing machine (description). Now the task is to identify if the given Turing machine is accepting any input. What’s ‘L’ doing here – <M> can be any Turing machine description and set of all such Turing machine descriptions (which accepts at least one input) is $L.$ 

Once the above point is clear, then you can see Rice’s theorem to answer 99%  of such questions.