Recursive language: Difference between revisions
Content deleted Content added
m see also |
MathMartin (talk | contribs) |
||
| Line 1: | Line 1: | ||
[[Category:Formal languages]] |
[[Category:Formal languages]] [[Category:Computability]] |
||
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|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 machine|Turing machines]], but several other equivalent approaches are possible. |
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|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 machine|Turing machines]], but several other equivalent approaches are possible. |
||
Revision as of 17:19, 6 November 2004
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 languages that are not recursive; one example is given by the halting problem.
See also: undecidable