in Theory of Computation
1,459 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.
in Theory of Computation
by
1.5k views

4 Comments

3 and 4 are also decidable.

Because the encoding of any TM contains all the data about it's moves.

3. If it has and left move can be easily found
4. If it moves left on any input can be also found from the encoding of the TM

reference: https://cs.stackexchange.com/questions/49615/what-is-an-encoding-of-a-tm

2
2
plz what is option (3) saying set of TM that never makes a left move is undeciable ??
0
0

6. Decidable

5. Undecidable

4.  Decidable 

3   Undecidable   https://cs.stackexchange.com/questions/94103/a-turing-machine-that-doesnt-move-to-the-left

2.  Undecidable

1.  Undecidable

plz check  ??   if i wrong plz tell ??

0
0

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
4