Communication
Install
Faster access than browser!

Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. [1]

101 relations: Ackermann function, Admissible numbering, Alan Turing, Algorithm, Algorithmically random sequence, Alonzo Church, Alpha recursion theory, Analog computer, Analog signal processing, Analogue electronics, Analytical hierarchy, Arithmetical hierarchy, Association for Symbolic Logic, Bijection, Cantor space, Church–Turing thesis, Computability in Europe, Computability logic, Computable function, Computation in the limit, Computational complexity theory, Computer science, Control theory, Countable set, Differential equation, Diophantine equation, Diophantine set, Dynamical system, Effective descriptive set theory, Emil Leon Post, Entscheidungsproblem, Erlangen program, First-order logic, Formal language, Formal methods, Friedberg numbering, Gödel's completeness theorem, Gödel's incompleteness theorems, Goodstein's theorem, Group (mathematics), Halting problem, Hartley Rogers Jr., Harvey Friedman, Hilbert's tenth problem, Hyperarithmetical theory, Identity element, Information and Computation, Injective function, Μ-recursive function, Jon Barwise, ... Expand index (51 more) »

Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive.

In computability theory, admissible numberings are enumerations (numberings) of the set of partial computable functions that can be converted to and from the standard numbering.

Alan Turing

Alan Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist.

Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

Algorithmically random sequence

Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm.

Alonzo Church

Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science.

Alpha recursion theory

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals \alpha.

Analog computer

An analog computer or analogue computer is a form of computer that uses the continuously changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved.

Analog signal processing

Analog signal processing is a type of signal processing conducted on continuous analog signals by some analog means (as opposed to the discrete Digital Signal Processing where the signal processing is carried out by a digital process).

Analogue electronics

Analogue electronics (also spelled analog electronics) are electronic systems with a continuously variable signal, in contrast to digital electronics where signals usually take only two levels.

Analytical hierarchy

In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy.

Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them.

Association for Symbolic Logic

The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic.

Bijection

In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

Cantor space

In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set.

Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions.

Computability in Europe

Computability in Europe (CiE) is an international organization of mathematicians, logicians, computer scientists, philosophers, theoretical physicists and others interested in new developments in computability and in their underlying significance for the real world.

Computability logic

Computability logic (CoL) is a research program and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth.

Computable function

Computable functions are the basic objects of study in computability theory.

Computation in the limit

In computability theory, a function is called limit computable if it is the limit of a uniformly computable sequence of functions.

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

Control theory

Control theory in control systems engineering deals with the control of continuously operating dynamical systems in engineered processes and machines.

Countable set

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

Differential equation

A differential equation is a mathematical equation that relates some function with its derivatives.

Diophantine equation

In mathematics, a Diophantine equation is a polynomial equation, usually in two or more unknowns, such that only the integer solutions are sought or studied (an integer solution is a solution such that all the unknowns take integer values).

Diophantine set

In mathematics, a Diophantine equation is an equation of the form P(x1,..., xj, y1,..., yk).

Dynamical system

In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in a geometrical space.

Effective descriptive set theory

Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980).

Emil Leon Post

Emil Leon Post (February 11, 1897 – April 21, 1954) was an American mathematician and logician.

Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.

Erlangen program

The Erlangen program is a method of characterizing geometries based on group theory and projective geometry.

First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.

Formal methods

In computer science, specifically software engineering and hardware engineering, formal methods are a particular kind of mathematically based techniques for the specification, development and verification of software and hardware systems.

Friedberg numbering

In computability theory, a Friedberg numbering is a numbering (enumeration) of the set of all uniformly recursively enumerable sets that has no repetitions: each recursively enumerable set appears exactly once in the enumeration (Vereščagin and Shen 2003:30).

Gödel's completeness theorem

Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic.

Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.

Goodstein's theorem

In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0.

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set of elements equipped with an operation that combines any two elements to form a third element and that satisfies four conditions called the group axioms, namely closure, associativity, identity and invertibility.

Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.

Hartley Rogers Jr.

Hartley Rogers Jr. (1926–2015) was a mathematician who worked in recursion theory, and was a professor in the Mathematics Department of the Massachusetts Institute of Technology.

Harvey Friedman

__notoc__ Harvey Friedman (born 23 September 1948)Handbook of Philosophical Logic,, p. 38 is a mathematical logician at Ohio State University in Columbus, Ohio.

Hilbert's tenth problem

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900.

Hyperarithmetical theory

In recursion theory, hyperarithmetic theory is a generalization of Turing computability.

Identity element

In mathematics, an identity element or neutral element is a special type of element of a set with respect to a binary operation on that set, which leaves other elements unchanged when combined with them.

Injective function

In mathematics, an injective function or injection or one-to-one function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain.

Μ-recursive function

In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers that are "computable" in an intuitive sense.

Jon Barwise

Kenneth Jon Barwise (June 29, 1942 – March 5, 2000) was an American mathematician, philosopher and logician who proposed some fundamental revisions to the way that logic is understood and used.

Julia Robinson

Julia Hall Bowman Robinson (December 8, 1919 – July 30, 1985) was an American mathematician renowned for her contributions to the fields of computability theory and computational complexity theory–most notably in decision problems.

Kolmogorov complexity

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output.

Kurt Gödel

Kurt Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.

List of undecidable problems

In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer.

Many-one reduction

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem.

Martin Davis

Martin David Davis (born March 8, 1928) is an American mathematician, known for his work on Hilbert's tenth problem.

Mathematical logic

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.

Mathematics

Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

MathSciNet

MathSciNet is a searchable online bibliographic database created by the American Mathematical Society in 1996.

Maximal set

In recursion theory, the mathematical theory of computability, a maximal set is a coinfinite recursively enumerable subset A of the natural numbers such that for every further recursively enumerable subset B of the natural numbers, either B is cofinite or B is a finite variant of A or B is not a superset of A. This gives an easy definition within the lattice of the recursively enumerable sets.

Model of computation

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how a set of outputs are computed given a set of inputs.

Natural number

In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country").

Neural network

The term neural network was traditionally used to refer to a network or circuit of neurons.

Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.

Partial function

In mathematics, a partial function from X to Y (written as or) is a function, for some subset X ′ of X.

Peano axioms

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano.

Piergiorgio Odifreddi

Piergiorgio Odifreddi (born 13 July 1950 in Cuneo) is an Italian mathematician, logician and aficionado of the history of science, who is also extremely active as a popular science writer and essayist, especially in a perspective of philosophical atheism as a member of the Italian Union of Rationalist Atheists and Agnostics.

Post's theorem

In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

Primitive recursive arithmetic

Primitive recursive arithmetic, or PRA, is a quantifier-free formalization of the natural numbers.

Primitive recursive function

In computability theory, primitive recursive functions are a class of functions that are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions (µ-recursive functions are also called partial recursive).

Proof theory

Proof theory is a major branchAccording to Wang (1981), pp.

Pyotr Novikov

Pyotr Sergeyevich Novikov (Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a Soviet mathematician.

Rózsa Péter

Rózsa Péter, born Politzer, (17 February 1905 &ndash; 16 February 1977) was a Hungarian mathematician and logician.

Recursion (computer science)

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to iteration).

Recursive set

In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set.

Recursively enumerable set

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if.

Reduction (recursion theory)

In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied.

Reverse mathematics

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics.

Rice's theorem

In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.

Robert I. Soare

Robert Irving Soare is an American mathematician.

S.

Second-order arithmetic

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.

Semi-membership

In mathematics and theoretical computer science, the semi-membership problem for a set is the problem of deciding which of two possible elements is logically more likely to belong to that set; alternatively, given two elements of which at least one is in the set, to distinguish the member from the non-member.

Set theory

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects.

Simple set

In recursion theory a subset of the natural numbers is called a simple set if it is co-infinite and recursively enumerable, but every infinite subset of its complement fails to be enumerated recursively.

Stephen Cole Kleene

Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.

Steve Simpson (mathematician)

Stephen George Simpson is an American mathematician whose research concerns the foundations of mathematics, including work in mathematical logic, recursion theory, and Ramsey theory.

Tarski's undefinability theorem

Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics.

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

Transactions of the American Mathematical Society

The Transactions of the American Mathematical Society is a monthly peer-reviewed scientific journal of mathematics published by the American Mathematical Society.

Transcomputational problem

In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information.

Truth-table reduction

In computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.

Turing degree

In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.

Turing jump

In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for.

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

Turing reduction

In computability theory, a Turing reduction from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987).

Uncountable set

In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable.

Universal Turing machine

In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input.

William Boone (mathematician)

William Werner Boone (16 January 1920 in Cincinnati – 14 September 1983 in Urbana, Illinois) was an American mathematician.

Word problem for groups

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element.

Yuri Matiyasevich

Yuri Vladimirovich Matiyasevich, (Ю́рий Влади́мирович Матиясе́вич; born March 2, 1947, in Leningrad) is a Russian mathematician and computer scientist.

References

Hey! We are on Facebook now! »