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 parent is the strongest statement that the child hears regarding what it means to be alive and real. More than what we say or do, the way we are expresses what we think it means to be alive. So the articulate parent is less a telling than a listening individual.”
    —Polly Berrien Berends (20th century)

    “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)

    “The new statement is always hated by the old, and, to those dwelling in the old, comes like an abyss of skepticism.”
    —Ralph Waldo Emerson (1803–1882)