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:

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

    “No statement about God is simply, literally true. God is far more than can be measured, described, defined in ordinary language, or pinned down to any particular happening.”
    —David Jenkins (b. 1925)

    “The most distinct and beautiful statement of any truth must take at last the mathematical form.”
    —Henry David Thoreau (1817–1862)