time-constructible function
Meanings
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.
Word forms
This entry uses open data from Wiktionary (CC BY-SA/GFDL). Word forms are used for search and are not indexed as separate pages.