Tₘ function

Let M be a non-deterministic Turing machine which recognizes a language L, that is, for every input word u there is an accepting computation with input u if and only if u ∈ L.

Let us assume that M terminates on every input. The simplest thing to assume is that if u ∈ L, the TM eventually gives "yes" and if u ∉ L, it gives "no".

The smallest time (number of steps) of such a computation is denoted by T_M(u) . For every n >= 1 we define T_M(n) the maximum of all T_M(u) for all accepted u of length <= n. Then T_M(n): N → N is the time function of M. If M is a deterministic Turing machine, then its time function T(n) is [constructible][2] that is there is a deterministic Turing machine which computes values T(n) in time ≈ T(n$.