Recursive languages and sets

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 and Undecidable 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 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.

Formal definition

A subset "S" of the natural numbers is called decidable if there exists a total computable function f such that f(x) = 0, if x in S and f(x) ot = 0 if x otin S. In other words, the set "S" is decidable if and only if the indicator function 1_{S} 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.

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.

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 A setminus B 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 Delta^0_1 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.

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 Harv|Chomsky|1959, and there is no simple class of formal grammars 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 a recursively 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 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.

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.

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.

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.

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.

References

*
* citation | author=Cutland, N. |title=Computability.|publisher=Cambridge University Press|year=1980|isbn=ISBN 0-521-29465-7
*
*
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Indo-Aryan languages — or Indic languages Major subgroup of the Indo Iranian branch of the Indo European language family. Indo Aryan languages are spoken by more than 800 million people, principally in India, Nepal, Pakistan, Bangladesh, and Sri Lanka. The Old Indo… …   Universalium

  • Cone (formal languages) — In formal language theory, a cone is a set of formal languages that has some desirable closure properties enjoyed by some well known sets of languages, in particular by the families of regular languages, context free languages and the recursive… …   Wikipedia

  • Construction and Analysis of Distributed Processes — Developer(s) the INRIA VASY team Initial release 1986, 24–25 years ago Stable release …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • List (computing) — In computer science, a list is an ordered collection of entities/items. In the context of object oriented programming languages, a list is defined as an instance of an abstract data type (ADT), formalizing the concept of an ordered collection of… …   Wikipedia

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

  • metalogic — /met euh loj ik/, n. the logical analysis of the fundamental concepts of logic. [1835 45; META + LOGIC] * * * Study of the syntax and the semantics of formal languages and formal systems. It is related to, but does not include, the formal… …   Universalium

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”