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, ..., Julia Robinson, Kolmogorov complexity, Kurt Gödel, List of undecidable problems, Many-one reduction, Martin Davis, Mathematical logic, Mathematics, MathSciNet, Maximal set, Model of computation, Natural number, Neural network, Oracle machine, Partial function, Peano axioms, Piergiorgio Odifreddi, Post's theorem, Primitive recursive arithmetic, Primitive recursive function, Proof theory, Pyotr Novikov, Rózsa Péter, Recursion (computer science), Recursive set, Recursively enumerable set, Reduction (recursion theory), Reverse mathematics, Rice's theorem, Robert I. Soare, S. Barry Cooper, Second-order arithmetic, Semi-membership, Set theory, Simple set, Stephen Cole Kleene, Steve Simpson (mathematician), Tarski's undefinability theorem, Theory of computation, Transactions of the American Mathematical Society, Transcomputational problem, Truth-table reduction, Turing degree, Turing jump, Turing machine, Turing reduction, Uncountable set, Universal Turing machine, William Boone (mathematician), Word problem for groups, Yuri Matiyasevich. Expand index (51 more) » « Shrink index
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 Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist.
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm.
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.
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals \alpha.
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 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 (also spelled analog electronics) are electronic systems with a continuously variable signal, in contrast to digital electronics where signals usually take only two levels.
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the 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.
The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic.
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.
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.
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 (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 (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 functions are the basic objects of study in computability theory.
In computability theory, a function is called limit computable if it is the limit of a uniformly computable sequence of functions.
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 deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
Control theory in control systems engineering deals with the control of continuously operating dynamical systems in engineered processes and machines.
In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.
A differential equation is a mathematical equation that relates some function with its derivatives.
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).
In mathematics, a Diophantine equation is an equation of the form P(x1,..., xj, y1,..., yk).
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 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 (February 11, 1897 – April 21, 1954) was an American mathematician and logician.
In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.
The Erlangen program is a method of characterizing geometries based on group theory and projective geometry.
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.
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.
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.
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 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 are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.
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.
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.
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. (1926–2015) was a mathematician who worked in recursion theory, and was a professor in the Mathematics Department of the Massachusetts Institute of Technology.
__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 is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900.
In recursion theory, hyperarithmetic theory is a generalization of Turing computability.
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.
Information and Computation is a computer science journal published by Elsevier (formerly Academic Press).
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.
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.
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 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.
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 Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.
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.
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 David Davis (born March 8, 1928) is an American mathematician, known for his work on Hilbert's tenth problem.
Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
MathSciNet is a searchable online bibliographic database created by the American Mathematical Society in 1996.
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.
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.
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").
The term neural network was traditionally used to refer to a network or circuit of neurons.
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.
In mathematics, a partial function from X to Y (written as or) is a function, for some subset X ′ of X.
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 (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.
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Primitive recursive arithmetic, or PRA, is a quantifier-free formalization of the natural numbers.
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 is a major branchAccording to Wang (1981), pp.
Pyotr Sergeyevich Novikov (Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a Soviet mathematician.
Rózsa Péter, born Politzer, (17 February 1905 – 16 February 1977) was a Hungarian mathematician and logician.
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).
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.
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.
In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied.
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics.
In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.
Robert Irving Soare is an American mathematician.
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.
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 is a branch of mathematical logic that studies sets, which informally are collections of objects.
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 (January 5, 1909 – January 25, 1994) was an American 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, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics.
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.
The Transactions of the American Mathematical Society is a monthly peer-reviewed scientific journal of mathematics published by the American Mathematical Society.
In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information.
In computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.
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.
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.
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.
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).
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable.
In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input.
William Werner Boone (16 January 1920 in Cincinnati – 14 September 1983 in Urbana, Illinois) was an American mathematician.
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 Vladimirovich Matiyasevich, (Ю́рий Влади́мирович Матиясе́вич; born March 2, 1947, in Leningrad) is a Russian mathematician and computer scientist.
Computability Theory, Computability theory (computation), Computability theory (computer science), Continuous computability theory, Ecursion theory, Recursion theory, Theory of computability, Turing computability.