# 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