Skip to content
 

Context-sensitive Grammars and Turing Completeness

Entering “context sensitive grammars are Turing complete” in Google returns plenty of results, re-printed one from other, including this Wikipedia page, that cites:

Classical Turing-complete systems include context-sensitive grammars, recursive functions and lambda calculus.

While I agree on recursive functions and lambda calculus I definitely do not on context-sensitive grammars!

In middle fifties Noam Chomsky has proposed classification of formal grammars, which he has explained in great detail in his paper “On certain formal properties of grammars”. He simply states that only Type 0 grammars (just any kind of grammars you might imagine, without any restrictions) are Turing-complete. Context-sensitive grammars are Type-1 grammars and are recognizable by linear bounded automaton.
Would context-sensitive (Type-1) grammars be Turing-complete they’d be able to express arbitrary sequences (as Turing-complete system is a universal computer, capable of computing anything). At the same time ability to express arbitrary sequences is only achievable by Type-0 systems! As Type-1 != Type-0, we’ve proved what we wanted! :)

Leave a Reply