Turing machines and the rest

A Turing machine (TM) is a generalization of a PDA which uses a tape instead of a stack. Turing machines are an abstract version of a computer - they have been used to define formally what is computable. There are a number of alternative approaches to formalize the concept of computability (e.g. called the $\lambda$-calculus, or $\mu$-recursive functions, ...) but they can all shown to be equivalent. That this is the case for any reasonable notion of computation is called the Church-Turing Thesis.

On the other side there is a generalization of context free grammars called phrase structure grammars or just grammars. Here we allow several symbols on the left hand side of a production, e.g. we may define the context in which a rule is applicable. Languages definable by grammars correspond precisely to the ones which may be accepted by a Turing machine and those are called Type-0-languages or the recursively enumerable languages.

Turing machines behave different from the previous machine classes we have seen: they may run forever, without stopping. To say that a language is accepted by a Turing machine means that the TM will stop in an accepting state for each word which is in the language. However, if the word is not in the language the Turing machine may stop in a non-accepting state or loop forever. In this case we can never be sure whether the given word is in the language - i.e. the Turing machine doesn't decide the word problem.

We say a language is decidable, if there is a TM which will always stop. There are type-0-languages which are not decidable -- the most famous one is the halting problem. This is the language of encodings of Turing machines which will always stop.

There is no type of grammars which captures all decidable languages (and for theoretical reasons there cannot be one). However there is a subset of decidable languages which are called context-sensitive languages which are given by context-sensitive grammars, these are those grammars where the left hand side of a production is always shorter than the right hand side. Context sensitive languages on the other hand correspond to linear bounded TMs, these are those TMs which use only a tape whose length can be given by a linear function over the length of the input.