Misplaced Pages

#763236

107-541: 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, or continue to run forever. The halting problem is 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 but not computable . A key part of

214-453: A certain program will halt given a certain input can be converted into an equivalent statement about natural numbers. If an algorithm could find the truth value of every statement about natural numbers, it could certainly find the truth value of this one; but that would determine whether the original program halts. Rice's theorem generalizes the theorem that the halting problem is unsolvable. It states that for any non-trivial property, there

321-472: A close relationship between the Turing jump operation and the arithmetical hierarchy , which is a classification of certain subsets of the natural numbers based on their definability in arithmetic. Much recent research on Turing degrees has focused on the overall structure of the set of Turing degrees and the set of Turing degrees containing computably enumerable sets. A deep theorem of Shore and Slaman states that

428-416: A computable function that lists all of the pairs ( i ,  x ) it contains. However, the complement of this set is not recursively enumerable. There are many equivalent formulations of the halting problem; any set whose Turing degree equals that of the halting problem is such a formulation. Examples of such sets include: Christopher Strachey outlined a proof by contradiction that the halting problem

535-484: A draft of Davis (1958) available to him, and Martin Davis states in the introduction that "the expert will perhaps find some novelty in the arrangement and treatment of topics", so the terminology must be attributed to Davis. Davis stated in a letter that he had been referring to the halting problem since 1952. The usage in Davis's book is as follows: "[...] we wish to determine whether or not [a Turing machine] Z, if placed in

642-436: A function is provided by Goodstein's theorem . The field of mathematical logic dealing with computability and its generalizations has been called "recursion theory" since its early days. Robert I. Soare , a prominent researcher in the field, has proposed that the field should be called "computability theory" instead. He argues that Turing's terminology using the word "computable" is more natural and more widely understood than

749-534: A further example of an automorphic property: that of the creative sets, the sets which are many-one equivalent to the halting problem. Besides the lattice of computably enumerable sets, automorphisms are also studied for the structure of the Turing degrees of all sets as well as for the structure of the Turing degrees of c.e. sets. In both cases, Cooper claims to have constructed nontrivial automorphisms which map some degrees to other degrees; this construction has, however, not been verified and some colleagues believe that

856-530: A given deadline. Sometimes these programmers use some general-purpose (Turing-complete) programming language, but attempt to write in a restricted style—such as MISRA C or SPARK —that makes it easy to prove that the resulting subroutines finish before the given deadline. Other times these programmers apply the rule of least power —they deliberately use a computer language that is not quite fully Turing-complete. Frequently, these are languages that guarantee all subroutines finish, such as Coq . The difficulty in

963-420: A given initial state, will eventually halt. We call this problem the halting problem for Z. [...] Theorem 2.2 There exists a Turing machine whose halting problem is recursively unsolvable . A related problem is the printing problem for a simple Turing machine Z with respect to a symbol S i ". A possible precursor to Davis's formulation is Kleene's 1952 statement, which differs only in wording: there

1070-443: A hierarchy of computably enumerable sets that are (1,  n  + 1)-recursive but not (1,  n )-recursive. After a long phase of research by Russian scientists, this subject became repopularized in the west by Beigel's thesis on bounded queries, which linked frequency computation to the above-mentioned bounded reducibilities and other related notions. One of the major results was Kummer's Cardinality Theory which states that

1177-417: A method called the priority method ; a proof using this method is called a priority argument . This method is primarily used to construct computably enumerable sets with particular properties. To use this method, the desired properties of the set to be constructed are broken up into an infinite list of goals, known as requirements , so that satisfying all the requirements will cause the set constructed to have

SECTION 10

#1733092917764

1284-405: A paper on a proof for the existence of Friedberg numberings without using the priority method. When Post defined the notion of a simple set as a c.e. set with an infinite complement not containing any infinite c.e. set, he started to study the structure of the computably enumerable sets under inclusion. This lattice became a well-studied structure. Computable sets can be defined in this structure by

1391-456: A perfectly periodic repetitive pattern . The duration of this repeating pattern cannot exceed the number of internal states of the machine... However, a computer with a million small parts, each with two states, would have at least 2 possible states: This is a 1 followed by about three hundred thousand zeroes ... Even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to

1498-489: A previously agreed on acceptable numbering of all computable functions; M learns S if M learns every f in S . Basic results are that all computably enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of computably enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards. Computability theory includes

1605-471: A property. Another important question is the existence of automorphisms in computability-theoretic structures. One of these structures is that one of computably enumerable sets under inclusion modulo finite difference; in this structure, A is below B if and only if the set difference B  −  A is finite. Maximal sets (as defined in the previous paragraph) have the property that they cannot be automorphic to non-maximal sets, that is, if there

1712-487: A randomly produced program halts. These numbers have the same Turing degree as the halting problem. It is a normal and transcendental number which can be defined but cannot be completely computed . This means one can prove that there is no algorithm which produces the digits of Ω, although its first few digits can be calculated in simple cases. Computability theory (computer science) Basic questions addressed by computability theory include: Although there

1819-409: A series of annual conferences. Linear bounded automaton In computer science , a linear bounded automaton (plural linear bounded automata , abbreviated LBA ) is a restricted form of Turing machine . A linear bounded automaton is a Turing machine that satisfies the following three conditions: In other words: instead of having potentially infinite tape on which to compute, computation

1926-434: A set A is computable if and only if there is an n such that some algorithm enumerates for each tuple of n different numbers up to n many possible choices of the cardinality of this set of n numbers intersected with A ; these choices must contain the true cardinality but leave out at least one false one. This is the computability-theoretic branch of learning theory. It is based on E. Mark Gold 's model of learning in

2033-418: A set B , then A is Turing reducible to B , but the converse does not always hold. Although the natural examples of noncomputable sets are all many-one equivalent, it is possible to construct computably enumerable sets A and B such that A is Turing reducible to B but not many-one reducible to B . It can be shown that every computably enumerable set is many-one reducible to the halting problem, and thus

2140-445: A set is c.e. if and only if it is the range of some computable function. The c.e. sets, although not decidable in general, have been studied in detail in computability theory. Beginning with the theory of computable sets and functions described above, the field of computability theory has grown to include the study of many closely related topics. These are not independent areas of research: each of these areas draws ideas and results from

2247-399: A set of natural numbers A is Turing reducible to a set B if there is an oracle machine that correctly tells whether numbers are in A when run with B as the oracle set (in this case, the set A is also said to be ( relatively ) computable from B and recursive in B ). If a set A is Turing reducible to a set B and B is Turing reducible to A then the sets are said to have

SECTION 20

#1733092917764

2354-464: A single hypothesis, the Church–Turing thesis , which states that any function that is computable by an algorithm is a computable function . Although initially skeptical, by 1946 Gödel argued in favor of this thesis: " Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance

2461-432: A straightforward way to compute g : Because g is partial computable, there must be a program e that computes g , by the assumption that the model of computation is Turing-complete. This program is one of all the programs on which the halting function h is defined. The next step of the proof shows that h ( e , e ) will not have the same value as f ( e , e ). It follows from the definition of g that exactly one of

2568-528: A strong reducibility will compute a total function regardless of which oracle it is presented with. Weak reducibilities are those where a reduction process may not terminate for all oracles; Turing reducibility is one example. The strong reducibilities include: Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article Reduction (computability theory) . The major research on strong reducibilities has been to compare their theories, both for

2675-455: A subset of the natural numbers) is random or not by invoking a notion of randomness for finite objects. Kolmogorov complexity became not only a subject of independent study but is also applied to other subjects as a tool for obtaining proofs. There are still many open problems in this area. This branch of computability theory analyzed the following question: For fixed m and n with 0 <  m  <  n , for which functions A

2782-413: A very complicated and non-trivial structure. There are uncountably many sets that are not computably enumerable, and the investigation of the Turing degrees of all sets is as central in computability theory as the investigation of the computably enumerable Turing degrees. Many degrees with special properties were constructed: hyperimmune-free degrees where every function computable relative to that degree

2889-412: Is a contradiction. If halts(g) returns false, then g will halt, because it will not call loop_forever ; this is also a contradiction. Overall, g does the opposite of what halts says g should do, so halts(g) can not return a truth value that is consistent with whether g halts. Therefore, the initial assumption that halts is a total computable function must be false. The concept above shows

2996-409: Is a one-one numbering of all partial-computable functions; it is necessarily not an admissible numbering. Later research dealt also with numberings of other classes like classes of computably enumerable sets. Goncharov discovered for example a class of computably enumerable sets for which the numberings fall into exactly two classes with respect to computable isomorphisms. Post's problem was solved with

3103-407: Is able to ask questions of an oracle , which is a particular set of natural numbers. The oracle machine may only ask questions of the form "Is n in the oracle set?". Each question will be immediately answered correctly, even if the oracle set is not computable. Thus an oracle machine with a noncomputable oracle will be able to compute sets that a Turing machine without an oracle cannot. Informally,

3210-426: Is an automorphism of the computably enumerable sets under the structure just mentioned, then every maximal set is mapped to another maximal set. In 1974, Soare showed that also the converse holds, that is, every two maximal sets are automorphic. So the maximal sets form an orbit, that is, every automorphism preserves maximality and any two maximal sets are transformed into each other by some automorphism. Harrington gave

3317-419: Is an effective procedure to decide whether a Diophantine equation over the integers has a solution in the integers. The main form of computability studied in the field was introduced by Turing in 1936. A set of natural numbers is said to be a computable set (also called a decidable , recursive , or Turing computable set) if there is a Turing machine that, given a number n , halts with output 1 if n

Halting problem - Misplaced Pages Continue

3424-541: Is by characterizing which computable functions the system can prove to be total . For example, in primitive recursive arithmetic any computable function that is provably total is actually primitive recursive , while Peano arithmetic proves that functions like the Ackermann function , which are not primitive recursive, are total. Not every total computable function is provably total in Peano arithmetic, however; an example of such

3531-423: Is closed under Turing reducibility. A numbering is an enumeration of functions; it has two parameters, e and x and outputs the value of the e -th function in the numbering on the input x . Numberings can be partial-computable although some of its members are total computable functions. Admissible numberings are those into which all others can be translated. A Friedberg numbering (named after its discoverer)

3638-478: Is computable if it is ( m ,  n )-recursive for some m ,  n with 2 m  >  n . On the other hand, Jockusch's semirecursive sets (which were already known informally before Jockusch introduced them 1968) are examples of a set which is ( m ,  n )-recursive if and only if 2 m  <  n  + 1. There are uncountably many of these sets and also some computably enumerable but noncomputable sets of this type. Later, Degtev established

3745-475: 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 subrecursive hierarchies , formal methods , and formal languages . The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics . Computability theory originated in

3852-463: Is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the computable sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; in 1991, Harrington and Soare found eventually such

3959-453: Is equal to the class of languages accepted by deterministic LBA. This problem can be phrased succinctly in the language of computational complexity theory as: The second LBA problem is whether the class of languages accepted by LBA is closed under complement. As observed already by Kuroda, a negative answer to the second LBA problem would imply a negative answer to the first problem. But the second LBA problem has an affirmative answer, which

4066-431: Is general enough to be equivalent to a Turing machine. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long and use an arbitrary amount of storage space before halting. The question

4173-418: Is in the set and halts with output 0 if n is not in the set. A function f from natural numbers to natural numbers is a (Turing) computable , or recursive function if there is a Turing machine that, on input n , halts and returns output f ( n ). The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines; for example

4280-404: Is it possible to compute for any different n inputs x 1 ,  x 2 , ...,  x n a tuple of n numbers y 1 , y 2 , ..., y n such that at least m of the equations A ( x k ) = y k are true. Such sets are known as ( m ,  n )-recursive sets. The first major result in this branch of computability theory is Trakhtenbrot's result that a set

4387-511: Is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen." With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided . In 1936, Church and Turing were inspired by techniques used by Gödel to prove his incompleteness theorems - in 1931, Gödel independently demonstrated that

Halting problem - Misplaced Pages Continue

4494-527: Is majorized by a (unrelativized) computable function; high degrees relative to which one can compute a function f which dominates every computable function g in the sense that there is a constant c depending on g such that g(x) < f(x) for all x > c ; random degrees containing algorithmically random sets ; 1-generic degrees of 1-generic sets; and the degrees below the halting problem of limit-computable sets. The study of arbitrary (not necessarily computably enumerable) Turing degrees involves

4601-441: Is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops. The halting problem is Turing equivalent to both Davis's printing problem ("does a Turing machine starting from a given state ever print a given symbol?") and to the printing problem considered in Turing's 1936 paper ("does a Turing machine starting from a blank tape ever print a given symbol?"). However, Turing equivalence

4708-400: Is no general decision procedure that, for all programs, decides whether the partial function implemented by the input program has that property. (A partial function is a function which may not always produce a result, and so is used to model programs, which can either produce results or fail to halt.) For example, the property "halt for the input 0" is undecidable. Here, "non-trivial" means that

4815-430: Is not solvable. The proof proceeds as follows: Suppose that there exists a total computable function halts(f) that returns true if the subroutine f halts (when run with no inputs) and returns false otherwise. Now consider the following subroutine: halts(g) must either return true or false, because halts was assumed to be total . If halts(g) returns true, then g will call loop_forever and never halt, which

4922-409: Is placed at column i , row j . Because f is assumed to be a total computable function, any element of the array can be calculated using f . The construction of the function g can be visualized using the main diagonal of this array. If the array has a 0 at position ( i , i ), then g ( i ) is 0. Otherwise, g ( i ) is undefined. The contradiction comes from the fact that there is some column e of

5029-463: Is rather loose and does not mean that the two problems are the same. There are machines which print but do not halt, and halt but not print. The printing and halting problems address different issues and exhibit important conceptual and technical differences. Thus, Davis was simply being modest when he said: It might also be mentioned that the unsolvability of essentially these problems was first obtained by Turing. In his original proof Turing formalized

5136-409: Is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers. An alternative, less restrictive definition is as follows: This limitation makes an LBA a somewhat more accurate model of a real-world computer than a Turing machine, whose definition assumes unlimited tape. The strong and the weaker definition lead to the same computational abilities of

5243-449: Is simply whether the given program will ever halt on a particular input. For example, in pseudocode , the program does not halt; rather, it goes on forever in an infinite loop . On the other hand, the program does halt. While deciding whether these programs halt is simple, more complex programs prove problematic. One approach to the problem might be to run the program for some number of steps and check if it halts. However, as long as

5350-473: Is that a computable bijection merely renames numbers in a set, rather than indicating any structure in the set, much as a rotation of the Euclidean plane does not change any geometric aspect of lines drawn on it. Since any two infinite computable sets are linked by a computable bijection, this proposal identifies all the infinite computable sets (the finite computable sets are viewed as trivial). According to Rogers,

5457-486: Is undefined for a particular input value. The proof proceeds by directly establishing that no total computable function with two arguments can be the required function h . As in the sketch of the concept, given any total computable binary function f , the following partial function g is also computable by some program e : The verification that g is computable relies on the following constructs (or their equivalents): The following pseudocode for e illustrates

SECTION 50

#1733092917764

5564-599: The Entscheidungsproblem is not effectively decidable. This result showed that there is no algorithmic procedure that can correctly decide whether arbitrary mathematical propositions are true or false. Many problems in mathematics have been shown to be undecidable after these initial examples were established. In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided. Extending this result, Pyotr Novikov and William Boone showed independently in

5671-548: The Blum–Shub–Smale machine model have formalized computation on the reals. There are close relationships between the Turing degree of a set of natural numbers and the difficulty (in terms of the arithmetical hierarchy ) of defining that set using a first-order formula . One such relationship is made precise by Post's theorem . A weaker relationship was demonstrated by Kurt Gödel in the proofs of his completeness theorem and incompleteness theorems . Gödel's proofs show that

5778-527: The Cantor's theorem , there are uncountably many sets of natural numbers. Although the halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a computably enumerable (c.e.) set , which is a set that can be enumerated by a Turing machine (other terms for computably enumerable include recursively enumerable and semidecidable ). Equivalently,

5885-408: The algorithm can operate upon. For example, if the formalism lets algorithms define functions over strings (such as Turing machines) then there should be a mapping of these algorithms to strings, and if the formalism lets algorithms define functions over natural numbers (such as computable functions ) then there should be a mapping of algorithms to natural numbers. The mapping to strings is usually

5992-414: The arithmetical hierarchy by permitting quantification over sets of natural numbers in addition to quantification over individual numbers. These areas are linked to the theories of well-orderings and trees; for example the set of all indices of computable (nonbinary) trees without infinite branches is complete for level Π 1 1 {\displaystyle \Pi _{1}^{1}} of

6099-587: The simple , hypersimple and hyperhypersimple sets. Post showed that these sets are strictly between the computable sets and the halting problem with respect to many-one reducibility. Post also showed that some of them are strictly intermediate under other reducibility notions stronger than Turing reducibility. But Post left open the main problem of the existence of computably enumerable sets of intermediate Turing degree; this problem became known as Post's problem . After ten years, Kleene and Post showed in 1954 that there are intermediate Turing degrees between those of

6206-412: The μ-recursive functions obtained from primitive recursion and the μ operator. The terminology for computable functions and sets is not completely standardized. The definition in terms of μ-recursive functions as well as a different definition of rekursiv functions by Gödel led to the traditional name recursive for sets and functions computable by a Turing machine. The word decidable stems from

6313-427: The 1930s, with the work of Kurt Gödel , Alonzo Church , Rózsa Péter , Alan Turing , Stephen Kleene , and Emil Post . The fundamental results the researchers obtained established Turing computability as the correct formalization of the informal idea of effective calculation. In 1952, these results led Kleene to coin the two names "Church's thesis" and "Turing's thesis". Nowadays these are often considered as

6420-456: The 1950s that the word problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presented group , will decide whether the element represented by the word is the identity element of the group. In 1970, Yuri Matiyasevich proved (using results of Julia Robinson ) Matiyasevich's theorem , which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there

6527-465: The German word Entscheidungsproblem which was used in the original papers of Turing and others. In contemporary use, the term "computable function" has various definitions: according to Nigel J. Cutland , it is a partial recursive function (which can be undefined for some inputs), while according to Robert I. Soare it is a total recursive (equivalently, general recursive) function. This article follows

SECTION 60

#1733092917764

6634-646: The analytical hierarchy. Both Turing reducibility and hyperarithmetical reducibility are important in the field of effective descriptive set theory . The even more general notion of degrees of constructibility is studied in set theory . Computability theory for digital computation is well developed. Computability theory is less well developed for analog computation that occurs in analog computers , analog signal processing , analog electronics , artificial neural networks and continuous-time control theory , modelled by differential equations and continuous dynamical systems . For example, models of computation such as

6741-531: The array corresponding to g itself. Now assume f was the halting function h , if g ( e ) is defined ( g ( e ) = 0 in this case), g ( e ) halts so f ( e,e ) = 1. But g ( e ) = 0 only when f ( e,e ) = 0, contradicting f ( e,e ) = 1. Similarly, if g ( e ) is not defined, then halting function f ( e,e ) = 0, which leads to g ( e ) = 0 under g' s construction. This contradicts the assumption of g ( e ) not being defined. In both cases contradiction arises. Therefore any arbitrary computable function f cannot be

6848-423: The basic result that a set is computable if and only if the set and its complement are both computably enumerable. Infinite c.e. sets have always infinite computable subsets; but on the other hand, simple sets exist but do not always have a coinfinite computable superset. Post introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are c.e. sets such that every c.e. superset

6955-609: The class of all computably enumerable sets as well as for the class of all subsets of the natural numbers. Furthermore, the relations between the reducibilities has been studied. For example, it is known that every Turing degree is either a truth-table degree or is the union of infinitely many truth-table degrees. Reducibilities weaker than Turing reducibility (that is, reducibilities that are implied by Turing reducibility) have also been studied. The most well known are arithmetical reducibility and hyperarithmetical reducibility . These reducibilities are closely connected to definability over

7062-427: The computable sets and the halting problem, but they failed to show that any of these degrees contains a computably enumerable set. Very soon after this, Friedberg and Muchnik independently solved Post's problem by establishing the existence of computably enumerable sets of intermediate degree. This groundbreaking result opened a wide study of the Turing degrees of the computably enumerable sets which turned out to possess

7169-405: The computably enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets. The program of reverse mathematics asks which set-existence axioms are necessary to prove particular theorems of mathematics in subsystems of second-order arithmetic . This study was initiated by Harvey Friedman and

7276-456: The concept of algorithm by introducing Turing machines . However, the result is in no way specific to them; it applies equally to any other model of computation that is equivalent in its computational power to Turing machines, such as Markov algorithms , Lambda calculus , Post systems , register machines , or tag systems . What is important is that the formalization allows a straightforward mapping of algorithms to some data type that

7383-405: The construction contains errors and that the question of whether there is a nontrivial automorphism of the Turing degrees is still one of the main unsolved questions in this area. The field of Kolmogorov complexity and algorithmic randomness was developed during the 1960s and 1970s by Chaitin, Kolmogorov, Levin, Martin-Löf and Solomonoff (the names are given here in alphabetical order; much of

7490-402: The definition and proof of undecidability of the halting problem to Turing's 1936 paper. However, this is not correct. Turing did not use the terms "halt" or "halting" in any of his published works, including his 1936 paper. A search of the academic literature from 1936 to 1958 showed that the first published material using the term “halting problem” was Rogers (1957) . However, Rogers says he had

7597-417: The desired properties. Each requirement is assigned to a natural number representing the priority of the requirement; so 0 is assigned to the most important priority, 1 to the second most important, and so on. The set is then constructed in stages, each stage attempting to satisfy one of more of the requirements by either adding numbers to the set or banning numbers from the set so that the final set will satisfy

7704-414: The following function h (for "halts") is not computable: Here program i refers to the i th program in an enumeration of all the programs of a fixed Turing-complete model of computation. Possible values for a total computable function f arranged in a 2D array. The orange cells are the diagonal. The values of f ( i , i ) and g ( i ) are shown at the bottom; U indicates that the function g

7811-423: The following two cases must hold: In either case, f cannot be the same function as h . Because f was an arbitrary total computable function with two arguments, all such functions must differ from h . This proof is analogous to Cantor's diagonal argument . One may visualize a two-dimensional array with one column and one row for each natural number, as indicated in the table above. The value of f ( i , j )

7918-426: 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 f that might determine whether programs halt, that a "pathological" program g exists for which f makes an incorrect determination. Specifically, g is the program that, when called with some input, passes its own source and its input to f and does

8025-476: The function mapping a degree x to the degree of its Turing jump is definable in the partial order of the Turing degrees. A survey by Ambos-Spies and Fejer gives an overview of this research and its historical progression. An ongoing area of research in computability theory studies reducibility relations other than Turing reducibility. Post introduced several strong reducibilities , so named because they imply truth-table reducibility. A Turing machine implementing

8132-423: The general method of the proof, but the computable function halts does not directly take a subroutine as an argument; instead it takes the source code of a program. Moreover, the definition of g is self-referential . A rigorous proof addresses these issues. The overall goal is to show that there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x ; that is,

8239-405: The halting function h . A typical method of proving a problem P {\displaystyle P} to be undecidable is to reduce the halting problem to P {\displaystyle P} . For example, there cannot be a general algorithm that decides whether a given statement about natural numbers is true or false. The reason for this is that the proposition stating that

8346-502: The halting problem as stated; it does not successfully answer "does not halt" for programs that do not halt. The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory. A machine with finite memory has a finite number of configurations, and thus any deterministic program on it must eventually either halt or repeat a previous configuration: ... any finite-state machine, if left completely to itself, will fall eventually into

8453-422: The halting problem generally. There are programs ( interpreters ) that simulate the execution of whatever source code they are given. Such programs can demonstrate that a program does halt if this is the case: the interpreter itself will eventually halt its simulation, which shows that the original program halted. However, an interpreter will not halt if its input program does not halt, so this approach cannot solve

8560-476: The halting problem is the most complicated computably enumerable set with respect to many-one reducibility and with respect to Turing reducibility. In 1944, Post asked whether every computably enumerable set is either computable or Turing equivalent to the halting problem, that is, whether there is no computably enumerable set with a Turing degree intermediate between those two. As intermediate results, Post defined natural types of computably enumerable sets like

8667-430: The halting problem lies in the requirement that the decision procedure must work for all programs and inputs. A particular program either halts on a given input or does not halt. Consider one algorithm that always answers "halts" and another that always answers "does not halt". For any specific program and input, one of these two algorithms answers correctly, even though nobody may know which one. Yet neither algorithm solves

8774-550: The halting problem. These type of sets can be classified using the arithmetical hierarchy . For example, the index set FIN of the class of all finite sets is on the level Σ 2 , the index set REC of the class of all recursive sets is on the level Σ 3 , the index set COFIN of all cofinite sets is also on the level Σ 3 and the index set COMP of the class of all Turing-complete sets Σ 4 . These hierarchy levels are defined inductively, Σ n +1 contains just all sets which are computably enumerable relative to Σ n ; Σ 1 contains

8881-424: The limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a class S of computable functions, is there a learner (that is, computable functional) which outputs for any input of the form ( f (0),  f (1), ...,  f ( n )) a hypothesis. A learner M learns a function f if almost all hypotheses are the same index e of f with respect to

8988-432: The more general model of (nondeterministic) linear bounded automata, and adapted Landweber's proof to show that the languages accepted by nondeterministic linear bounded automata are precisely the context-sensitive languages. In his seminal paper, Kuroda also stated two research challenges, which subsequently became famously known as the "LBA problems": The first LBA problem is whether the class of languages accepted by LBA

9095-399: The most straightforward, but strings over an alphabet with n characters can also be mapped to numbers by interpreting them as numbers in an n -ary numeral system . The conventional representation of decision problems is the set of objects possessing the property in question. The halting set represents the halting problem. This set is recursively enumerable , which means there is

9202-477: The names recursion theory and computability theory fail to convey the fact that most of the objects studied in computability theory are not computable. In 1967, Rogers has suggested that a key property of computability theory is that its results and structures should be invariant under computable bijections on the natural numbers (this suggestion draws on the ideas of the Erlangen program in geometry). The idea

9309-401: The non-computability inherent in well known mathematical theorems. In 1999, Simpson discussed many aspects of second-order arithmetic and reverse mathematics. The field of proof theory includes the study of second-order arithmetic and Peano arithmetic , as well as formal theories of the natural numbers weaker than Peano arithmetic. One method of classifying the strength of these weak systems

9416-400: The opposite of what f predicts g will do. The behavior of f on g shows undecidability as it means no program f will solve the halting problem in every possible case. The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that

9523-420: The others, and most computability theorists are familiar with the majority of them. Computability theory in mathematical logic has traditionally focused on relative computability , a generalization of Turing computability defined using oracle Turing machines , introduced by Turing in 1939. An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine,

9630-481: The possible sequences of nondeterministic decisions, by enumerating states after each possible decision. In April 1936, Alonzo Church published his proof of the undecidability of a problem in the lambda calculus . Turing's proof was published later, in January 1937. Since then, many other undecidable problems have been described, including the halting problem which emerged in the 1950s. Many papers and textbooks refer

9737-707: The program is running, it is unknown whether it will eventually halt or run forever. Turing proved no algorithm exists that always correctly decides whether, for a given arbitrary program and input, the program halts when run with that input. The essence of Turing's proof is that any such algorithm can be made to produce contradictory output and therefore cannot be correct. Some infinite loops can be quite useful. For instance, event loops are typically coded as infinite loops. However, most subroutines are intended to finish. In particular, in hard real-time computing , programmers attempt to write subroutines that are not only guaranteed to finish, but are also guaranteed to finish before

9844-410: The program itself. For example, "halt on input 0 within 100 steps" is not a property of the partial function that is implemented by the program—it is a property of the program implementing the partial function and is very much decidable. Gregory Chaitin has defined a halting probability , represented by the symbol Ω , a type of real number that informally is said to represent the probability that

9951-613: The requirement. It may happen that satisfying one requirement will cause another to become unsatisfied; the priority order is used to decide what to do in such an event. Priority arguments have been employed to solve many problems in computability theory, and have been classified into a hierarchy based on their complexity. Because complex priority arguments can be technical and difficult to follow, it has traditionally been considered desirable to prove results without priority arguments, or to see if results proved with priority arguments can also be proved without them. For example, Kummer published

10058-420: The research was independent, and the unity of the concept of randomness was not understood at the time). The main idea is to consider a universal Turing machine U and to measure the complexity of a number (or string) x as the length of the shortest input p such that U ( p ) outputs x . This approach revolutionized earlier ways to determine when an infinite sequence (equivalently, characteristic function of

10165-421: The respective automaton classes, by the same argument used to prove the linear speedup theorem . Linear bounded automata are acceptors for the class of context-sensitive languages . The only restriction placed on grammars for such languages is that no production maps a string to a shorter string. Thus no derivation of a string in a context-sensitive language can contain a sentential form longer than

10272-413: The same Turing degree (also called degree of unsolvability ). The Turing degree of a set gives a precise measure of how uncomputable the set is. The natural examples of sets that are not computable, including many different sets that encode variants of the halting problem , have two properties in common: Many-one reductions are "stronger" than Turing reductions: if a set A is many-one reducible to

10379-474: The second of these conventions. In 1996, Soare gave additional comments about the terminology. Not every set of natural numbers is computable. The halting problem , which is the set of (descriptions of) Turing machines that halt on input 0, is a well-known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only countably many Turing machines, and thus only countably many computable sets, but according to

10486-657: The set of logical consequences of an effective first-order theory is a computably enumerable set , and that if the theory is strong enough this set will be uncomputable. Similarly, Tarski's indefinability theorem can be interpreted both in terms of definability and in terms of computability. Computability theory is also linked to second-order arithmetic , a formal theory of natural numbers and sets of natural numbers. The fact that certain sets are computable or relatively computable often implies that these sets can be defined in weak subsystems of second-order arithmetic. The program of reverse mathematics uses these subsystems to measure

10593-444: The set of partial functions that satisfy the property is neither the empty set nor the set of all partial functions. For example, "halts or fails to halt on input 0" is clearly true of all partial functions, so it is a trivial property, and can be decided by an algorithm that simply reports "true." Also, this theorem holds only for properties of the partial function implemented by the program; Rice's Theorem does not apply to properties of

10700-511: The sets of interest in computability theory are the noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers. The main professional organization for computability theory is the Association for Symbolic Logic , which holds several research conferences each year. The interdisciplinary research Association Computability in Europe ( CiE ) also organizes

10807-453: The standard model of arithmetic. Rice showed that for every nontrivial class C (which contains some but not all c.e. sets) the index set E = { e : the e th c.e. set W e is in C } has the property that either the halting problem or its complement is many-one reducible to E , that is, can be mapped using a many-one reduction to E (see Rice's theorem for more detail). But, many of these index sets are even more complicated than

10914-485: The string itself. Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string to be recognized by the automaton. In 1960, John Myhill introduced an automaton model today known as deterministic linear bounded automaton. In 1963, Peter Landweber proved that the languages accepted by deterministic LBAs are context-sensitive. In 1964, S.-Y. Kuroda introduced

11021-427: The study of generalized notions of this field such as arithmetic reducibility , hyperarithmetical reducibility and α-recursion theory , as described by Sacks in 1990. These generalized notions include reducibilities that cannot be executed by Turing machines but are nevertheless natural generalizations of Turing reducibility. These studies include approaches to investigate the analytical hierarchy which differs from

11128-537: The study of the Turing jump. Given a set A , the Turing jump of A is a set of natural numbers encoding a solution to the halting problem for oracle Turing machines running with oracle A . The Turing jump of any set is always of higher Turing degree than the original set, and a theorem of Friedburg shows that any set that computes the Halting problem can be obtained as the Turing jump of another set. Post's theorem establishes

11235-469: The terminology using the word "recursive" introduced by Kleene. Many contemporary researchers have begun to use this alternate terminology. These researchers also use terminology such as partial computable function and computably enumerable ( c.e. ) set instead of partial recursive function and recursively enumerable ( r.e. ) set . Not all researchers have been convinced, however, as explained by Fortnow and Simpson. Some commentators argue that both

11342-453: The time of a journey through such a cycle: Although a machine may be finite, and finite automata "have a number of theoretical limitations": ...the magnitudes involved should lead one to suspect that theorems and arguments based chiefly on the mere finiteness [of] the state diagram may not carry a great deal of significance. It can also be decided automatically whether a nondeterministic machine with finite memory halts on none, some, or all of

11449-411: Was studied in detail by Stephen Simpson and others; in 1999, Simpson gave a detailed discussion of the program. The set-existence axioms in question correspond informally to axioms saying that the powerset of the natural numbers is closed under various reducibility notions. The weakest such axiom studied in reverse mathematics is recursive comprehension , which states that the powerset of the naturals

#763236