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

Answer 2

Think of your Turing machine as a Linear Bounded Automaton (LBA), that works within the bound of h*k. Let's first consider single tape machine.

For a single tape LBA, if a LBA has:

1) q states 2) g symbols in its tape alphabet, and 3) an input of length n,

then the number of its possible configurations is q * n * g^n for a single tape LBA. Proof of halting problem on LBA

Put it simple, that for a single tape LBA, we have g^n possible tapes, and there are n possible positions for the head to point to, and q states the machine could be in. Hence we have q * n * g^n configurations.

To generalize it for a k-tape machine, there are (g^n)^k possible tape configurations. There are n ^ k possible configurations for all tape heads (since you can move some or all tape heads at the same time), and q states the machine could be possibly in. Thus the number of distinct configurations would then be q * (n ^ k) * g^(nk)

Change n to your h, which is literally the length for single tape LBA, and g to your σ, there is the answer.