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:

    “Truth is used to vitalize a statement rather than devitalize it. Truth implies more than a simple statement of fact. “I don’t have any whisky,” may be a fact but it is not a truth.”
    —William Burroughs (b. 1914)

    “After the first powerful plain manifesto
    The black statement of pistons, without more fuss
    But gliding like a queen, she leaves the station.”
    —Stephen Spender (1909–1995)

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