Word.ws English Dictionary

time-constructible function

time-constructible function noun: 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), whose purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.

Noun

time-constructible function (countable and uncountable, plural time-constructible functions)

  1. (computational complexity theory) 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), whose purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.

Forms of time-constructible function

pluraltime-constructible functions

Questions about time-constructible function

What does time-constructible function mean?
Time-constructible function means 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), whose purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.
What part of speech is time-constructible function?
Time-constructible function is a noun.
What is the plural of time-constructible function?
The plural of time-constructible function is time-constructible functions.

Words near time-constructible function in the dictionary

  1. time-clause
  2. time-clauses
  3. time-compensated gain
  4. time-constant
  5. time-constants
  6. time-constructible function
  7. time-constructible functions
  8. time-consuming
  9. time-consumingly
  10. time-course
  11. time-courses

Source and license

Adapted from Wiktionary: time-constructible function (page history and authors). Text available under the Creative Commons Attribution-ShareAlike 4.0 license. Word.ws reformatted the entry and added links. Wiktionary data of 2026-09-02.

Last updated:

Cite this entry: “time-constructible function.” Word.ws, https://word.ws/time-constructible_function. Based on Wiktionary, CC BY-SA 4.0.