3
$\begingroup$

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?

$\endgroup$
  • $\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$ – reinierpost Dec 13 '13 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 Dec 13 '13 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$ – Charles Stewart Dec 13 '13 at 12:34
  • $\begingroup$ I discovered this thread: which-models-of-computation-can-be-expressed-through-grammars, with a related topic. $\endgroup$ – Nikolaj-K Dec 14 '13 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$ – reinierpost Dec 19 '13 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.