Recursive language: Difference between revisions
Content deleted Content added
m cat |
m see also |
||
| Line 4: | Line 4: | ||
All [[regular language|regular]], [[context-free grammar|context-free]] and [[context-sensitive language|context-sensitive]] languages are recursive, but there exist [[recursively enumerable language|recursively enumerable language]]s that are not recursive; one example is given by the [[Halting Problem|halting problem]]. |
All [[regular language|regular]], [[context-free grammar|context-free]] and [[context-sensitive language|context-sensitive]] languages are recursive, but there exist [[recursively enumerable language|recursively enumerable language]]s that are not recursive; one example is given by the [[Halting Problem|halting problem]]. |
||
''See also:'' [[undecidable]] |
|||
Revision as of 07:29, 16 October 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