Tₘ function: Difference between revisions
Jump to navigation
Jump to search
(Created page with "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<sub>M</sub>(u) . For every n >= 1 we define T<sub>M</sub>(...") |
m (Qwerpiw moved page T M function to Tₘ function) |
Revision as of 19:04, 6 August 2025
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 TM(u) . For every n >= 1 we define TM(n) the maximum of all TM(u) for all accepted u of length <= n. Then TM(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)$. [1]