how to calculate the turing machine running time?

Question

I just review the computing theorem. And i met a question as follow.
Consider a deterministic k-tape Turing machine with q states
and σ alphabetic symbols. Suppose this Turing machine halts after using a
maximum of h cells on each of the tapes. What is the maximum running time?
why the answer is q X(σ^hk)X(h^k) ?
And what is σ^hk and h^k means? thanks!

Answer 1

The key insight is that in order for a Turing machine to halt, it cannot enter a loop. Since a Turing machine will always follow the same sequence after being a specific state, if it ever becomes that same state twice, we know the machine is caught in an infinite loop and will never finish. Therefore, the theoretical maximum number of steps it can run is the maximum number of possible different states for the machine without being the same exact state twice.

In this example, a unique state is made of:

1. the values on each of the k tapes (maximum of h cells),
2. the current state of the machine (1 of q possibilities),
3. the current position of each of the k machine heads.

Since there are σ possible symbols, that means each of the h cells on each of the k tapes can be one of σ possible values. There are a total of hk cells between all of the tapes, and they can each independently be one of σ values. So the total possible combinations is σ^(h*k) - this addresses (1). The expression literally means (number of possible alphabet symbols) ^ (max number of cells * number of tapes).

For (2), there is an additional q combination of states that can be in effect for every combination of tape cells. That gives an additional factor of q to the theoretical maximum.

For (3), each of the machine heads can also independently be in one of the h possible cell locations for each of the k tape. This adds another factor of h^k possible states.

So the total number of possible states is the product of q * σ^(h*k) * h^k