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!
Archive of entries posted on 29th December 2010



