## The most amazing fact

A charming discussion of what should be called the fundamental theorem of computation theory, in Epstein and Carnielli, Computability: Computable Functions, Logic, and the Foundations of Mathematics (2008):

We have studied one formalization of the notion of computability. In succeeding chapters we will study two more: recursive functions and functions representable in a formal system.

The Most Amazing Fact
All the attempts at formalizing the intuitive notion of computable function yield exactly the same class of functions.

So if a function is Turing machine computable, it can also be computed in any of the other systems described in Chapter 8.E. This is a mathematical fact which requires a proof. […] Odifreddi, 1989 establishes all the equivalences. […]

The Most Amazing Fact is stated about an extensional class of functions, but it can be stated constructively: Any computation procedure for any of the attempts at formalizing the intuitive notion of computable function can be translated into any other formalization in such a way that the two formalizations have the same outputs for the same inputs.

In 1936, even before these equivalences were established, Church said,

We now define the notion, already discussed, of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a lambda-definable function of positive integers). This definition is thought to be justified by the considerations which follow, so far as positive justification can ever be obtained for the selection of a formal definition to correspond to an intuitive notion.

So we have

Church’s Thesis: A function is computable iff it is lambda-definable.

This is a nonmathematical thesis: it equates an intuitive notion (computability) with a precise, formal one (lambda-definability). By our amazing fact this thesis is equivalent to

A function is computable iff it is Turing machine computable.

Turing devised his machines in a conscious attempt to capture in simplest terms what computability is. That his model turned out to give the same class of functions as Church’s (as established by Turing in the paper cited above) was strong evidence that it was the “right” class. Later we will consider some criticisms of Church’s Thesis in that the notion of computability should coincide with either a larger or a small class than the Turing machine computable ones.

## The immediate perceptive epithet

from Bruce Wilshire, “William James’s Pragmatism: A Distinctly Mixed Bag,” in 100 Years of Pragmatism, edited by John Stuhr:

William James is a tragic figure. I will try to fully explain what I mean by that. But right off the bat, we can point out a feature of this tragic stance. It’s fairly widely believed that James is a major philosopher. Yet in no other such philosopher’s work, I believe, are great strengths so vividly mixed with major defects. His famous, often read—too often read, I think—popular lectures, Pragmatism, gaudily illustrate this claim.

What does it take to be a major philosopher? A most difficult question. Wilfrid Sellars’s one-liner statement of what philosophy seeks to discover is hard to better: how things, in the broadest sense, hang together, in the broadest sense.

But how does one start a process of discovery without begging crucial questions that philosophy should endeavor to answer? How does one begin to comprehend the farthest reaches of complexity without prejudging things—or occluding whole horizons of possibilities and viewpoints—stupidly? James’s description in Pragmatism of expertness in philosophy is arresting: “Expertness in philosophy is measured by the definiteness of our summarizing reactions, by the immediate perceptive epithet with which the expert hits such complex objects off” (P, 25). Thee summarizing that emerges through perceptual epithet! A taking in at a glance that delivers the first sketch of the whole lay of the land. Is there any better way to avoid getting lost in the details of some corner of the subject matter, any better way to begin doing philosophy unprejudiciously?