History of logic - Recursive Function, Theory Applications

history of logic

Table of Contents

Introduction
Origins of logic in the West
- Precursors of ancient logic
- Aristotle
  - Categorical forms
  - Syllogisms
- Theophrastus of Eresus
- The Megarians and the Stoics
- Late representatives of ancient Greek logic
Medieval logic
- Transmission of Greek logic to the Latin West
- Arabic logic
- The revival of logic in Europe
  - St. Anselm and Peter Abelard
  - The “properties of terms” and discussions of fallacies
- Developments in the 13th and early 14th centuries
  - The theory of supposition
  - Developments in modal logic
- Late medieval logic
Modern logic
- The 16th century
- The 17th century
- Leibniz
- The 18th and 19th centuries
  - Gottfried Ploucquet
  - Johann Heinrich Lambert
  - Other 18th-century logicians
  - Boole and De Morgan
  - Charles Sanders Peirce
  - Gottlob Frege
  - Ernst Schröder
  - Georg Cantor
  - Other 19th-century logicians
Logic since 1900
- Propositional and predicate logic
- Principia Mathematica and its aftermath
- Set theory
  - Zermelo-Fraenkel set theory (ZF)
  - The continuum problem and the axiom of constructibility
  - The axiom of choice
  - Problems and new directions
- Theory of logic (metalogic)
- Syntax and proof theory
- Logical semantics and model theory
  - Completeness
  - Gödel’s incompleteness theorems
  - Development of model theory
- Interfaces of proof theory and model theory
- Theory of recursive functions and computability
  - Effective computability
  - The Turing machine
  - Applications of recursive-function theory

References & Edit History Related Topics

Images

Rembrandt: Aristotle with a Bust of Homer

Applications of recursive-function theory

inhistory of logic inLogic since 1900

Written by Jaakko J. Hintikka, Paul Vincent Spade•All

Fact-checked by The Editors of Encyclopaedia Britannica

Article History

Related Topics:: logic

See all related content

Questions about effective computability come up naturally in different contexts. Not surprisingly, recursive-function theory has developed in different directions and has been applied to different problem areas. The recursive unsolvability of the decision problem for first-order logic illustrates one kind of application. The best-known problem of this kind concerns the recursive solvability of all Diophantine equations, or polynomial equations with integral coefficients. This problem was in effect formulated by Hilbert in 1900 as the 10th problem in his list of major open mathematical problems, though the concept of effective computability was not available to him. The problem was solved negatively in 1970 by the Russian mathematician Yury Matiyasevich on the basis of earlier work by the American mathematician Julia Robinson.

A natural class of questions concerns relative computability. Could a Turing machine enumerate recursively a given set A if it had access to all the members of another set B? Such access could be implemented, for example, by adding to the Turing machine two infinite tapes, one on which all the members of B are listed and one on which all the nonmembers of B are listed. If such recursive enumeration is possible, A is said to be reducible to B. Mutually reducible sets are said to be Turing-equivalent. The question of whether all recursively enumerable sets are Turing-equivalent is known as Post’s problem. It was solved negatively in 1956 by two mathematicians working independently, Richard Friedberg in the United States and Andrey Muchnik in Russia.

Equivalence classes of Turing reducibility are also known as degrees of unsolvability. The charting of the hierarchy they form was one of the major early developments of recursive-function theory. Other major topics in recursive-function theory include the study of special kinds of recursively enumerable sets, the study of recursive well-orderings, and the study of recursive structures.

Jaakko J. Hintikka