User:Qwerpiw/Tₘ function: Difference between revisions
Jump to navigation
Jump to search
m LegionMammal978 moved page Tₘ function to User:Qwerpiw/Tₘ function without leaving a redirect: Doesn't belong in the main namespace |
RobinCodes (talk | contribs) Removed from stubs |
||
| Line 1: | Line 1: | ||
{{DISPLAYTITLE:T<sub>M</sub> function | {{DISPLAYTITLE:T<sub>M</sub> 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 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. | ||
Latest revision as of 18:33, 4 November 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]