Register

Turing Machine

1,324 views
2 votes
2 votes

Consider the following languages :
L1 : {< M, q >|M is a Turing Machine that visits state q on some input within 15 steps}.
L2 : {< M >|M is a Turing Machine, |M|< 200 where |M|is number of states in machine}.
Which of the following is correct ?

  • L1 is decidable but L2 is not decidable
  • L2 is decidable but L1 is not decidable
  • Both L1 and L2 is decidable
  • Neither L1 nor L2 is decidable
User Avatar

1 Answer

Best answer
6 votes
6 votes
L1: ​​​​​​ Since steps are finite, configurations are also finite. Within finite configurations we can know whether that particular state has been encountered or not. Hence decidable.

L2: Number of states can be known just looking at encoding of inputted TM by/in UTM. Hence decidable.

Therefore, both decidable.
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
RahulVerma3 asked Apr 2
46 views
Theory of Computation | design of Turing Machine
Is this the correct Turing machine for the language $0^n 1^n0^n$? assuming $ at the end and begining of the input tape
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
User Avatar
3 votes
3 votes
2 answers
4
h4kr asked Dec 7, 2022
726 views
Turing machine 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?
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 langua...
User Avatar
Link Copied!