But for $L_1$ we do not have an input given.

Dark Mode

1,420 views

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 ???

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 ???

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

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.

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.