MadeEasy Subject Test: Theory of Computation - Decidability

Question

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 decidable

please explain decidability for L1

Answer 1

If there is function and We can solve this function using a halting Turing machine then it is Computable.  

If there is halting Turing machine available for given problem and if it gives output as YES or NO. Then it is decidable. 

For L1, there is halting Turing machine which can say is state q visited or not in 15 steps .

Hence it is Decidable

Answer 2

above TM ends within 15 steps, means its an HALTING TURING MACHINE

for an HALTING TURING MACHINE corresponding LANGUAGE is RECURSIVE LANGUAGE

NOW in question it is said that "M is a Turing Machine that visits state q on some input " that means its an MEMBERSHIP ALGORITHM .

so,for an RECURSIVE LANGUAGE -----------> MEMBERSHIP ALGORITHM  is acceptable this is why it is 

DECIDABLE

Answer 3

Turing machine visits state Q for some input of length atmost 15, as it is going to run for atmost 15 steps.

Set of strings of length atmost 15 is finite, hence if machine visits state Q for atleast one input from this set machine halts and says yes. Otherwise no.

We got an algorithm hence it is decidable.