Hello, you have come here looking for the meaning of the word
time-constructible function. In DICTIOUS you will not only get to know all the dictionary meanings for the word
time-constructible function, but we will also tell you about its etymology, its characteristics and you will know how to say
time-constructible function in singular and plural. Everything you need to know about the word
time-constructible function you have here. The definition of the word
time-constructible function will help you to be more precise and correct when speaking or writing your texts. Knowing the definition of
time-constructible function, as well as those of other words, enriches your vocabulary and provides you with more and better linguistic resources.
English
Noun
time-constructible function (countable and uncountable, plural time-constructible functions)
- (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.