Space-constructible Definitions
Similarly, a function f is space-constructible if there exists a positive integer n0 and a Turing machine M which, given a string 1n consisting of n ones, halts after using exactly f(n) cells for all n ≥ n0. Equivalently, a function f is space-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, outputs the binary (or unary) representation of f(n), while using only O(f(n)) space.
Also, a function f is fully space-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, halts after using exactly f(n) cells.
Read more about this topic: Constructible Function
Famous quotes containing the word definitions:
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)