0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ No, but also in DFA we defined recursive transition function with domain: Q × Σ* . So what is the difference? $\endgroup$
    – Ella
    Commented Jun 13, 2020 at 12:55
  • $\begingroup$ In DFAs the domain of the transition function is $Q \times \Sigma$, not $Q \times \Sigma^*$. $\endgroup$
    – Steven
    Commented Jun 13, 2020 at 13:06
  • $\begingroup$ But there is a recursive definition of the transition function, where the domain if the same as I mentioned. $\endgroup$
    – Ella
    Commented Jun 13, 2020 at 13:09
  • $\begingroup$ The definition of the transition function $\delta' : Q \times \sigma^* \to Q$ you are talking about is not part of the definition of a DFA. It is an extension on the transition function $\delta : \Sigma \times Q \to Q$ of the DFA. The definition of $\delta'$ does depend on $\delta$, you cannot define a DFA using any transition function $Q \times \sigma^* \to Q$ otherwise weird things can happen (similarly to what I have done in my answer). $\endgroup$
    – Steven
    Commented Jun 13, 2020 at 13:12
  • $\begingroup$ Ok, got it. thank you! $\endgroup$
    – Ella
    Commented Jun 13, 2020 at 13:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ the transition function is computable? Because how can i tell if α∈L or α∉L? $\endgroup$
    – Ella
    Commented Jun 13, 2020 at 13:08
  • $\begingroup$ It is not necessarily computable. Your definition does not require the transition function to be computable. I merely showed the existence of a special Turing machine $T$. $\endgroup$
    – Steven
    Commented Jun 13, 2020 at 13:10
  • $\begingroup$ So as long as I can define well the transition function, can I conclude its existence? Even if I can't find it at a reasonable time? $\endgroup$
    – Ella
    Commented Jun 13, 2020 at 13:13
  • $\begingroup$ Why the special Turing machine T that decides L runs in polynomial time, and not linear? $\endgroup$
    – Ella
    Commented Jun 13, 2020 at 13:15
  • $\begingroup$ Your question has nothing to do with the time needed to find $T$. It only talks about the time that $T$ itself takes to complete its computation (as a function of the input size). Proving the existence of a mathematical object that satisfies the definition of "special Turing machine" is enough. $\endgroup$
    – Steven
    Commented Jun 13, 2020 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.