Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Decidable language
Main Page | See live article | Alphabetical index

Decidable language

A decidable or recursive language is a formal language that is a recursive set, i.e., 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 number of steps. 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 languagess that are not recursive; one example is given by the halting problem.