I am studying Turing machines and somewhat confused about their time complexity.
Is the time complexity defined to be the number of steps that a Turing machine takes overall or is it only the number of times it performs a state transition?
For example, If I just have one state, $q_{0}$ where the head moves from left to right, until it finds Empty/End-of-string symbol and halts $q_{halt}$, my questions are:
$1)$ Would the number of right-shifts be taken into account when estimating its complexity?
$2)$ Does it make a difference how many Tapes there are?
Thanks.
Best Answer
(1) Time complexity counts all of the steps, not only those that change the control state. (2) Usually, one does not take the number of tapes into account when defining what is meant by a step (and therefore in defining time complexity). A Turing machine can, in a single step, write on all of its tapes (in one cell per tape), move its heads on all tapes (at most one step on each tape), and change its control state.