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.
随便看	Riemann-Hurwitz theorem RiemannianManifold Riemannian manifold RiemannianManifoldsCategoryRM Riemannian manifolds category R_M RiemannIntegral Riemann integral RiemannLebesgueLemma Riemann-Lebesgue lemma RiemannMappingTheorem Riemann mapping theorem RiemannMultipleIntegral Riemann multiple integral RiemannNormalCoordinates Riemann normal coordinates RiemannRochTheoremForCurves Riemann-Roch theorem for curves RiemannsRemovableSingularityTheorem RiemannsRemovableSingularityTheoremInSeveralVariables RiemannsTheoremOnIsolatedSingularities RiemannsTheoremOnRearrangements RiemannStieltjesIntegral Riemann-Stieltjes integral RiemannSum Riemann sum