|
Selman's Theorem
In computability theory, Selman's theorem is a theorem relating enumeration reducibility with enumerability relative to oracles. It is named after Alan Selman, who proved it as part of his PhD thesis in 1971. Statement Informally, a set ''A'' is enumeration-reducible to a set ''B'' if there is a Turing machine which receives an enumeration of ''B'' (it has a special instruction to get the next element, or none if it has not yet been provided), and produces an enumeration of ''A''. See enumeration reducibility for a precise account. A set ''A'' is computably enumerable with oracle ''B'' (or simply "in ''B''") when there is a Turing machine with oracle ''B'' which enumerates the members of ''A''; this is the relativized version of computable enumerability. Selman's theorem: A set ''A'' is enumeration-reducible to a set ''B'' if and only if ''A'' is computably enumerable with an oracle ''X'' whenever ''B'' is computably enumerable with the same oracle ''X''. Discussion Informal ... [...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] |
Enumeration Reducibility
In computability theory, enumeration reducibility (or e-reducibility for short) is a specific type of reducibility. Roughly speaking, ''A'' is enumeration-reducible to ''B'' if an enumeration of ''B'' can be algorithmically converted to an enumeration of ''A''. In particular, if ''B'' is computably enumerable, then ''A'' also is. Introduction In one of the possible formalizations of the concept, a Turing reduction from ''A'' to ''B'' is a Turing machine augmented with a special instruction "query the oracle". This instruction takes an integer ''x'' and instantly returns whether ''x'' belongs to ''B''. The oracle machine should compute ''A'', possibly using this special capability to decide ''B''. Informally, the existence of a Turing reduction from ''A'' to ''B'' means that if it is possible to decide ''B'', then this can be used to decide ''A''. Enumeration reducibility is a variant whose informal explanation is, instead, that if it is possible to enumerate ''B'', then this can b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Oracle Machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used. Oracles An oracle machine can be conceived as a Turing machine connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or a function problem. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "black box" that is able to produce a solution for any instance of a given computational problem: * A decision problem is represented as a set ''A'' of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alan Selman
Alan Louis Selman (April 2, 1941 – January 22, 2021) was an American mathematician and theoretical computer scientist known for his research on structural complexity theory, the study of computational complexity in terms of the relation between complexity classes rather than individual algorithmic problems. Education and career Selman was a graduate of the City College of New York. He earned a master's degree at the University of California, Berkeley before completing his Ph.D. in 1970 at Pennsylvania State University. His dissertation, ''Arithmetical Reducibilities and Sets of Formulas Valid in Finite Structures'', was supervised by Paul Axt, a student of Stephen Cole Kleene. He became a postdoctoral researcher at Carnegie Mellon University, and an assistant professor of mathematics at Florida State University, before moving to the computer science department of Iowa State University, eventually becoming a full professor there. In the late 1980s he moved to Northeastern Uni ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computably Enumerable Set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the set of input numbers for which the algorithm halts is exactly ''S''. Or, equivalently, *There is an enumeration algorithm, algorithm that enumerates the members of ''S''. That means that its output is a list of all the members of ''S'': ''s''1, ''s''2, ''s''3, ... . If ''S'' is infinite, this algorithm will run forever, but each element of S will be returned after a finite amount of time. Note that these elements do not have to be listed in a particular way, say from smallest to largest. The first condition suggests why the term ''semidecidable'' is sometimes used. More precisely, if a number is in the set, one can ''decide'' this by running the algorithm, but if the number is not in the set, the algorithm can run forever, and no inf ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mučnik Reducibility
In computability theory, a set P of functions \mathbb \rarr \mathbb is said to be Mučnik-reducible to another set Q of functions \mathbb \rarr \mathbb when for every function g in Q, there exists a function f in P which is Turing-reducible to g. Unlike most reducibility relations in computability, Mučnik reducibility is not defined between functions \mathbb \rarr \mathbb but between sets of such functions. These sets are called "mass problems" and can be viewed as problems with more than one solution. Informally, P is Mučnik-reducible to Q when any solution of Q can be used to compute some solution of P. See also * Medvedev reducibility * Turing reducibility In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm ... * Reduction (computability) References ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Medvedev Reducibility
In computability theory, a set ''P'' of functions \mathbb \rarr \mathbb is said to be Medvedev-reducible to another set ''Q'' of functions \mathbb \rarr \mathbb when there exists an oracle Turing machine which computes some function of ''P'' whenever it is given some function from ''Q'' as an oracle. Medvedev reducibility is a uniform variant of Mučnik reducibility, requiring a single oracle machine that can compute some function of ''P'' given any oracle from ''Q'', instead of a family of oracle machines, one per oracle from ''Q'', which compute functions from ''P''. See also * Mučnik reducibility * Turing reducibility In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm ... * Reduction (computability) References Theoretical computer science Reduction ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Oracle Turing Machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used. Oracles An oracle machine can be conceived as a Turing machine connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or a function problem. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "black box" that is able to produce a solution for any instance of a given computational problem: * A decision problem is represented as a set ''A'' of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pairing Function
In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number. Any pairing function can be used in set theory to prove that integers and rational numbers have the same cardinality as natural numbers. Definition A pairing function is a bijection :\pi:\mathbb \times \mathbb \to \mathbb. Generalization More generally, a pairing function on a set A is a function that maps each pair of elements from A into an element of A, such that any two pairs of elements of A are associated with different elements of A, or a bijection from A^2 to A. Instead of abstracting from the domain, the arity of the pairing function can also be generalized: there exists an n-ary generalized Cantor pairing function on \mathbb. Cantor pairing function The Cantor pairing function is a primitive recursive pairing function :\pi:\mathbb \times \mathbb \to \mathbb defined by :\pi(k_1,k_2) := \frac(k_1 + k_2)(k_1 + k_2 + 1)+k_2 where k_1, k_2\in\. It ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semi-algorithm
In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem. Similarly, co-RE is the set of all languages that are complements of a language in RE. In a sense, co-RE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever. Equivalent definition Equivalently, RE is the class ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Priority Method
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] |
Enumeration Reducibility
In computability theory, enumeration reducibility (or e-reducibility for short) is a specific type of reducibility. Roughly speaking, ''A'' is enumeration-reducible to ''B'' if an enumeration of ''B'' can be algorithmically converted to an enumeration of ''A''. In particular, if ''B'' is computably enumerable, then ''A'' also is. Introduction In one of the possible formalizations of the concept, a Turing reduction from ''A'' to ''B'' is a Turing machine augmented with a special instruction "query the oracle". This instruction takes an integer ''x'' and instantly returns whether ''x'' belongs to ''B''. The oracle machine should compute ''A'', possibly using this special capability to decide ''B''. Informally, the existence of a Turing reduction from ''A'' to ''B'' means that if it is possible to decide ''B'', then this can be used to decide ''A''. Enumeration reducibility is a variant whose informal explanation is, instead, that if it is possible to enumerate ''B'', then this can b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
