Recursive language

In theoretical computer science , a formal language over an alphabet is called recursive (decidable) if a Turing machine M exists that holds on to all inputs and accepts every input if and only if is. The difference to the recursively enumerable languages is, by definition, that a Turing machine must always hold for a recursive language, while one for a recursively enumerable language only has to hold if the word is in the language. ${\ displaystyle L}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ ${\ displaystyle w \ in L}$

The set of recursive languages agrees with all of the predictability models proposed so far . This includes in particular the Goto computability and the while computability , which result from the most common programming constructs on the computer. These similarities are the starting point for Church's thesis .

(Note: The languages generated by primitive recursion only form a real subset of the recursive languages; one can show that these are then the same languages that are also generated by the loop computability .)

The set of recursive languages is a real subset of the Chomsky type 0 languages (recursively enumerable languages) and a real superset of the Chomsky type 1 languages ( context-sensitive languages ):

The halt problem can be enumerated recursively (type 0), but not recursively
There are languages that are recursive but not context-sensitive (type 1).

If there is no Turing machine that solves such a decision problem , then, according to Church's thesis, there is no algorithm for the problem at all. With this definition, one restricts oneself to decision-making problems, i.e. to problems whose answer can only be yes or no . It turns out, however, that despite this restriction, it is usually sufficient, since the calculation problems associated with decision problems are usually no more difficult to solve.

The advantage is that all decision problems can be traced back to languages; these can be described by ( Chomsky ) grammars: An input w is a solution for a decision problem P if and only if w lies in the language L belonging to P ( word problem ). Thus there is a bridge between the generating grammar model and the accepting machine model. Indeed, for every Chomsky grammar class one can find an automaton class that accepts exactly the languages of the respective class and vice versa ( Chomsky hierarchy ).

The non-recursiveness of a language can be demonstrated using Rice's theorem .