Design a polynomial space bounded deterministic TM (Turing Ma­chine) D that deci

Question

Design a polynomial space bounded deterministic TM (Turing Ma­chine) D that decides the following problem. The input is an encoding (AT, s, t, k) of (N, s, t, k) , where AT is a nondeterministic TM, s and t are IDs (instantaneous descriptions) of N of length m each, and k is a natural number. D decides, whether there is a computation of N starting in s, reaching t in exactly 2k steps, hereby never going through an ID that is longer than m. Using pseudo-code, write a recursive function Test(N, s, t, k) that returns 1 if D should accept ((N, s, t, k)), and 0 otherwise. Concisely describe an implementation of your pseudo-code on a the TM D on a high level, i.e., say what is stored where on the tape or tapes of D, and what is done with it. How much space does D use as a function of n and k?

Explanation / Answer

A Turing machine is the original idealized model of a computer, invented by Alan Turing in 1936.

Turing machines are equivalent to modern electronic computers at a certain theoretical level, but differ in many details.

A Turing machine consists of a line of cells known as the "tape", together with a single active cell, known as the "head". The cells on the tape can have a certain set of possible colors, and the head can be in a certain set of possible states.

Any particular Turing machine is defined by a rule which specifies what the head should do at each step. The rule looks at the state of the head, and the color of the cell that the head is on. Then it specifies what the new state of the head should be, what color the head should "write" onto the tape, and whether the head should move left or right.

The prize Turing machine has two possible states of its head, and three possible colors on its tape.

The animation below shows the operation of the machine, with the states of the head represented by the orientation of the arrows.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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