Skip to content
Archive of entries posted on 29th December 2010

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!