constructible

A function $f:\\mathbb{N}\\rightarrow\\mathbb{N}$ is time constructible if there is a deterministic Turing machine $T$ (with alphabet $\\{0,1,B\\}$ ) such that when $T$ receives as input the a series of $n$ ones, it halts after exactly $f(n)$ steps. Similarly $f$ is space constructible if there is a similar Turing machine which halts after using exactly $f(n)$ cells.

Most ’natural’ functions are both time and space constructible, including constant functions, polynomials, and exponentials, for example.

单词	Constructible
释义	constructible A function $f:\\mathbb{N}\\rightarrow\\mathbb{N}$ is time constructible if there is a deterministic Turing machine $T$ (with alphabet $\\{0,1,B\\}$ ) such that when $T$ receives as input the a series of $n$ ones, it halts after exactly $f(n)$ steps. Similarly $f$ is space constructible if there is a similar Turing machine which halts after using exactly $f(n)$ cells. Most ’natural’ functions are both time and space constructible, including constant functions, polynomials, and exponentials, for example.
随便看	HammingMetric Hamming metric HamSandwichTheorem ham sandwich theorem HandleDecomposition handle decomposition HandshakeLemma handshake lemma HankelContourIntegral Hankel contour integral HannaNeumann Hanna Neumann HappyEndingProblem happy ending problem HappyNumber happy number HardyLittlewoodMaximalOperator Hardy-Littlewood maximal operator HardyLittlewoodMaximalTheorem Hardy-Littlewood maximal theorem HardysInequality HardysTheorem Hardy’s inequality Hardy’s theorem HarmonicConjugateFunction