Theory of Computation #14

Now we want a function to move the head to the left and write:

(move-head 2 :right) -> 3
(move-head 2 :left) -> 1

Also not that hard:

(defn move-head
  "Moves the head to the direction by one."
  [position direction]
  (cond (= direction :left) (if (zero? position)
                              nil
                              (dec position))
        (= direction :right) (inc position)
        :else nil))

Here are all the tests so far:

(with-test
  (def tape [:a :b nil :a :a])

  (is (= (read-tape tape 0) :a))
  (is (= (read-tape tape 2) nil))
  (is (= (read-tape tape 6) nil))

  (is (= (write-tape tape 0 :c) [:c :b nil :a :a]))
  (is (= (write-tape tape 2 :a) [:a :b :a :a :a]))

  (is (= (move-head 0 :right) 1)) 
  (is (= (move-head 0 :left) nil))
  (is (= (move-head 3 :left) 2)))

Now we need to think about states. We have the current position of the head and the current state of the program.

The good thing is that we don’t need variables which can be accessed from everywhere, i.e. we can put these states without problems in our execution loop and bind them locally.

The last thing we need is the rule table. The rule table consists of rules which match with the current state and current symbol and perform a write and change in state.

We can represent that with a hash-map:

{:start 2
:symbol :b
:write :right
:end 3}

This rule for example is activated if the start state is 2 and the current symbol is :b. It moves the head to the right and moves to state 3. If write is neither :left or :right it writes the symbol in the current cell.

Similarly, we can describe our current machine state:

{:state 3
:head 2}

In this example the program state is 3 and the head is on position 2. I reserve state 0 to be the halting state.

Next part tomorrow