# Recursive language

(Redirected from Decidable language)

A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. This type of language is conspicuously missing from the Chomsky hierarchy.

## Definitions

There are two equivalent major definitions for the concept of a recursive language:

1. A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
2. A recursive language is a formal language for which there exists a turing machine which will, when presented with any input string, halt and accept if the string is in the language, and halt and reject otherwise. The Turing machine always halts; it is known as a decider and is said to decide the recursive language.

All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

## Properties

Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well:

• the Kleene star L* of L
• the concatenation LP of L and P
• the union LP
• the intersection LP
• the complement of L
• the set difference L\P

The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy