1,647 views
5 votes
5 votes
WHICH OF THE FOLLOWING IS DECIDABLE?

1.WHEATHER AN ARBITRARY TURING MACHINE PRINTS SOME NON BLANK CHARACTER

2.WHEATHER A TURING MACHINE PRINTS A SPECIFIC CHARACTER

3.THE SET OF CODES FOR TURING MACHINE THAT NEVER MAKE A LEFT MOVE.

4. WHEATHER T.M EVER MOVES ITS HEAD TO THE LEFT WHEN STARTED WITH INPUT W.

5.WHEATHER T.M EVER REACHES STATE Q WHEN STARTED WITH INPUT W FROM ITS INITIAL STATE

6.T.M VISITS STATE Q ON SOME INPUT WITHIN 10 STEPS.

7.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
140 views
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
142 views
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
148 views
How is equality problem for DCFL decidable?