To Mock a Mockingbird
Encyclopedia
To Mock a Mockingbird and Other Logic Puzzles: Including an Amazing Adventure in Combinatory Logic (1985, ISBN 0-19-280142-2) is a book by the mathematician
and logician Raymond Smullyan
. It contains many nontrivial recreational puzzles of the sort for which Smullyan is well-known. It is also a gentle and humorous introduction to combinatory logic
and the associated metamathematics
, built on an elaborate ornithological metaphor
.
Combinatory logic
, functionally equivalent to the lambda calculus
, is a branch of symbolic logic having the expressive power of set theory
, and with deep connections to questions of computability and provability
. Smullyan's exposition takes the form of an imaginary account of two men going into a forest and discussing the unusual "birds" (combinators) they find there (bird watching was a hobby of the inventor of combinatory logic, Haskell Curry
). Each species of bird in Smullyan's forest stands for a particular kind of combinator appearing in the conventional treatment of combinatory logic. Each bird has a distinctive call, which it emits when it hears the call of another bird. Hence an initial call by certain "birds" gives rise to a cascading sequence of calls by a succession of birds.
Deep inside the forest dwells the Mockingbird, which imitates other birds hearing themselves. The resulting cascade of calls and responses analogizes to abstract models of computing. With this analogy in hand, one can explore advanced topics in the mathematical theory of computability, such as Church-Turing Computability and Gödel's Theorem
.
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and logician Raymond Smullyan
Raymond Smullyan
Raymond Merrill Smullyan is an American mathematician, concert pianist, logician, Taoist philosopher, and magician.Born in Far Rockaway, New York, his first career was stage magic. He then earned a BSc from the University of Chicago in 1955 and his Ph.D. from Princeton University in 1959...
. It contains many nontrivial recreational puzzles of the sort for which Smullyan is well-known. It is also a gentle and humorous introduction to combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
and the associated metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
, built on an elaborate ornithological metaphor
Metaphor
A metaphor is a literary figure of speech that uses an image, story or tangible thing to represent a less tangible thing or some intangible quality or idea; e.g., "Her eyes were glistening jewels." Metaphor may also be used for any rhetorical figures of speech that achieve their effects via...
.
Combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
, functionally equivalent to the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, is a branch of symbolic logic having the expressive power of set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, and with deep connections to questions of computability and provability
Provability logic
Provability logic is a modal logic, in which the box operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich formal theory, such as Peano arithmetic....
. Smullyan's exposition takes the form of an imaginary account of two men going into a forest and discussing the unusual "birds" (combinators) they find there (bird watching was a hobby of the inventor of combinatory logic, Haskell Curry
Haskell Curry
Haskell Brooks Curry was an American mathematician and logician. Curry is best known for his work in combinatory logic; while the initial concept of combinatory logic was based on a single paper by Moses Schönfinkel, much of the development was done by Curry. Curry is also known for Curry's...
). Each species of bird in Smullyan's forest stands for a particular kind of combinator appearing in the conventional treatment of combinatory logic. Each bird has a distinctive call, which it emits when it hears the call of another bird. Hence an initial call by certain "birds" gives rise to a cascading sequence of calls by a succession of birds.
Deep inside the forest dwells the Mockingbird, which imitates other birds hearing themselves. The resulting cascade of calls and responses analogizes to abstract models of computing. With this analogy in hand, one can explore advanced topics in the mathematical theory of computability, such as Church-Turing Computability and Gödel's Theorem
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...
.
See also
- SKI combinator calculusSKI combinator calculusSKI combinator calculus is a computational system that may be perceived as a reduced version of untyped lambda calculus. It can be thought of as a computer programming language, though it is not useful for writing software...
- B,C,K,W systemB,C,K,W systemThe B, C, K, W system is a variant of combinatory logic that takes as primitive the combinators B, C, K, and W. This system was discovered by Haskell Curry in his doctoral thesis Grundlagen der kombinatorischen Logik, whose results are set out in Curry .The combinators are defined as follows:* B x...
- Fixed point combinatorFixed point combinatorIn computer science, a fixed-point combinator is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that x = f. For example, 0 and 1 are fixed points of the function f = x2, because 0 = 02 and 1 = 12...
- Lambda calculusLambda calculusIn mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
- Logic puzzleLogic puzzleA logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...
- Brain teaserBrain teaserA brain teaser is a form of puzzle that requires thought to solve. It often requires thinking in unconventional ways with given constraints in mind; sometimes it also involves lateral thinking. Logic puzzles and riddles are specific types of brain teasers....
- ParadoxParadoxSimilar to Circular reasoning, A paradox is a seemingly true statement or group of statements that lead to a contradiction or a situation which seems to defy logic or intuition...
External links
- Keenan, David C. (2001) "To Dissect a Mockingbird."
- Rathman, Chris, "Combinator Birds."