Term re-writing systems are a really interesting way of looking at computation.
It completely abstracts away the concept of a machine, and it's simply translation as computation - but equally as powerful.
It's a shame the standard texts are all 20 years old or more than way too heavy mathematically.
A little book for term rewriting would be a great new addition.
loading story #42067199
Agreed. This reminds me – and I wonder if it could be applied – to Computational Type Theory, which relies on a similar concept of "reducing" types to their primitive forms, actually taking computation into account (something type theories normally do not!)
This lecture series goes into how it works: https://www.youtube.com/watch?v=LE0SSLizYUI
I would argue that it is more "primordial". After all, computation is first and foremost a human activity, generally performed using pen and paper, which involves a good deal of rewriting (computers were originally people). The machine only came later as a way to simulate this human activity. Its meaning is entirely contingent on the primordial notion. It have no meaning on its own.
loading story #42070162