Theory of Computation #14

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

Also not that hard:

Here are all the tests so far:

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:

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:

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

Theory of Computation #13

Exercise 3.1.1: With what tape configuration will the Turing machine represented below halt if it is started with its tape configured as _x_xx delta delta delta…?


A table works fine for going through that:

Tape State Transition
_x_xxddd 0 x/R
x_x_xddd 1 x/R
xx_x_ddd 0 x/R
xxx_d_dd 1 d/R
xxxd_d_d 0 d/d
xxxd_d_d 2 halt

Exercise 3.1.3: Design a Turing machine that, when started with its tape head over the leftmost tape cell, will suffer an abnormal termination if and only if and x is recorded somewhere on its tape. If you applied your machine to a tape that did not contain an x, would the machine ever detect that fact?

The idea is pretty basic. We start in a state and repeat a state which isn’t left in case no x is found. If a x is found it goes into a next state which just repeats going left over and over again.

In case there’s no x on the tape, the machine will go into an infinite look checking every cell of the infinite right side.


Exercise 3.6.1P: Develop a Turing machine simulator. Design the simulator so that the description of the machine to be simulated is provided in a tabular form that can be replaced easily by the description of another machine.

So, a Turing machine has the following features:

  • It has a tape which is infinite to the right, if nothing written on it then they are blank
  • It has a head which can write and write at the current tape cell
  • It has a state register which stores the current state
  • It has a table of instructions which take the state, the current symbol and tells the machine what to write and a new state

Let’s start with building the machine without the instruction table first. I.e. it can read, write and move it’s head.

The first thing we want it to do is read the current cell. The cell will be represented as a vector.

This tape consists of a b blank a a. Our machine also needs to know its current head position.

This is rather easy:

Now, we need an option to write:

This is also very easy:

Next part tomorrow

Theory of Computation #12

Let’s take the rules from the beginning.

The result should be:

Here’s the final code which stitches together all our functions:

And the result is:

Yay. This took a while.

Theory of Computation #11

The next major step is to transform existing rules to CNF. We have to do two things:

A) Transform the terminals to new non-terminals
B) Shorten the rule

A) seems easier, so let’s do that first.

Examples: xA, By

In this case, we have to create a new variable – for the sake of simplicity its name will be the name of the terminal in uppercase – and replace it.

Before that I need a function which decomposes the string.

Here’s the code and test: (I edited the input later to directly take a decomposed map)

Ok, now we can concentrate on the right-side of the rules. Want we want the function from before:

The idea is pretty basic. We extract each terminal, i.e. lower case, and create a new rule for that, afterwards we take the initial rule and uppercase everything.

Now we have a list of rules which may be too long. Let’s take care of that.

For the sake of simplicity I will use variables A to H for existing rules. And everything higher than that for new rules which are needed for shortening the existing one.

Let’s say we have the following transformed rules:

What we want is:

Here’s the function to do that:

It works. So, now we need to put everything together.

Continue tomorrow