Mark the following turning machine related facts with true or false. And explain

Question

Mark the following turning machine related facts with true or false. And explain why.

1. There exists a 1-DTM recognising an infinite language that is only allowed to move the head at most one position away from the starting position. is equivalent to one with only one state. 2. Every 1-DTM 2. If we remove the left start-mark and allow the machine to move the head to the infinitely to the left as well, the machine is not more powerful than the orginially defined one 4. If the machine from 3. is not allowed anymore to move the head to the right, the accepted language is a subset of

Explanation / Answer

1)FALSE

     The option in the given question is False.Because ,here the our Turing maching need to recognize the infinate languages .so for each strnig, it needs to evaluate from starting positions.so the given option is false.

2)TRUE

       The given option is True .the reason is A turing machien moves head for one input from one state.

3)FALSE

         No,no yet all.If you remove the " left start mark " nothing will be wrong ,there is chance to move the head left to right too.

4)FALSE

      If you stop the moving the head to right side ,then machine can't get the proper string.

  

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.