# How does it demonstrate that the computational model of rewriting is adequate?

How can I demonstrate that the computational model of rewriting is adequate? For example, with it, it is possible to compute any computable function.

• Show that any TM can be expressed as a rewriting system. It's just a matter of modelling the head movement and tape reading/writing. A type 0 grammar can achieve that. – chi Nov 25 '17 at 19:09
• Are we making a distinction between first order and higher order rewriting? If not then writing an interpreter for a Turing machine in lambda calculus (relatively easy compared to encoding a TM and doing all that jazz) is sufficient. – Jake Nov 26 '17 at 4:08
• @chi thanks for the reply, but how can I write a detailed demonstration that? Could you please show me in more detail? :) – Leomar de Souza Nov 27 '17 at 18:30
• Represent the head of the TM as a nonterminal symbol (encoding the state) in the middle of the tape (made by terminals). Make it move using productions, so that e.g. if $abcQdef$ has to write $w$, move left and change the state to $R$, we have $abRwdef$. You need a production for every state/read-symbol. Use some special terminals for the beginning and end of the tape, so that you know when to extend it. For each state, you will need a nonterminal symbol. – chi Nov 27 '17 at 18:39