User:Qwerpiw/Tₘ function: Difference between revisions
Jump to navigation
Jump to search
stub |
RobinCodes (talk | contribs) Removed from stubs |
||
| (One intermediate revision by one other user not shown) | |||
| 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]