in Theory of Computation retagged by
1,420 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 ???
in Theory of Computation retagged by
1.4k views

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.

1 comment

But for $L_1$ we do not have an input given.
0
0
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

4 Comments

@Anirudh and @Arjun, Can i say like : for L1 make that state q final state. run input and see if halts within 10 steps. So decidable.

For second one, we know that TM halting problem is undecidable. And even decreasing number of states won't help. {L,R} movements are possible in a TM so undecidable.
0
0
@coolcoder Same question - run "what input" for $L_1$?

For $L_2$, first we should understand the question - it says given a TM we should decide if it has less than 100 states- there is no need to run it for any input to say "yes" or "no".
0
0
M is a TM , but L1 and L2 are two languages of it. Then why we are considering only TM , but not the language of the TM?
0
0

Related questions