Content deleted Content added
→Definitions: use the definition from the textbook by Sipser. |
m →Definitions: add wiki-link. |
||
Line 14:
# A recursive language is a [[recursive set|recursive]] subset of the set of all possible finite-length [[formal language|words]] over an [[alphabet (formal languages)|alphabet]].
# A recursive language is a [[formal language]] for which there exists a [[Turing machine]] that [[decider (Turing machine)|decides]] it.
By the second definition, any [[decision problem]] can be shown to be decidable by exhibiting an [[algorithm]] for it that terminates on all inputs. An [[undecidable problem]] is a problem that is not decidable.
| |||