in Books, Doing Books, Theory of Computation

Theory of Computation #15

Next we need a function which matches the rules with the current state:

Let’s say we have two rules:

And the current state {:state 2 :head 1}. We now want our function to compare the states and read the head position and return the matching rule.

Which is also pretty easy to write:

Ok. Now let’s put everything together. And here we go:

The idea is pretty basic (god I love Lisps) we just find the matching state and apply it results and do that as long we reach an halting state (0). I included a print function at the start of the loop to see what’s happening. In our case we can see the following:

Yeah :)

Write a Comment