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:
“Empirical science is apt to cloud the sight, and, by the very knowledge of functions and processes, to bereave the student of the manly contemplation of the whole.”
—Ralph Waldo Emerson (1803–1882)
“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)