Dictionaries › English

time-constructible function

The English word “time-constructible function” has 1 meaning listed here.

noun

  1. 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.
Keep exploring: in the interactive dictionary every word of a definition is a link. Open “time-constructible function” there

More English words

About this dictionary

The English dictionary on Glottosphere has 650,529 entries with a page. Browse the English dictionary.

Definitions are from Wiktionary, extracted by Kaikki.org, and are available under the CC BY-SA 4.0 licence.