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.

Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

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

plural time-constructible functions

  1. countableuncountablecomputational complexity theoryA 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.
Cite this entry
APA

time-constructible function. (n.d.). In WatkinsX Dictionary. Retrieved November 2, 2026, from https://dictionary.watkinsx.com/word/time-constructible%20function

MLA

“time-constructible function.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/time-constructible%20function. Accessed November 2, 2026.

Chicago

WatkinsX Dictionary, s.v. “time-constructible function,” accessed November 2, 2026, https://dictionary.watkinsx.com/word/time-constructible%20function.

Source: time-constructible function on Wiktionary, CC BY-SA 4.0.