Recursive languages and sets
From Wikipedia, the free encyclopedia
- 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 and Undecidable problem. Input on how best to do this is very much welcome on the article's talk page. 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 an algorithm 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 a decision 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 sets. 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.
Contents |
[edit] Formal definition
A subset S of the natural numbers is called decidable if there exists a total computable function f such that 
if 
and 
if 
. In other words, the set S is decidable if and only if the indicator function 1S 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 numberings. 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.
[edit] Examples
There are many examples of decidable sets:
- The empty set is decidable, and the entire set of natural numbers is decidable.
- Every finite or cofinite subset of the natural numbers is decidable.
- The set of prime numbers is decidable.
- The finite binary strings with an even number of 1s is decidable.
- If f is a computable 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 primes 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.
[edit] 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 the Cantor pairing function is decidable.
- The preimage of a decidable set under a total computable function is a decidable set.
- The image of a decidable set under a total computable bijection is decidable.
Sets of strings have additional closure properties. If L and P are two decidable languages, then the following languages are also decidable:
- The Kleene 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 are recursively enumerable sets.
- A set of natural numbers is decidable if and only if it is at level
of the arithmetical 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.
[edit] Decidable languages
A decidable language in mathematics, logic and computer science, is a type of formal 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 (Chomsky 1959), and there is no simple class of formal grammars that capture the decidable languages.
[edit] 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 a recursively enumerable set. Partially decidable problems and any other problems that are not decidable are called undecidable.
[edit] 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 general algorithm 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.
[edit] Decidability of logical theories
In mathematical logic, a theory is a set of formal sentences that is closed under logical 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 of natural numbers, and the set of arithmetical sentences provable from the axioms of Peano 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.
[edit] List of undecidable problems
In computability theory, an undecidable problem is a problem whose language is not a recursive 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 a subset of Turing recognizable languages.
[edit] Problems related to abstract machines
- The halting problem (determining whether a specified machine halts or runs forever).
- The busy 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.
[edit] Other problems
- The Post correspondence problem.
- The word problem for groups.
- The word problem for certain formal languages.
- The problem of determining if a given set of Wang tiles can tile the plane.
- The problem whether a Tag system halts.
- The problem of determining the Kolmogorov complexity of a string.
- Determination of the solvability of a Diophantine equation, known as Hilbert's tenth problem
- Determining whether two finite simplicial complexes are homeomorphic
- Determining whether the fundamental group of a finite simplicial complex is trivial
- Determining if a context-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.
[edit] References
- Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control 2 (2): 137–167. doi:.
- Cutland, N. (1980), Computability., Cambridge University Press, ISBN ISBN 0-521-29465-7
- Rogers, Hartley (1987), The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3
- Michael Sipser (1997). "Decidability", Introduction to the Theory of Computation. PWS Publishing, 151–170. ISBN 0-534-94728-X.
- Soare, R. (1987), Recursively Enumerable Sets and Degrees, Berlin, New York: Springer-Verlag
| Chomsky hierarchy |
Grammars | Languages | Minimal automaton |
|---|---|---|---|
| Type-0 | Unrestricted | Recursively enumerable | Turing machine |
| n/a | (no common name) | Recursive | Decider |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| n/a | Indexed | Indexed | Nested stack |
| n/a | Tree-adjoining etc. | (Mildly context-sensitive) | Embedded pushdown |
| Type-2 | Context-free | Context-free | Nondeterministic pushdown |
| n/a | Deterministic context-free | Deterministic context-free | Deterministic pushdown |
| Type-3 | Regular | Regular | Finite |
| n/a | Star-free | Counter-Free | |
| Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it. |
|||
