Unless otherwise noted, the alphabet for all questions below is assumed to be (a

Question

Unless otherwise noted, the alphabet for all questions below is assumed to be (a,b). 1. [10 marks] This question asks you to examine the formal definitions of a TM and related concepts closely. B on these definitions, answer the following. (a) A configuration of a Turing Machine (TM) consists of three things. What are these three things? (b) Can input alphabet contain the blank symbol u? Why or why not? (c) The tape is infinite. Is the tape alphabet infinite? (d) Can a Turing machine's head ever be in the same location in two successive steps? (e) What is the difference between a decidable language and a Turing-recognizable language?

Explanation / Answer

Solution:-

(a) A configuration of Turing Machine consists of three things, these things make a triple which is (p,,m). Where p S is the state of the configuration. is the tape description of the configuration and m is the position of the reading head of the configuration.

(b) NO. Input alphabet can not be a blank symbol because if it allow then it will not possible for the machine to find the end of data.

(c) Tape alphabet is finite in Turing Machine. we can think that turing machine with infinite tape alphabet. But this creates two fundamental problem. First machine description will not be finite. Second one is such machine can be decide any language over the alphabet.

(d) YES. It is possible when it's head on the first tape square and it tries to move left.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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