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?
Which are the rewriting systems corresponding to the levels of the computatational hierarchy?
term rewriting systems