2
$\begingroup$

Given the Turing machine $M = ( \{q_0, q_1, q_2. q_3,q_4\}, \Sigma= \{a, b, c \}, \Gamma = \{a, b, c, 򪪪\}, \delta, q_0, 򪪪, \{q_4\} )$ where $q_0$ is the start state, $q_4$ the end state and 򪪪 the blank symbol. $\delta$ is defined as:

enter image description here

Let $w$ be any word of length $n$ accepted by the Turing machine $M$. Is it always true, that $M$ will reach $q_4$ in maximum of $1.5 \cdot (n+5)$ steps?

Is there a general strategy for this or do we just try different inputs until we find a contradiction? If none is found, how do we go about proving such a statement?

$\endgroup$
  • $\begingroup$ Out of curiosity: is $\delta(q_{3},a)$ really $(q_{3},b,L)$? $\endgroup$ – André Souza Lemos Feb 22 at 22:51
  • $\begingroup$ Yes, I took this question from an old exam. $\endgroup$ – iMazing Feb 23 at 9:28
2
$\begingroup$

In general, it is impossible to even determine if it will ever halt. And if it halts, determining the number of steps is also impossible. Check out the busy beaver game for details.

There are general techniques that work in a large proportion of cases of practical interest, for a start check out the reference question here. But there have been complete libraries written on the intricacies of the matter...

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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