Constructible function - Revision history

imported>TeaTowel341076: /* growthexperiments-addlink-summary-summary:1|1|0 */

2025-12-28T22:18:58Z

growthexperiments-addlink-summary-summary:1|1|0

← Previous revision		Revision as of 22:18, 28 December 2025
Line 1:		Line 1:
	{{Short description\|Concept in complexity theory}}		{{Short description\|Concept in complexity theory}}
	In [[computational complexity theory\|complexity theory]], a '''time-constructible function''' is a function ''f'' from [[natural numbers]] to natural numbers with the property that ''f''(''n'') can be constructed from ''n'' by a [[Turing machine]] in the time of order ''f''(''n''). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.<ref name=":0">{{Cite book\|title=Computational Complexity: A Conceptual Perspective\|last=Goldreich\|first=Oded\|publisher=Cambridge University Press\|year=2008\|isbn=978-0-521-88473-0\|pages=130, 139}}</ref>		In [[computational complexity theory\|complexity theory]], a '''time-constructible function''' is a function ''f'' from [[natural numbers]] to natural numbers with the property that ''f''(''n'') can be constructed from ''n'' by a [[Turing machine]] in the time [[big O notation\|of order]] ''f''(''n''). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.<ref name=":0">{{Cite book\|title=Computational Complexity: A Conceptual Perspective\|last=Goldreich\|first=Oded\|authorlink = Oded Goldreich\|publisher=Cambridge University Press\|year=2008\|isbn=978-0-521-88473-0\|pages=130, 139}}</ref>

	==Time-constructible==		==Time-constructible==
	Let the Turing machine be defined in the standard way, with an alphabet that includes the symbols <math>0, 1</math>. It has a standard input tape containing zeros except for an input string. Let <math>1^n</math> denote a string composed of <math>n</math> ones. That is, it's the [[Unary numeral system\|unary representation]]. Let <math>\|n\|</math> be the binary representation.		Let the Turing machine be defined in the standard way, with an alphabet that includes the symbols <math>0, 1</math>. It has a standard input tape containing zeros except for an input string. Let <math>1^n</math> denote a string composed of <math>n</math> ones. That is, it's the [[Unary numeral system\|unary representation]] of <math>n</math>. Let <math>\|n\|</math> be the [[Binary number\|binary representation]].

	~~There are two different definitions of a~~ '''time-constructible ~~function~~'''.		A function <math>f</math> is called '''time-constructible''' if there exists a Turing machine <math>M</math> such that the computation <math>M(1^n)</math> halts in <math>O(f(n))</math> steps with value <math>\|f(n)\|</math>.

	In the first definition, a function <math>f</math> is called time-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n)</math> halts in <math>O(f(n))</math> steps.		This definition may use <math>M(1^n) = 1^{f(n)}</math> instead, since the two can be interconverted in <math>O(f(n))</math> steps.<ref name=":0" />

	In the second definition, a function <math>f</math> is called time-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n) = \|f(n)\|</math> and halts in <math>O(f(n))</math> steps.

	~~The second~~ definition may use <math>M(1^n) = 1^{f(n)}</math> instead, since the two can be interconverted in <math>O(f(n))</math> steps.<ref name=":0" />

	=== Fully time-constructable ===		=== Fully time-constructable ===
	There is also a notion of a '''''fully'' time-constructible function'''.		There is also a notion of a '''''fully'' time-constructible function'''.

	A function <math>f</math> is called fully time-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n)</math> halts in ''exactly'' <math>f(n)</math> steps.<ref name=":2">{{Cite book \|last1=Homer \|first1=Steven \|title=Computability and Complexity Theory \|last2=Selman \|first2=Alan L. \|publisher=Springer \|year=2011 \|isbn=978-1-4614-0681-5 \|edition=Second}}</ref> This definition is slightly less general than the first ~~two~~ but, for most applications, either definition can be used.<ref name=":1">{{Cite book		A function <math>f</math> is called fully time-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n)</math> halts in ''exactly'' <math>f(n)</math> steps.<ref name=":2">{{Cite book \|last1=Homer \|first1=Steven \|title=Computability and Complexity Theory \|last2=Selman \|first2=Alan L. \|author2link = Alan Selman\|publisher=Springer \|year=2011 \|isbn=978-1-4614-0681-5 \|edition=Second}}</ref> This definition is slightly less general than the first, but for most applications, either definition can be used.<ref name=":1">{{Cite book
	\|title=Structural Complexity I		\|title=Structural Complexity I
	\|last1=Balcázar		\|last1=Balcázar
Line 28:		Line 24:
	\|year=1988}}</ref> The following equivalence theorem shows that these two concepts are equivalent for most functions used in practice:		\|year=1988}}</ref> The following equivalence theorem shows that these two concepts are equivalent for most functions used in practice:

	Theorem.<ref name=":1" />{{Pg\|location=Theorem 2.6}} If <math>f</math> is a function such that there exists <math>\epsilon > 0</math> such that, for all but finitely many <math>n</math>, <math>f(n) \geq (1+ \epsilon) n</math>~~, then <math>f</math> is time-constructible iff it~~ is ~~fully time-constructible.~~		Theorem.<ref name=":1" />{{Pg\|location=Theorem 2.6}} If <math>f</math> is a function such that there exists <math>\epsilon > 0</math> such that, for all but finitely many <math>n</math>, <math>f(n) \geq (1+ \epsilon) n</math> (that is, if <math>f(n) - n = \Omega(n)</math>), then <math>f</math> is time-constructible if and only if it is fully time-constructible.

	~~More succinctly~~, ~~the condition states that~~ <math>f(n) - n = \Omega(n)</math>.

	==Space-constructible==		==Space-constructible==
	~~Function~~ <math>f</math> is called space-constructible, if there exists a Turing machine <math>M</math>, such that ~~for all but finitely many~~ <math>n</math>, <math>~~M(1^n) =~~ \|f(n)\|</math> (or equivalently <math>1^{f(n)}</math>), while using <math>O(f(n))</math> space.<ref name=":0" />		A function <math>f</math> is called '''space-constructible''' if there exists a Turing machine <math>M</math> such that <math>M(1^n)</math> halts with value <math>\|f(n)\|</math> (or equivalently <math>1^{f(n)}</math>), while using <math>O(f(n))</math> space.<ref name=":0" />

	Equivalently, if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math> ~~given~~ <math>1^n</math>, halts in a configuration in which exactly <math>f(n)</math> cells are not blank, and no other cell has been written to during its operation.<ref name=":1" />{{Pg\|location=Definition 2.4}} This is sometimes called "fully space-constructible". However, the two definitions are equivalent.<ref name=":1" />{{Pg\|location=Theorem 2.7}}		Equivalently, <math>f</math> is called space-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, the computation <math>M(1^n)</math> halts in a configuration in which ''exactly'' <math>f(n)</math> cells are not blank, and no other cell has been written to during its operation.<ref name=":1" />{{Pg\|location=Definition 2.4}} This is sometimes called "fully space-constructible". However, the two definitions are equivalent.<ref name=":1" />{{Pg\|location=Theorem 2.7}}

	==Properties==		==Properties==
	All the commonly used functions (such as <math>n, n^2, 2^n, n!</math>) are time- and space-constructible, as long as <math>f(n) = \Omega(n)</math>. The construction is straightforward. For example, <math>n^2</math> is constructed by one for-loop, while <math>n^3</math> is constructed by two for-loops, etc.		All the commonly used functions (such as <math>n, n^2, 2^n, n!</math>) are time- and space-constructible, as long as <math>f(n) = \Omega(n)</math>. The construction is straightforward. For example, <math>n^2</math> is constructed by one nested for-loop, while <math>n^3</math> is constructed by two nested for-loops, etc.

	If <math>f(n) = o(n)</math> is time-constructible, then it is eventually constant, since otherwise there is insufficient time to read the entire input.		If <math>f(n) = o(n)</math> is time-constructible, then it is eventually constant, since otherwise there is insufficient time to read the entire input.
Line 45:		Line 39:
	</math>.		</math>.

	For every ~~recursive~~ function <math>f</math>, there is a ~~recursive~~ function <math>g</math> ~~which~~ is time constructible and <math>\forall n, g(n) > f(n)</math>.<ref name=":1" />{{Pg\|location=Lemma 2.3}}		For every [[computable function]] <math>f</math>, there is a computable function <math>g</math> that is time constructible and <math>\forall n, g(n) > f(n)</math>.<ref name=":1" />{{Pg\|location=Lemma 2.3}}

	==Applications==		==Applications==

imported>Cosmia Nebula: /* Space-constructible */ fully

2025-03-10T01:32:13Z

Space-constructible: fully

New page

{{Short description|Concept in complexity theory}}
In [[computational complexity theory|complexity theory]], a '''time-constructible function''' is a function ''f'' from [[natural numbers]] to natural numbers with the property that ''f''(''n'') can be constructed from ''n'' by a [[Turing machine]] in the time of order ''f''(''n''). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.<ref name=":0">{{Cite book|title=Computational Complexity: A Conceptual Perspective|last=Goldreich|first=Oded|publisher=Cambridge University Press|year=2008|isbn=978-0-521-88473-0|pages=130, 139}}</ref>

==Time-constructible==
Let the Turing machine be defined in the standard way, with an alphabet that includes the symbols <math>0, 1</math>. It has a standard input tape containing zeros except for an input string. Let <math>1^n</math> denote a string composed of <math>n</math> ones. That is, it's the [[Unary numeral system|unary representation]]. Let <math>|n|</math> be the binary representation.

There are two different definitions of a '''time-constructible function'''.

In the first definition, a function <math>f</math> is called time-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n)</math> halts in <math>O(f(n))</math> steps.

In the second definition, a function <math>f</math> is called time-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n) = |f(n)|</math> and halts in <math>O(f(n))</math> steps.

The second definition may use <math>M(1^n) = 1^{f(n)}</math> instead, since the two can be interconverted in <math>O(f(n))</math> steps.<ref name=":0" />

=== Fully time-constructable ===
There is also a notion of a '''''fully'' time-constructible function'''.

A function <math>f</math> is called fully time-constructible if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n)</math> halts in ''exactly'' <math>f(n)</math> steps.<ref name=":2">{{Cite book |last1=Homer |first1=Steven |title=Computability and Complexity Theory |last2=Selman |first2=Alan L. |publisher=Springer |year=2011 |isbn=978-1-4614-0681-5 |edition=Second}}</ref> This definition is slightly less general than the first two but, for most applications, either definition can be used.<ref name=":1">{{Cite book
|title=Structural Complexity I
|last1=Balcázar
|first1=José Luis
|last2=Díaz
|first2=Josep
|last3=Gabarró
|first3=Joaquim
|isbn=3-540-18622-0
|publisher=Springer-Verlag
|year=1988}}</ref> The following equivalence theorem shows that these two concepts are equivalent for most functions used in practice:

Theorem.<ref name=":1" />{{Pg|location=Theorem 2.6}} If <math>f</math> is a function such that there exists <math>\epsilon > 0</math> such that, for all but finitely many <math>n</math>, <math>f(n) \geq (1+ \epsilon) n</math>, then <math>f</math> is time-constructible iff it is fully time-constructible.

More succinctly, the condition states that <math>f(n) - n = \Omega(n)</math>.

==Space-constructible==
Function <math>f</math> is called space-constructible, if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math>, <math>M(1^n) = |f(n)|</math> (or equivalently <math>1^{f(n)}</math>), while using <math>O(f(n))</math> space.<ref name=":0" />

Equivalently, if there exists a Turing machine <math>M</math>, such that for all but finitely many <math>n</math> given <math>1^n</math>, halts in a configuration in which exactly <math>f(n)</math> cells are not blank, and no other cell has been written to during its operation.<ref name=":1" />{{Pg|location=Definition 2.4}} This is sometimes called "fully space-constructible". However, the two definitions are equivalent.<ref name=":1" />{{Pg|location=Theorem 2.7}}

==Properties==
All the commonly used functions (such as <math>n, n^2, 2^n, n!</math>) are time- and space-constructible, as long as <math>f(n) = \Omega(n)</math>. The construction is straightforward. For example, <math>n^2</math> is constructed by one for-loop, while <math>n^3</math> is constructed by two for-loops, etc.

If <math>f(n) = o(n)</math> is time-constructible, then it is eventually constant, since otherwise there is insufficient time to read the entire input.

<math>\ln n</math> is space-constructible even though <math>\ln n = o(n)
</math>.

For every recursive function <math>f</math>, there is a recursive function <math>g</math> which is time constructible and <math>\forall n, g(n) > f(n)</math>.<ref name=":1" />{{Pg|location=Lemma 2.3}}

==Applications==
Time-constructible functions are used in results from complexity theory such as the [[time hierarchy theorem]]. They are important because the time hierarchy theorem relies on Turing machines that must determine in ''[[big-O notation|O]]''(''f''(''n'')) time whether an algorithm has taken more than ''f''(''n'') steps. This is, of course, impossible without being able to calculate ''f''(''n'') in that time. Such results are typically true for all natural functions ''f'' but not necessarily true for artificially constructed ''f''. To formulate them precisely, it is necessary to have a precise definition for ''a natural function f'' for which the theorem is true. Time-constructible functions are often used to provide such a definition.

Space-constructible functions are used similarly, for example in the [[space hierarchy theorem]].

==References==
{{PlanetMath attribution|id=3461|title=constructible}}
{{Reflist}}

[[Category:Computational complexity theory]]
[[Category:Types of functions]]