Faster access than browser!
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) »
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.
New!!: Computability theory and Ackermann function · See more »
Admissible numbering
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.
New!!: Computability theory and Admissible numbering · See more »
Alan Turing
Alan Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist.
New!!: Computability theory and Alan Turing · See more »
Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
New!!: Computability theory and Algorithm · See more »
Algorithmically random sequence
Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm.
New!!: Computability theory and Algorithmically random sequence · See more »
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.
New!!: Computability theory and Alonzo Church · See more »
Alpha recursion theory
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals \alpha.
New!!: Computability theory and Alpha recursion theory · See more »
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.
New!!: Computability theory and Analog computer · See more »
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).
New!!: Computability theory and Analog signal processing · See more »
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.
New!!: Computability theory and Analogue electronics · See more »
Analytical hierarchy
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy.
New!!: Computability theory and Analytical hierarchy · See more »
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.
New!!: Computability theory and Arithmetical hierarchy · See more »
Association for Symbolic Logic
The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic.
New!!: Computability theory and Association for Symbolic Logic · See more »
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.
New!!: Computability theory and Bijection · See more »
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.
New!!: Computability theory and Cantor space · See more »
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.
New!!: Computability theory and Church–Turing thesis · See more »
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.
New!!: Computability theory and Computability in Europe · See more »
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.
New!!: Computability theory and Computability logic · See more »
Computable function
Computable functions are the basic objects of study in computability theory.
New!!: Computability theory and Computable function · See more »
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.
New!!: Computability theory and Computation in the limit · See more »
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.
New!!: Computability theory and Computational complexity theory · See more »
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.
New!!: Computability theory and Computer science · See more »
Control theory
Control theory in control systems engineering deals with the control of continuously operating dynamical systems in engineered processes and machines.
New!!: Computability theory and Control theory · See more »
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.
New!!: Computability theory and Countable set · See more »
Differential equation
A differential equation is a mathematical equation that relates some function with its derivatives.
New!!: Computability theory and Differential equation · See more »
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).
New!!: Computability theory and Diophantine equation · See more »
Diophantine set
In mathematics, a Diophantine equation is an equation of the form P(x1,..., xj, y1,..., yk).
New!!: Computability theory and Diophantine set · See more »
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.
New!!: Computability theory and Dynamical system · See more »
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).
New!!: Computability theory and Effective descriptive set theory · See more »
Emil Leon Post
Emil Leon Post (February 11, 1897 – April 21, 1954) was an American mathematician and logician.
New!!: Computability theory and Emil Leon Post · See more »
Entscheidungsproblem
In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.
New!!: Computability theory and Entscheidungsproblem · See more »
Erlangen program
The Erlangen program is a method of characterizing geometries based on group theory and projective geometry.
New!!: Computability theory and Erlangen program · See more »
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.
New!!: Computability theory and First-order logic · See more »
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.
New!!: Computability theory and Formal language · See more »
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.
New!!: Computability theory and Formal methods · See more »
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).
New!!: Computability theory and Friedberg numbering · See more »
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.
New!!: Computability theory and Gödel's completeness theorem · See more »
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.
New!!: Computability theory and Gödel's incompleteness theorems · See more »
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.
New!!: Computability theory and Goodstein's theorem · See more »
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.
New!!: Computability theory and Group (mathematics) · See more »
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.
New!!: Computability theory and Halting problem · See more »
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.
New!!: Computability theory and Hartley Rogers Jr. · See more »
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.
New!!: Computability theory and Harvey Friedman · See more »
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.
New!!: Computability theory and Hilbert's tenth problem · See more »
Hyperarithmetical theory
In recursion theory, hyperarithmetic theory is a generalization of Turing computability.
New!!: Computability theory and Hyperarithmetical theory · See more »
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.
New!!: Computability theory and Identity element · See more »
Information and Computation
Information and Computation is a computer science journal published by Elsevier (formerly Academic Press).
New!!: Computability theory and Information and Computation · See more »
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.
New!!: Computability theory and Injective function · See more »
Μ-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.
New!!: Computability theory and Μ-recursive function · See more »
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.
New!!: Computability theory and Jon Barwise · See more »
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.
New!!: Computability theory and Julia Robinson · See more »
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.
New!!: Computability theory and Kolmogorov complexity · See more »
Kurt Gödel
Kurt Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.
New!!: Computability theory and Kurt Gödel · See more »
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.
New!!: Computability theory and List of undecidable problems · See more »
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.
New!!: Computability theory and Many-one reduction · See more »
Martin Davis
Martin David Davis (born March 8, 1928) is an American mathematician, known for his work on Hilbert's tenth problem.
New!!: Computability theory and Martin Davis · See more »
Mathematical logic
Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.
New!!: Computability theory and Mathematical logic · See more »
Mathematics
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
New!!: Computability theory and Mathematics · See more »
MathSciNet
MathSciNet is a searchable online bibliographic database created by the American Mathematical Society in 1996.
New!!: Computability theory and MathSciNet · See more »
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.
New!!: Computability theory and Maximal set · See more »
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.
New!!: Computability theory and Model of computation · See more »
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").
New!!: Computability theory and Natural number · See more »
Neural network
The term neural network was traditionally used to refer to a network or circuit of neurons.
New!!: Computability theory and Neural network · See more »
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.
New!!: Computability theory and Oracle machine · See more »
Partial function
In mathematics, a partial function from X to Y (written as or) is a function, for some subset X ′ of X.
New!!: Computability theory and Partial function · See more »
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.
New!!: Computability theory and Peano axioms · See more »
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.
New!!: Computability theory and Piergiorgio Odifreddi · See more »
Post's theorem
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
New!!: Computability theory and Post's theorem · See more »
Primitive recursive arithmetic
Primitive recursive arithmetic, or PRA, is a quantifier-free formalization of the natural numbers.
New!!: Computability theory and Primitive recursive arithmetic · See more »
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).
New!!: Computability theory and Primitive recursive function · See more »
Proof theory
Proof theory is a major branchAccording to Wang (1981), pp.
New!!: Computability theory and Proof theory · See more »
Pyotr Novikov
Pyotr Sergeyevich Novikov (Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a Soviet mathematician.
New!!: Computability theory and Pyotr Novikov · See more »
Rózsa Péter
Rózsa Péter, born Politzer, (17 February 1905 – 16 February 1977) was a Hungarian mathematician and logician.
New!!: Computability theory and Rózsa Péter · See more »
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).
New!!: Computability theory and Recursion (computer science) · See more »
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.
New!!: Computability theory and Recursive set · See more »
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.
New!!: Computability theory and Recursively enumerable set · See more »
Reduction (recursion theory)
In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied.
New!!: Computability theory and Reduction (recursion theory) · See more »
Reverse mathematics
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics.
New!!: Computability theory and Reverse mathematics · See more »
Rice's theorem
In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.
New!!: Computability theory and Rice's theorem · See more »
Robert I. Soare
Robert Irving Soare is an American mathematician.
New!!: Computability theory and Robert I. Soare · See more »
S. Barry Cooper
S.
New!!: Computability theory and S. Barry Cooper · See more »
Second-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.
New!!: Computability theory and Second-order arithmetic · See more »
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.
New!!: Computability theory and Semi-membership · See more »
Set theory
Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects.
New!!: Computability theory and Set theory · See more »
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.
New!!: Computability theory and Simple set · See more »
Stephen Cole Kleene
Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.
New!!: Computability theory and Stephen Cole Kleene · See more »
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.
New!!: Computability theory and Steve Simpson (mathematician) · See more »
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.
New!!: Computability theory and Tarski's undefinability theorem · See more »
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.
New!!: Computability theory and Theory of computation · See more »
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.
New!!: Computability theory and Transactions of the American Mathematical Society · See more »
Transcomputational problem
In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information.
New!!: Computability theory and Transcomputational problem · See more »
Truth-table reduction
In computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.
New!!: Computability theory and Truth-table reduction · See more »
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.
New!!: Computability theory and Turing degree · See more »
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.
New!!: Computability theory and Turing jump · See more »
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.
New!!: Computability theory and Turing machine · See more »
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).
New!!: Computability theory and Turing reduction · See more »
Uncountable set
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable.
New!!: Computability theory and Uncountable set · See more »
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.
New!!: Computability theory and Universal Turing machine · See more »
William Boone (mathematician)
William Werner Boone (16 January 1920 in Cincinnati – 14 September 1983 in Urbana, Illinois) was an American mathematician.
New!!: Computability theory and William Boone (mathematician) · See more »
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.
New!!: Computability theory and Word problem for groups · See more »
Yuri Matiyasevich
Yuri Vladimirovich Matiyasevich, (Ю́рий Влади́мирович Матиясе́вич; born March 2, 1947, in Leningrad) is a Russian mathematician and computer scientist.
New!!: Computability theory and Yuri Matiyasevich · See more »
Redirects here:
Computability Theory, Computability theory (computation), Computability theory (computer science), Continuous computability theory, Ecursion theory, Recursion theory, Theory of computability, Turing computability.
References
[1] https://en.wikipedia.org/wiki/Computability_theory
