retagged by
1,846 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 10 steps}

L2 = {< M > |M is a turing machine, |M | < 100 where |M | is number of states in machine}

Which of the following is correct?

(A) L1 is decidable but L2 is not decidable (B) L2 is decidable but L1 is not decidable

(C) Both L1 and L2 is decidable

(D) Neither L1 nor L2 is decidable

 

In L2, if the states are unreachable, then will it be possible to detect whether machine has less than 100 states ???
retagged by

3 Answers

2 votes
2 votes

L1. A Universal Turing Machine can simulate any Turing Machine, whose states and transitions are encoded in a way that the Universal Turing Machine understands it. You can also modify it to keep track of how many steps you have made so far (even stop it right there). so Decidable.

L2.Given a TM in a suitable encoding, it is fairly straightforward to determine how many states the TM has. Consider any common encoding, or define a reasonable one yourself, and then describe an algorithm that answers the question using the encoding. so Decidable.

2 votes
2 votes
We take a turing machine say M and run on given input approx 10 step and see wheter it give answer in form of YES or NO.Then we can clearly say that it is decidable.

But in the second case Turing can have more that 100 and less than 100 states depend upon specification of problem so it is undecidable.
0 votes
0 votes

Answer : a

L1 : says within 10 steps hence finite steps so can be decided in finite time hence decidable.

L2 : states of M < 100 ...Finite number of states is there, hence decidable.

edited by

Related questions

0 votes
0 votes
0 answers
1
1 votes
1 votes
1 answer
3
1 votes
1 votes
0 answers
4
iarnav asked Oct 17, 2017
680 views
I have read that T.M does not accept ε , but then in questions I have read T.M taking input ε ?Well, if T.M can't accept ε then why we are giving T.M the input ε ?Th...