Application To Computable Functions
Goodstein's theorem can be used to construct a total computable function that Peano arithmetic cannot prove to be total. The Goodstein sequence of a number can be effectively enumerated by a Turing machine; thus the function which maps n to the number of steps required for the Goodstein sequence of n to terminate is computable by a particular Turing machine. This machine merely enumerates the Goodstein sequence of n and, when the sequence reaches 0, returns the length of the sequence. Because every Goodstein sequence eventually terminates, this function is total. But because Peano arithmetic does not prove that every Goodstein sequence terminates, Peano arithmetic does not prove that this Turing machine computes a total function.
Read more about this topic: Goodstein's Theorem
Famous quotes containing the words application to, application and/or functions:
“The receipt to make a speaker, and an applauded one too, is short and easy.—Take of common sense quantum sufficit, add a little application to the rules and orders of the House, throw obvious thoughts in a new light, and make up the whole with a large quantity of purity, correctness, and elegancy of style.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“We will not be imposed upon by this vast application of forces. We believe that most things will have to be accomplished still by the application called Industry. We are rather pleased, after all, to consider the small private, but both constant and accumulated, force which stands behind every spade in the field. This it is that makes the valleys shine, and the deserts really bloom.”
—Henry David Thoreau (1817–1862)
“Mark the babe
Not long accustomed to this breathing world;
One that hath barely learned to shape a smile,
Though yet irrational of soul, to grasp
With tiny finger—to let fall a tear;
And, as the heavy cloud of sleep dissolves,
To stretch his limbs, bemocking, as might seem,
The outward functions of intelligent man.”
—William Wordsworth (1770–1850)