Hacker News new | ask | show | jobs
by tel 4151 days ago
The type of abstract syntax trees of this language and brainfuck are isomorphic. There are lots of definitions of what a "Turing Machine" is. If we take the one on Wikipedia as canon it isn't the same as this.

In particular, a Turing Machine is a model while both Brainfuck and Groot are languages. It's easy to see how each of these languages is directly translated into a Turing Machine model (providing them a choice of semantics). Indeed, due to their isomorphism we need only translate one of them to have a faithful translation of the other "for free".

Better yet, Brainfuck and Groot both have a privileged semantic model which is more or less identically a Turing Machine (except Brainfuck merely specifies that the tape is at least 30,000 bytes long and Groot mentions site not at all while Turing Machines are explicitly infinite).

So, they're really closely related to a Turing Machine but honestly separate things more closely related to one another (via isomorphism) than to TMs directly (via semantic mapping).