Encyclopedia > Recursive language

  Article Content

Decidable language

Redirected from Recursive language

A decidable or recursive language is a formal language for which there exists an algorithm to solve the following decision problem: Given string w, does w belong to the language? The algorithm is not allowed to run into an infinite loop and has to produce a YES/NO answer for any input string after a finite amount of time. To formalize the rather vague term "algorithm", one usually employs Turing machines, but several other equivalent approaches are possible.

All regular, context-free and context-sensitive languages are recursive, but there exist recursively enumerable languages which are not recursive; one example is given by the halting problem.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Springs, New York

... are 102.1 males. For every 100 females age 18 and over, there are 100.8 males. The median income for a household in the town is $57,038, and the median income for ...

 
 
 
This page was created in 25.1 ms