|
Basis Theorem (computability)
In computability theory, there are a number of basis theorems. These theorems show that particular kinds of sets always must have some members that are, in terms of Turing degree, not too complicated. One family of basis theorems concern nonempty effectively closed sets (that is, nonempty \Pi^0_1 sets in the arithmetical hierarchy); these theorems are studied as part of classical computability theory. Another family of basis theorems concern nonempty lightface analytic sets (that is, \Sigma^1_1 in the analytical hierarchy); these theorems are studied as part of hyperarithmetical theory. Effectively closed sets Effectively closed sets are a topic of study in classical computability theory. An effectively closed set is the set of all paths through some computable subtree of the binary tree 2^. These sets are closed, in the topological sense, as subsets of the Cantor space 2^\omega, and the complement of an effective closed set is an effective open set in the sense of effective Poli ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computability Theory
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 definable set, 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 (mathematics), 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 computational complexity theory ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stephen Cole Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of mathematical logic known as recursion theory, which subsequently helped to provide the foundations of theoretical computer science. Kleene's work grounds the study of computable functions. A number of mathematical concepts are named after him: Kleene hierarchy, Kleene algebra, the Kleene star (Kleene closure), Kleene's recursion theorem and the Kleene fixed-point theorem. He also invented regular expressions in 1951 to describe McCulloch-Pitts neural networks, and made significant contributions to the foundations of mathematical intuitionism. Biography Kleene was awarded a bachelor's degree from Amherst College in 1930. He was awarded a Ph.D. in mathematics from Princeton University in 1934, where his thesis, entitled ''A Theory of Po ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exponential Function Arithmetic
In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic, is the system of arithmetic with the usual elementary properties of 0, 1, +, ×, x^y, together with induction for formulas with bounded quantifiers. EFA is a very weak logical system, whose proof theoretic ordinal is \omega^3, but still seems able to prove much of ordinary mathematics that can be stated in the language of first-order arithmetic. Definition EFA is a system in first order logic (with equality). Its language contains: *two constants 0, 1, *three binary operations +, \times, \textrm, with \textrm(x,y) usually written as x^y, *a binary relation symbol < (This is not really necessary as it can be written in terms of the other operations and is sometimes omitted, but is convenient for defining bounded quantifiers). Bounded quantifiers are those of the form [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Peano Arithmetic
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. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete. The axiomatization of arithmetic provided by Peano axioms is commonly called Peano arithmetic. The importance of formalizing arithmetic was not well appreciated until the work of Hermann Grassmann, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about the successor operation and induction. In 1881, Charles Sanders Peirce provided an axiomatization of natural-number arithmetic. In 1888, Richard Dedekind proposed another axiomatization of natural-number arithmetic, and in 1889, Peano published a simplified version of them a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Halting Problem
In computability theory (computer science), 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, or continue to run forever. The halting problem is ''Undecidable problem, undecidable'', meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically Definable set, definable but not Computable function, computable. A key part of the formal statement of the problem is a mathematical definition of a computer and program, usually via a Turing machine. The proof then shows, for any program that might determine whether programs halt, that a "pathological" program exists for which makes an incorrect determination. Specifically, is the program that, when called with some input, passes its own s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 . The operator is called a ''jump operator'' because it increases the Turing degree of the problem . That is, the problem is not Turing-reducible to . Post's theorem establishes a relationship between the Turing jump operator and the arithmetical hierarchy of sets of natural numbers.. Informally, given a problem, the Turing jump returns the set of Turing machines that halt when given access to an oracle that solves that problem. Definition The Turing jump of can be thought of as an oracle to the halting problem for oracle machines with an oracle for . Formally, given a set and a Gödel numbering of the -computable functions, the Turing jump of is defined as X'= \. The th Turing jump is defined inductive ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Recursively Enumerable 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. Overview The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems. The Turing degree of a set is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set. Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered, so that if the Turing degree of a set ''X'' is less than the Turing degree of a set ''Y'', then any (possibly noncomputable) procedure that correctly decides whether ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Low Basis Theorem
The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree 2^, it is possible to find an infinite path through the tree with particular computability properties. The low basis theorem, in particular, shows that there must be a path which is low; that is, the Turing jump of the path is Turing equivalent to the halting problem \emptyset'. Statement and proof The low basis theorem states that every nonempty \Pi^0_1 class in 2^\omega (see arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...) contains a set of low degree (Soare 1987:109). This is equivalent, by definition, to the statement that each infinite computable subtree of the binary tree 2^ has an infinite path o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Effective Polish Space
In mathematical logic, an effective Polish space is a complete separable metric space that has a computable presentation. Such spaces are studied in effective descriptive set theory and in constructive analysis. In particular, standard examples of Polish spaces such as the real line, the Cantor set and the Baire space In mathematics, a topological space X is said to be a Baire space if countable unions of closed sets with empty interior also have empty interior. According to the Baire category theorem, compact Hausdorff spaces and complete metric spaces are ... are all effective Polish spaces. Definition An effective Polish space is a complete separable metric space ''X'' with metric ''d'' such that there is a countable dense set ''C'' = (''c''0, ''c''1,...) that makes the following two relations on \mathbb^4 computable (Moschovakis 2009:96-7): :P(i,j,k,m) \equiv \left\ :Q(i,j,k,m) \equiv \left\ References * Yiannis N. Moschovakis, 2009, ''Descriptive Set Theory'', ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. Overview The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems. The Turing degree of a set is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set. Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered, so that if the Turing degree of a set ''X'' is less than the Turing degree of a set ''Y'', then any (possibly noncomputable) procedure that correctly decides whether ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. In set theory, the topological space 2ω is called "the" Cantor space. Examples The Cantor set itself is a Cantor space. But the canonical example of a Cantor space is the countably infinite topological product of the discrete 2-point space . This is usually written as 2^\mathbb or 2ω (where 2 denotes the 2-element set with the discrete topology). A point in 2ω is an infinite binary sequence, that is a sequence that assumes only the values 0 or 1. Given such a sequence ''a''0, ''a''1, ''a''2,..., one can map it to the real number :\sum_^\infty \frac. This mapping gives a homeomorphism from 2ω onto the Cantor set, demonstrating that 2ω is indeed a Cantor space. Cantor spaces occur abundantly in real analysis. For example, they exist as subspaces in every perfect, complete metri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
