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?

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

1 Answer 1

Reset to default
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...

Improve this answer
$\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.