Raymond Smullyan on Self Reference

This nice book is a tribute to Raymond Smullyan (1919–2017), who according to Wikipedia, was an eminent mathematician, magician, concert pianist, logician, Taoist and philosopher. He is one of many logicians to have studied with Alonzo Church.

The book under review collects contributions honoring Smullyan’s work on self-reference. Smullyan’s very first published paper was “Languages in which self-reference is possible” (J. Symb. Logic, 22, 1957). This rather obviously deals with self-reference, but the basic motivation was to strip off as much of the formal machinery as possible, to get at the essence of what going on in Gödel’s proof. This minimalist (or Taoist) approach is well explained in the introduction, written with true skill by his student and collaborator Melvin Fitting.

Smullyan wrote several books that have been influential, often in unexpected ways. His first book, Theory of Formal Systems (1961), was a novel presentation of recursion theory and the incompleteness theorems, topics he returned to often throughout his career. Smullyan’s second book, First-Order Logic (1968), was intended to be an elegant and beautiful presentation of formal logic. There were several other books devoted to his research in mathematical logic: Gödel’s Incompleteness Theorems (1992), Recursion Theory for Metamathematicians (1993), Diagonalization and Self-reference (1994) and, jointly with Melvin Fitting, Set Theory and the Continuum Problem (1996).

In the 1970s, even while continuing his formal mathematical logic researches, Smullyan developed an interest in puzzles, especially those that were based on mathematical logic. Martin Gardner devoted a column in Scientific American to some of these puzzles, and they turned out to be quite popular. This led to What is the Name of This Book? (1978). It turned out to be an unexpected success and was followed by This Book Needs No Title (1980), Alice in Puzzle-Land (1982), and many others.

At some point Smullyan decided that puzzles could be used to teach some of the fundamental discoveries in modern logic. This idea was implemented in The Lady or the Tiger? (1982), which actually led the readers through the basic ideas of Gödel’s incompleteness theorems, via a series of puzzles. That was followed by To Mock a Mockingbird (1985), which explored the Lambda-calculus via puzzles about birds.

This book gathers ten elegant contributions on the themes dear to Raymond Smullyan They are preceded by an introduction, written by Melvin Fitting and are followed by a complete bibliography of Smullyan’s writings.

Robert L. Constable’s “Formal Systems, Logics and Programs” is devoted to proof assistants, that is, software assistants for humans attempting to provide correct proofs. In this article two successful uses of the proof assistant Nuprl (now maintained by the PRL Project at Cornell University) are discussed in an informal way. The first is the formalization of a fundamental result from Smullyan’s book First Order Logic: an assignment of truth values to propositional variables extends to at most one assignment of truth values to all propositional formulas that respects the logical connectives. The second involvement of Nuprl has to do with the formalization of the halting problem in constructive type theory.

The third chapter of the book is the interesting “Adaptive Fault Diagnosis using Self Reference Reasoning” by Robert Cowen. Processors are much like Smullyan’s Knights, who are truth-telling. Knaves, who lie, and Normals, who sometimes lie and sometimes tell the truth. The aim of the paper is to make use of self-referential questions, Smullyan-style, to determine the reliability of processors at a distance, say in space or in a nuclear reactor. For this purpose, both Knights and Knaves are considered reliable: if we know a processor is Knave-like (or Knight-like), we know how make use of its answers. It is the Normals who are the problem. Cowen provides an algorithm for excluding Normals using self-referential questions, subject to the condition that more than half the processors are reliable.

In “Russell’s Paradox, Gödel’s Theorem”, Melvin Fitting examines Smullyan’s proofs of incompleteness theorems. His purpose is to show that Gödel’s ideas fit naturally into the context of the elementary set theory that any mathematics student would know. Combining the spirt of both Smullyan’s formal and his popular work, Fitting shows how Russel’s paradox can be used in a direct and natural way to obtain Gödel’s incompleteness results.

The joint work “Dance of the Starlings”, by H. Barendregt, J. Endrullis, J. W. Klop and J. Waldmann is an essay on Lambda calculus in the Smullyan’s style. It is full of beautiful and artistic illustrations.

The essay “Some Tweets About Mockingbirds” of Rick Statam is, like “Dance of the Starlings”, another paper about combinatorial logic, derived from Smullyan’s To Mock a Mockinbird. In his book Smullyan asked whether a fixed point combinator could be constructed from his Bluebird, Identity bird and Mockinbird combinators B, I, and M.

This is still not known, but the present paper is an examination of some closely related questions.

Stephen Yablo, David W. Skinner Professor of Linguistics and Philosophy at the Massachusetts Institute of Technology, also known for his “Paradox without Self-Reference” (Analysis, 53, 1993), contributed to this book with “Knights, Knaves, Truth, Truthfulness, Grounding, Tethering, Aboutness, and Paradox.” In this paper, which is of both philosophical and technical interest, recent theories of truth and self-reference are examined for what they have to say about an issue which is, as the paper says, a “problem not apparent even to veteran paradox-mongers” and “is a datum in need of explanation.” The paper provides a profound attempt for a solution.

Martin Davis’ paper “What I Tell You Three Times Is True”, is an attempt to establish a connection between Smullyan’s use of self-reference and self-referentiality in art. The references to Laurence Sterne (The Life and Opinion of Tristram Shandy, Gentleman) in literature and to René Magritte, Diego Velazques, and Saul Steinberg in the graphic arts cannot be missed.

The chapter 9 of the book contains the article “Gödel, Lucas, and Soul-Searching Selfie”, written by Vann McGee. In this paper, Mechanism is understood to be “the doctrine that the symbol-producing capabilities of the human mind can be simulated by a finite machine.” This is, of course, weaker than simply asserting that the mind is a machine. But it is a doctrine that has gathered about it many attempts to say something rigorous in its defense, or the opposite. Well-known names here include Lucas, Penrose, Putnam, and many others, all of whom argued against Mechanism. McGinn’s true goal is to argue against Lucas’s thesis.

Andrew G. Buchanan and John H. Conway wrote the piece “An Island Tale for young Anthropologists.” Here is the description that they themselves offer: “In which the fictional Professor Kit Sune explores the Archipelago of Ambiguity, following in the footsteps of an earlier explorer, Raymond Smullyan. Here, she reviews the great progress made in Knight-Knave studies since Smullyan’s seminal work. In the process, she discovers an eight-word question she can repeat three times to identify three natives’ tribal affiliations. She also gives an answer to a knotty problem posed by Simon Norton. After pausing to gasp in horror at the looming “Knownot Apocalypse”, she finishes by posing 14 open Knight-Knave questions.”

The book ends with the essay by Walter Carnielli on “Making the `Hardest Logic Puzzle Ever’ Endlessy Harder.” In “The Hardest Logic Puzzle Ever” (The Harvard Review of Philosophy, 1996) George Boolos introduced what he claimed was the hardest logic puzzle ever, which he credited as originating with Raymond Smullyan but with an important complication added by John McCarthy. There are three gods, one a liar, one a truth teller, and one who answers randomly. Of course, you are not told which are which. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which. You must figure out who the truth teller is, who is the liar and who is the randomizer, by asking yes/no questions. Because of the random answerer, three valued logic is implicit in the formulation of the puzzle, but solutions are usually considered to be based on classical logic. In this paper the author considers the explicit use of three-valued logic not only for solving the puzzle but for producing versions that, in some sense, are still harder.

Enrico Jabara (jabara@unive.it) is at the Department of Philosophy and Cultural Heritage of the Università Ca’Foscari in Venice.