Turing machine that can remember

Question

Special Turing Machine is defined just like standard Turing Machine, only that each step is made according to the content of the tape starting from the left edge to the head position in tape. (The transition function in this case belongs to Q X Γ* -> Q X Γ X {L,R})

Which of the following is true:

A. Every language L has a Turing machine that decides L if and only if there is a special Turing machine that decides L.

B. Every language L has a Turing machine that decides L in a polynomial time if and only if there is an special Turing machine that decides L in a polynomial (input length polynomial).

C. A,B answers are correct.

D. A,B answers are incorrect.

and my question is: the correct answer is D and I can't understand why.

The answer is: Each language can be decided by a special Turing machine in linear input length time (O(n) when n is the input length). A transition function goes to the right as long as no blank space is seen, and as soon as you see a blank space switches to receiving or rejecting according to the word written on the tape.

My question is: How can I decide whether to reject or accept a word? In other computational models, such as PDA, DFA, we defined the transition function similarly, and no power was added to the model. Why does it seem that power is added to the computational model as a result of the change of the transition function when it comes to Turing machines?

Thanks.

Answer 1

Given any language $L$ there is a special Turing machine $T$ that decides $L$ in polynomial time.

The Turing machine has 3 states: the initial states $q_0$, the accepting state $q_A$ and the rejecting state $q_R$. Let $\Gamma$ be the tape alphabet (including the blank symbol $\varepsilon$), and let $\alpha x$ denote the contents of the tape starting from the left edge to the head position in tape, where $\alpha \in \Gamma^*$ and $x \in \Gamma$. As usual, I am going to assume that the input is written starting from the beginning of the tape and that the head is initially positioned at the beginning of the tape. The transition function $\delta$ is defined as follows:

• $\delta(q_0, \alpha x) = (q_0, x, R)$ if $x \neq \varepsilon$
• $\delta(q_0, \alpha x) = (q_A, x, R)$ if $x = \varepsilon$ and $\alpha \in L$
• $\delta(q_0, \alpha x) = (q_A, x, R)$ if $x = \varepsilon$ and $\alpha \not\in L$

Since there are undecidable languages for regular Turing Machines, this immediately implies that A and B are false.

Answers D and C are unclear. They talk about "both answers" but you are given $4$ possible answers.