Eastern Great Lakes Theory Workshop Talk

The place of Turing's solution to the Entscheidungsproblem in its (strictly) Philosophical and Logical Background and Impact

Randall Dipert, University at Buffalo

Saturday, September 29, 2:30-3:30pm

ABSTRACT

The usual story about about the Entscheidungsproblem (Decision Problem) begins with Hilbert (1928) and ends a short time later with results by Turing and Church (1935-1937). It is primarily considered a result whose impact was on the theory of computation and the foundations of mathematics. Far less recognized is a longer history in the discussion of designs for mechanical logic machines beginning with Leibniz and accelerating in the 19th century with elaborate work on logical notations and machines. It even appears that the American philosopher and pioneering logician Charles S. Peirce had, in the 1880's, a clear grasp of the problem of decidability for the full first-order logic. He conjectured that the full FOL with relations was undecidable and that this fact had implications for the inadequacy of Aristotelian logic for descriptions of the world and mathematical objects.

Landing in the heyday of logicism--the view that mathematics or at least arithmetic could be reduced to a definite and finite number of postulates, with fully calculable proofs and counterproofs--the results of Gödel, and then Turing and Church, had the effect of showing that things were not so simple.

But if one-place predicates are inadequate for describing mathematics, and mathematics is a necessary activity for understanding the world, then the world is not describable by Aristotelian logic and must contain at least one fundamental 2- or more place relation. This story is complicated by proofs that there were various distinct decidable fragments of FOL, although Peano arithmetic could not be fitted into any of them. As Peirce and I see it, the Church-Turing Theorem drives a wedge between quantified monadic logics and quantified relational logics. It is a proof of the inadequacy of Aristotelian logic, although in fact Aristotelian logics came to be regarded as inadequate by mere rhetoric in the early 20th century (as Thomas Kuhn argued also happens with the replacement of scientific theories).

I will also argue that Turing, in a shrewd paper in his unpublished Nachlass, made contributions to the theory of mathematical and logical notations.

Speaker Bio

Randall R. Dipert is the C.S. Peirce Professor of Philosophy at the University at Buffalo. His dissertation and many papers are on logic and the history of logic. These include a paper "Logic Notations Peirce, Frege, the Church-Turing Theorem and the Logic of Relations" and "Logic Machines and Diagrams" in the Routledge Encyclopedia of Philosophy. His other current research interests include applied formal ontology, Common Logic, ethical and policy isssues of cyberwarfare.

< Schedule < EaGL-V homepage