User:Qwerpiw/Tₘ function - Revision history

RobinCodes: Removed from stubs

2025-11-04T18:33:22Z

Removed from stubs

← Older revision		Revision as of 18:33, 4 November 2025
Line 1:		Line 1:
	{{DISPLAYTITLE:T<sub>M</sub> function~~}}{{stub~~}}		{{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.

LegionMammal978: LegionMammal978 moved page Tₘ function to User:Qwerpiw/Tₘ function without leaving a redirect: Doesn't belong in the main namespace

2025-11-04T18:27:40Z

LegionMammal978 moved page Tₘ function to User:Qwerpiw/Tₘ function without leaving a redirect: Doesn't belong in the main namespace

← Older revision		Revision as of 18:27, 4 November 2025
(No difference)

Int-y1: stub

2025-08-25T08:51:20Z

stub

← Older revision		Revision as of 08:51, 25 August 2025
Line 1:		Line 1:
	{{DISPLAYTITLE:T<sub>M</sub> function}}		{{DISPLAYTITLE:T<sub>M</sub> function}}{{stub}}

	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.

Qwerpiw at 19:07, 6 August 2025

2025-08-06T19:07:20Z

← Older revision		Revision as of 19:07, 6 August 2025
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]]

Qwerpiw: Qwerpiw moved page T M function to Tₘ function

2025-08-06T19:04:59Z

Qwerpiw moved page T M function to Tₘ function

← Older revision		Revision as of 19:04, 6 August 2025
(No difference)

Qwerpiw: 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_M(u) . For every n >= 1 we define T_M(..."

2025-08-06T18:43:46Z

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 TM(u) . For every n >= 1 we define TM(..."

New page

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)$.
<ref> https://mathoverflow.net/questions/307607/time-functions-of-non-deterministic-turing-machines-a-better-question/307614</ref>[[Category:Functions]]