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:
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)