# Maximum number of steps a Turing machine makes

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:

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?

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

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