The lambda calculus is a rewriting system and Turing complete. Which are the rewriting systems corresponding to the other levels of the Chomsky hierarchy? E.g. what is the functionally computing system for finite state machines and so on?

  • $\begingroup$ Lots of rewriting systems could be used. The common way to do it is grammars. What sort of rewriting are you thinking of if grammars don't qualify? $\endgroup$ Commented Dec 13, 2013 at 9:40
  • $\begingroup$ @reinierpost: I understand grammars as rules to form all words of a language. When I speak of functional rewriting here, with the example of the lambda calculus, I think of a scheme where I provide a syntactically correct expression and the formalism computes by reducing it to some result. Te way finite state machines are typtically introduced is by some kind of board game where you move your figures, not by an expression which collapses down until you have your answer. $\endgroup$
    – Nikolaj-K
    Commented Dec 13, 2013 at 9:47
  • $\begingroup$ The rules of a grammar can be applied as rewrite rules. This trick actually sees quite a bit of use. $\endgroup$ Commented Dec 13, 2013 at 12:34
  • $\begingroup$ I discovered this thread: which-models-of-computation-can-be-expressed-through-grammars, with a related topic. $\endgroup$
    – Nikolaj-K
    Commented Dec 14, 2013 at 21:15
  • $\begingroup$ @Nick Kidman: If you want the rewrite rules to reduce, then automata to parse the language in question come to mind, reducing a string to a yes/no decision (you could modify them to emit 'yes' or 'no'. The classes of automata used are standard, too (finite; pushdown; linear bounded). $\endgroup$ Commented Dec 19, 2013 at 9:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.