<p>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?</p>

CC BY-SA 3.0
2013-12-13T09:40:30.983Z
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?
reinierpost
CC BY-SA 3.0
2013-12-13T09:47:37.117Z
@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.
Nikolaj-K
CC BY-SA 3.0
2013-12-13T12:34:30.900Z
The rules of a grammar can be applied as rewrite rules.  This trick actually sees quite a bit of use.
Charles Stewart
CC BY-SA 3.0
2013-12-14T21:15:51.537Z
I discovered this thread: [which-models-of-computation-can-be-expressed-through-grammars](http://cstheory.stackexchange.com/questions/6437/which-models-of-computation-can-be-expressed-through-grammars), with a related topic.
Nikolaj-K
CC BY-SA 3.0
2013-12-19T09:08:14.297Z
@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).
reinierpost
<term-rewriting-systems>
Which are the rewriting systems corresponding to the levels of the computatational hierarchy?
Nikolaj-K
# Which are the rewriting systems corresponding to the levels of the computatational hierarchy?

(Asked by: username_0 on 2013-12-12)

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?

**Tags:** term-rewriting-systems

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1: 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.  
> **username_2**: The rules of a grammar can be applied as rewrite rules.  This trick actually sees quite a bit of use.  
> **username_0**: I discovered this thread: [which-models-of-computation-can-be-expressed-through-grammars](http://cstheory.stackexchange.com/questions/6437/which-models-of-computation-can-be-expressed-through-grammars), with a related topic.  
> **username_1**: @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).  

---

## 0 answers

