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

  • $\begingroup$ 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. $\endgroup$ – chi Nov 25 '17 at 19:09
  • $\begingroup$ 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. $\endgroup$ – Jake Nov 26 '17 at 4:08
  • $\begingroup$ @chi thanks for the reply, but how can I write a detailed demonstration that? Could you please show me in more detail? :) $\endgroup$ – Leomar de Souza Nov 27 '17 at 18:30
  • $\begingroup$ 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. $\endgroup$ – chi Nov 27 '17 at 18:39

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.