Space Hierarchy Theorem - Statement

Statement

Formally, a function is space-constructible if and there exists a Turing machine which computes the function in space when starting with an input, where represents a string of s. Most of the common functions that we work with are space-constructible, including polynomials, exponents, and logarithms.

For every space-constructible function f:\mathbb{N} \longrightarrow
\mathbb{N}, there exists a language that is decidable in space but not in space .

Read more about this topic:  Space Hierarchy Theorem

Famous quotes containing the word statement:

    The new statement will comprise the skepticisms, as well as the faiths of society, and out of unbeliefs a creed shall be formed. For, skepticisms are not gratuitous or lawless, but are limitations of the affirmative statement, and the new philosophy must take them in, and make affirmations outside of them, just as much as must include the oldest beliefs.
    Ralph Waldo Emerson (1803–1882)

    A sentence is made up of words, a statement is made in words.... Statements are made, words or sentences are used.
    —J.L. (John Langshaw)

    The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.
    Nicholson Baker (b. 1957)