Church, Alonzo (1903–1995)

views updated

CHURCH, ALONZO
(1903–1995)

Alonzo Church, an American logician and philosopher, was born in Washington, D.C. He received his PhD from Princeton in 1927, having written his dissertation under Oswald Veblen on alternatives to the axiom of choice. He spent a year at Harvard and then a year in Europe, studying first at Göttingen and then at Amsterdam with L.E.J. Brouwer. He returned to Princeton where he was professor of mathematics from 1929 to 1967, after which he moved to UCLA to become professor of mathematics and philosophy. He retired from teaching at UCLA in 1990. Church's most important contributions to logic were his analysis of the concept of effective computability and his proof of the undecidability of first-order logic (Church's theorem).

A function of natural number is effectively computable if there is an algorithm—a surefire method requiring no ingenuity to follow—that will yield the value of the function for any given natural number as input. Church devised a formal system, the lambda calculus (which subsequently became an important tool in computer science), and proposed that a function of natural numbers be taken to be computable if it is lambda definable —definable by way of a formula in the calculus. The analysis has little to recommend it initially, but experience with intuitively computable functions led Church to conjecture that every such function is lambda definable—a conjecture now known as Church's thesis. Alan Turing gave a more compelling analysis of computability in terms of abstract computing machines (Turing machines) and it was subsequently shown that lambda definability is equivalent to this notion of Turing computability. Various other analyses have been proposed and all have turned out to be equivalent to Church's definition. This is often regarded by logicians as evidence for the correctness of the conjecture. Church's thesis is now almost universally accepted.

Say, for instance, that a property of an expression is (effectively) decidable if there is an algorithm for deciding whether or not any given expression has the property. This notion can be identified with a certain sort of effective computability by supposing that all expressions have been assigned numbers (in some effectively determinate way) and then saying that a property of an expression is effectively decidable if there is an algorithm that will yield 0 (no ) when applied to the number for the expression if the expression does not have the property and will yield 1 (yes ) if the expression does have the property. If one then identifies the existence of such an algorithm with the lambda definability (or Turing computability) of that function, as Church's (or the Church-Turing) thesis proposes, one has a precise definition of effective decidability. Church's theorem shows that the property of being a valid formula of first-order predicate logic is not decidable in this sense. Thus, unlike the propositional calculus for which truth tables yield an effective procedure for deciding tautologousness, the validity of a first-order formula can not be decided, yea or nay, by any uniform algorithmic procedure.

Church's most important philosophical contributions involve the realism-nominalism controversy in the philosophy of mathematics and logic and problems and theories about meaning. He was a realist or Platonist about abstract entities and provided powerful arguments against various attempts to explain away such entities.

Rudolf Carnap and others associated with logical positivism displayed a general animosity toward such abstracta as numbers, functions, properties, and propositions. Carnap attempted to analyze sentences ostensibly ascribing belief in a proposition to someone in terms of sentences and a relation of "intensional isomorphism" between sentences. Roughly, the relation holds when the sentences in question are made up of necessarily equivalent parts, arranged in the same order. Church objected that a sentence ascribing a belief to someone does not mention a sentence of a particular language. He goes on to give a detailed and compelling refutation of Carnap's specific proposal. The method used, what is now called the "translation argument," appears to be of general applicability and makes it seem implausible that any replacement of propositions by more concrete things such as sentences will be successful. Church also raised powerful objections to nominalist maneuvers by A. J. Ayer and Israel Scheffler. Problems about the notion of synonymy were raised by Nelson Goodman and Benson Mates. Church answered these decisively.

Church's work on the logic of sense and denotation, a formal intensional logic incorporating some of Gottlob Frege's ideas about meaning, was one of his most important projects for philosophy, but it remains unfinished. The basic new idea is the "delta-relation"—the relation that holds between the sense of an expression and the denotation of that expression in some possible (N.B.) language. This is taken to be a logical relation and it is said that the sense is a concept of the denotation. It is postulated that a concept (the sense of some expression in some possible language) is a concept of at most one thing. And if F is a concept of a function f and X is a concept of an object x, then F[X] is a concept of f(x). Church assumes that one can construe concepts of functions as certain functions on concepts, so that F[X], plausibly taken to be a certain complex entity, is just construed as application of the function F to an argument X.

Various difficulties were encountered in working out this last idea, as well as in developing an axiomatic treatment of a criterion of identity for concepts that would render them suitable for the analysis and logic of the propositional attitudes—belief, knowledge, and the like. Modifying Carnap's notion of intensional isomorphism, Church proposed that two sentences (or other complex expressions) express the same proposition (or concept) if they are synonymously isomorphic —roughly, that they consist of synonymous expressions arranged in the same order. The development of axioms for the logic of sense and denotation that this idea suggests Church calls "Alternative (0)." Church was unable to complete an adequate formalization of this important conception.

Bibliography

primary works

"A Formulation of the Logic of Sense and Denotation." In Structure, Method, and Meaning: Essays in Honor of Henry M. Sheffer, edited by Paul Henle. New York: Liberal Arts Press, 1951.

"Logic and Analysis." Atti del XII Congresso Internazionale de Filosofia Venezia, 12–18 settembre, 1958.

"On Carnap's Analysis of Statements of Assertion and Belief." Analysis 10 (1950): 97–99.

"Outline of a Revised Formulation of the Logic of Sense and Denotation," pt. 1. Noûs 7 (1973): 24–33.

"Outline of a Revised Formulation of the Logic of Sense and Denotation," pt 2. Noûs 8 (1974): 135–156.

"Propositions and Sentences." In The Problem of Universals—A Symposium, 1–12. Notre Dame, IN: University of Notre Dame Press 1956.