Lesson plan

Recursive language

In mathematics, logic and computer science, a recursive (or decidable) language is a recursive subset of the Kleene closure of an alphabet. Equivalently, a formal language is recursive if there exists a Turing machine that decides the formal language. In theoretical computer science, such always-halting Turing machines are called total Turing machines or algorithms. The concept of decidability may be extended to other models of computation. For example, one may speak of languages decidable on a non-deterministic Turing machine. Therefore, whenever an ambiguity is possible, the synonym used for "recursive language" is Turing-decidable language, rather than simply decidable. The class of all recursive languages is often called R, although this name is also used for the class RP. This type of language was not defined in the Chomsky hierarchy. All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

Back to article

Article summary

In mathematics, logic and computer science, a recursive (or decidable) language is a recursive subset of the Kleene closure of an alphabet. Equivalently, a formal language is recursive if there exists a Turing machine that decides the formal language. In theoretical computer science, such always-halting Turing machines are called total Turing machines or algorithms. The concept of decidability may be extended to other models of computation. For example, one may speak of languages decidable on a non-deterministic Turing machine. Therefore, whenever an ambiguity is possible, the synonym used for "recursive language" is Turing-decidable language, rather than simply decidable. The class of all recursive languages is often called R, although this name is also used for the class RP. This type of language was not defined in the Chomsky hierarchy. All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.