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:

    “It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
    —John Dewey (1859–1952)

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

    “If we do take statements to be the primary bearers of truth, there seems to be a very simple answer to the question, what is it for them to be true: for a statement to be true is for things to be as they are stated to be.”
    —J.L. (John Langshaw)