in Books, Doing Books, Theory of Computation

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

Write a Comment