Register

Turing machine question

726 views
3 votes
3 votes
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?
User Avatar

2 Answers

Best answer
1 votes
1 votes
Here,  $<M>$ is referring to the encoding of a Turing machine, And   $L(M) = ϕ$ , means the language accepted by turning machine M is empty.
• selected by
User Avatar
1 votes
1 votes

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.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
2 answers
1
srestha asked Apr 30, 2019
1,081 views
Made Easy Test Series:TOC-Turing Machine
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length}$P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on whi...
User Avatar
3 votes
3 votes
2 answers
2
Anurag Aizen Mukherj asked Jan 20, 2019
1,032 views
TOC-Turing Machine
Consider the given below Turing Machine and identify the correct language accepted: (a+b)*aa(a+b)* b*a(bb*a)*a b*ab*a None of these The answer is given as (1). But I think (3) is correct as well. Can anyone tell me why only (1) is correct.
Consider the given below Turing Machine and identify the correct language accepted:(a+b)*aa(a+b)*b*a(bb*a)*ab*ab*aNone of theseThe answer is given as (1). But I think (3)...
User Avatar
4 votes
4 votes
2 answers
3
Kai asked Jan 29, 2017
747 views
Ace Test Series: Theory Of Computation - Turing Machine
When a Multi-tape TM of time complexity T(N) is reduced to a single tape turing machine, the complexity can go upto?
When a Multi-tape TM of time complexity T(N) is reduced to a single tape turing machine, the complexity can go upto?
User Avatar
0 votes
0 votes
1 answer
4
Neal Caffery asked Dec 1, 2016
1,364 views
turning machine
TM 'M1' accepts atmost 2 distinct input . TM 'M2' accept more than 2 distinct input . Which of the machine is Turning recognizable ?
TM 'M1' accepts atmost 2 distinct input .TM 'M2' accept more than 2 distinct input . Which of the machine is Turning recognizable ?
User Avatar
Link Copied!