Recursive language

A formal language is called recursive ( decidable ) if there exists a Turing machine M that holds on all inputs, ie, and each input if and only accepted if it is.

The non- recursive nature of a language can be demonstrated by means of set of Rice.

If there is no Turing machine that solves such a decision problem, so there's according to the Church 's thesis in general no algorithm for the problem. It is limited in this definition to decision problems, ie problems whose answer can only be yes or no. But it turns out that it is usually sufficient, despite this constraint, since the decision problems associated with computational problems are usually not difficult to solve.

The advantage is that you can reduce all decision problems languages; these can be described by, among others ( Chomsky ) grammars: An input w is a decision problem P iff a solution if w is in the language L corresponding to P (word problem). Thus, there is a bridge between the generating grammar model and the accepting machine model. In fact, you can find at any Chomsky grammar class a machine class which accepts exactly the languages ​​of the respective class, and vice versa ( Chomsky hierarchy ).

The set of recursive languages ​​is a proper subset of Chomsky type 0 (or recursively enumerable ) languages ​​and proper superset of the Chomsky - type 1 languages:

  • The halting problem is recursively enumerable ( type 0), but not recursively
  • There are languages ​​that recursive, but not context-sensitive (type 1).

The set of recursive languages ​​is consistent with all the predictability models proposed so far. These include in particular which emerge from the most common programming constructs on the computer the Goto - predictability and the While predictability. These similarities are the starting point for the Church's thesis.

(Note: The languages ​​generated by primitive recursion only form a proper subset of recursive languages, one can show that this will be the same languages ​​that are generated by the loop predictability. )

The difference to the recursively enumerable languages ​​is by definition that a Turing machine for a recursive language must always hold, while a must hold recursively enumerable for a language only if the word is in the language.

  • Compiler
  • Theory of formal languages
  • Language type
Rice's theorem Word problem (computability)
309583
de