Computable Functions and Lambda Calculus
A function F: N → N of natural numbers is a computable function if and only if there exists a lambda expression f such that for every pair of x, y in N, F(x)=y if and only if f x =β y, where x and y are the Church numerals corresponding to x and y, respectively and =β meaning equivalence with beta reduction. This is one of the many ways to define computability; see the Church-Turing thesis for a discussion of other approaches and their equivalence.
Read more about this topic: Lambda Calculus
Famous quotes containing the words functions and/or calculus:
“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)
“I try to make a rough music, a dance of the mind, a calculus of the emotions, a driving beat of praise out of the pain and mystery that surround me and become me. My poems are meant to make your mind get up and shout.”
—Judith Johnson Sherwin (b. 1936)