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>(...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{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. | ||
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". | 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>(n) the maximum of all T<sub>M</sub>(u) for all accepted u of length <= n. Then T<sub>M</sub>(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 | 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>(n) the maximum of all T<sub>M</sub>(u) for all accepted u of length <= n. Then T<sub>M</sub>(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$. | ||
<ref> https://mathoverflow.net/questions/307607/time-functions-of-non-deterministic-turing-machines-a-better-question/307614</ref>[[Category:Functions]] | <ref> https://mathoverflow.net/questions/307607/time-functions-of-non-deterministic-turing-machines-a-better-question/307614</ref>[[Category:Functions]] | ||
Latest revision as of 19:07, 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]