Concept
Computability theory
Overview
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.
Basic questions addressed by computability theory include:
What does it mean for a function on the natural numbers to be computable?
How can noncomputable functions be classified into a hierarchy based on their level of noncomputability?
Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages. The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Computability theory is.
This is nothing else than the necessity of abstract logic, which is the presupposition involved in the very fact of interrelated existence as disclosed in each immediate occasion of experience. The key to the pattern means this fact:—that from a select set of those general conditions, exemplified in any one and the same occasion, a pattern involving an infinite variety of other such conditions, also exemplified in…
Alfred North Whitehead, Science and the modern world
States what Computability theory is.
All types of series are capable of formal definition, and their properties can be deduced from the principles of symbolic logic by means of the Algebra of Relatives. The notion of a limit, which is fundamental in the greater part of higher mathematics, used to be defined by means of quantity, as a term to which the terms of some series approximate as nearly as we please. But nowadays the limit is defined quite…
Bertrand Russell, Mysticism and Logic and Other Essays
States what Computability theory is.
Philosophers who discussed Computability theory
Related ideas
- Formal language
- First-order logic
- Alan Turing
- Gödel's completeness theorem
- Effective method
- Differential equation
- Kurt Gödel
- Proof theory
- Function (mathematics)
- Mathematics
- Group (mathematics)
- Mathematical logic
- Natural number
- Partially ordered set
- Peano axioms
- Set theory
- Theory of computation
- Turing machine
- Computably enumerable set
- Cantor's theorem
- Second-order arithmetic
- Emil Leon Post
- Association for Symbolic Logic
- Bijection
Place in the tradition
Part of Formal epistemology.