# 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

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.