- Recursive languages and sets
:"This article is a temporary experiment to see whether it is feasible and desirable to merge the articles
Recursive set ,Recursive language ,Decidable language ,Decidable problem andUndecidable problem . Input on how best to do this is very much welcome on . This is a work in progress so the current version may seem awkward."In
computability theory , a set is decidable, computable, or recursive if there is analgorithm that terminates after a finite amount of time and correctly decides whether or not a given object belongs to the set. Decidability of a set is of particular interest when the set is viewed as adecision problem ; a decidable set is also a decidable problem, computable problem, and recursive problem. The remainder of this article uses the term "decidable", although "recursive" and "computable" are equivalent in this context.A language is a set of finite strings over a particular alphabet. A language is decidable (also computable, recursive) if it is a decidable set.
A set, language, or decision problem that is not decidable is undecidable, non-recursive, non-computable, or uncomputable. There are many known undecidable sets; one of the earliest, and most famous, examples is the
halting problem .Decidable sets and languages are a strict subclass of the class of
recursively enumerable set s. For those sets, it is only required that there is an algorithm that correctly decides when an input "is" in the set; the algorithm may fail to terminate for inputs not belonging to the set.Formal definition
A subset "S" of the
natural numbers is called decidable if there exists a totalcomputable function such that if and if . In other words, the set "S" is decidableif and only if theindicator function is computable.A parallel definition applies to sets of strings over some finite alphabet; these sets are often called languages. A language is decidable if there is a computable function taking strings over the alphabet as input, which returns 0 when presented with a string not in the language, and returns 1 when presented with a string in the language.
The definition can be extended to arbitrary countable sets via
Gödel numbering s. If each element of a set "U" has a unique associated natural number, a subset "C" of "U" is called computable if the set of natural numbers corresponding to the elements of "C" is decidable under the definition above. A similar definition can be made in which elements of "U" are identified with finite strings rather than natural numbers.The definition can also be extended to sets of ordered pairs, ordered triples, and more generally finite sequences of objects. One way to do this is to use computable functions taking more than one argument – for example, a set "A" of ordered pairs of elements of a set "X" is decidable if there is a computable function "g" taking two arguments, such that for all "x" and "y" in "X", "g"("x","y")= 0 if the pair ("x","y") is not in "A", and "g"("x","y")=1 if the pair is in "A". Another way of defining decidability for sets of sequences is to use a pairing function to identify each sequence with a single object (natural number or string). Then the definitions of decidability above can be directly applied. This second method is particularly useful when the set in question contains sequences of varying lengths.
Examples
There are many examples of decidable sets:
* Theempty set is decidable, and the entire set of natural numbers is decidable.
* Every finite orcofinite subset of the natural numbers is decidable.
* The set ofprime number s is decidable.
* The finite binary strings with an even number of 1s is decidable.
* If "f" is acomputable function then the set of pairs ("x","y") such that "f"("x") = "y" is decidable.It is possible for a set to be decidable even if the precise algorithm that decides it is not known. For example, consider the set "A" containing all natural numbers "n" such that there is a pair of
twin prime s larger than "n". It is not presently known whether there are infinitely many twin primes, or whether (otherwise) there is a largest pair of twin primes. But in either case, the set "A" is decidable. If there are infinitely many twin primes, "A" contains every natural number, and is thus decidable. Otherwise, there is a largest pair of twin primes, which means "A" is finite, and thus decidable. This means that, regardless of whether there are infinitely many twin primes, the set "A" is decidable, despite the fact that the correct algorithm has not been identified.Properties
The class of decidable sets has numerous closure properties.
*If "A" is a decidable set then the complement of "A" is also a decidable set.
*If "A" and "B" are decidable sets then "A" ∩ "B", "A" ∪ "B", and are decidable.
* If "A" and "B" are decidable sets then "A" × "B" is decidable; this is the set of pairs ("x","y") such that "x" is in "A" and "y" is in "B". Moreover, the image of "A" × "B" under theCantor pairing function is decidable.
*Thepreimage of a decidable set under a totalcomputable function is a decidable set.
* The image of a decidable set under a total computablebijection is decidable.Sets of strings have additional closure properties. If "L" and "P" are two decidable languages, then the following languages are also decidable:
* TheKleene star "L"∗. A string is in this set if and only if it can be obtained by concatenating zero or more elements of "L", with repetition allowed.
* The concatenation "L" "P". A string is in this set if and only if it can be written as an element of "L" followed by an element of "P".Several characterizations of decidable sets are known.
* A set "A" is decidable if and only if both "A" and the complement of "A" arerecursively enumerable set s.
* A set of natural numbers is decidable if and only if it is at level of thearithmetical hierarchy .
* A set of natural numbers is decidable if and only if it is either the range of a nondecreasing total computable function or is the empty set. Conversely, the image of a decidable set under a nondecreasing total computable function is decidable.Decidable languages
A decidable language in
mathematics ,logic andcomputer science , is a type offormal language which is also called recursive or Turing-decidable. The class of all decidable languages is often called R, although this name is also used for the class RP. All decidable languages are recursively enumerable, and all regular, context-free and context-sensitive languages are decidable.This type of language was not defined in the
Chomsky hierarchy of Harv|Chomsky|1959, and there is no simple class offormal grammar s that capture the decidable languages.Undecidability
A
decision problem is, informally, a problem whose solution is either "yes" or "not". Each such problem is characterized by the set of inputs whose solution is "yes". As a result, decision problems are formally defined as being sets, either of strings or of natural numbers: any such set defines the problem of deciding whether a given object belongs to the set.A decision problem "A" is called decidable or effectively solvable if "A" is a
recursive set , that is, there exists an algorithm for establishing the presence of the element in the set. A problem is called partially decidable, semidecidable, solvable, or provable if "A" is arecursively enumerable set . Partially decidable problems and any other problems that are not decidable are called undecidable.The halting problem
In computability theory, the halting problem is a
decision problem which can be stated as follows::"Given a description of a program and a finite input, decide whether the program eventually halts when started with that input, or whether it runs forever.."
Alan Turing proved in 1936 that a generalalgorithm to solve the halting problem for "all" possible program-input pairs cannot exist; the set of pairs ("e","n") such that the program with description "e" halts on input "n" is undecidable.Decidability of logical theories
In
mathematical logic , a theory is a set of formal sentences that is closed underlogical consequence (essentially, any sentence that can be proved from sentences in the theory is itself in the theory). Important examples are the set of all arithmetical sentences that are satisfied by the set ofnatural numbers , and the set of arithmetical sentences provable from the axioms ofPeano arithmetic .Many formal theories have been studied in the context of decidability. For example, the theory of the real numbers (in the signature of fields) is decidable, while the first-order theory of the natural numbers is not.
Gödel's incompleteness theorem implies that no first-order theory capable of interpreting a sufficient amount of the theory of the natural numbers can be decidable.List of undecidable problems
In
computability theory , an undecidable problem is a problem whose language is not arecursive set . More informally, such problems cannot be solved in general by computers; see decidability. This is a list of undecidable problems. Note that there are uncountably many undecidable problems, so this list is necessarily incomplete. Though undecidable languages are not recursive languages, they may be asubset of Turing recognizable languages.Problems related to
abstract machine s* The
halting problem (determining whether a specified machine halts or runs forever).
* Thebusy beaver problem (determining the length of the longest halting computation among machines of a specified size).
*Rice's theorem states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.Other problems
* The
Post correspondence problem .
* Theword problem for groups .
* The word problem for certainformal languages .
* The problem of determining if a given set ofWang tile s can tile the plane.
* The problem whether aTag system halts.
* The problem of determining theKolmogorov complexity of a string.
* Determination of the solvability of a Diophantine equation, known asHilbert's tenth problem
* Determining whether two finite simplicial complexes are homeomorphic
* Determining whether thefundamental group of a finite simplicial complex is trivial
* Determining if acontext-free grammar generates all possible strings, or if it is ambiguous.
* Given two context-free grammars, determining whether they generate the same set of strings, or whether one generates a subset of the strings generated by the other, or whether there is any string at all that both generate.References
*
* citation | author=Cutland, N. |title=Computability.|publisher=Cambridge University Press|year=1980|isbn=ISBN 0-521-29465-7
*
*
*
Wikimedia Foundation. 2010.