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$
2
  • $\begingroup$ Out of curiosity: is $\delta(q_{3},a)$ really $(q_{3},b,L)$? $\endgroup$ Commented Feb 22, 2020 at 22:51
  • $\begingroup$ Yes, I took this question from an old exam. $\endgroup$
    – Monika
    Commented Feb 23, 2020 at 9:28

1 Answer 1

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...

$\endgroup$

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.