G12FCO -- Formal Computation

Coursework 3 -- solutions

1. Pelicans:

   Simplest is to think of the sequence of events surrounding a green phase:

   output:	R	R	R	R	R	R	R	G	G	G	G	G	R	R	R	R	R	R	R
   tick:	...	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9	10	11	...

   Once the green phase starts, the sequence is determined as far as tick 10; thereafter, a new green phase will start as soon as the button is pushed, so ticks 11, 12, ... are indistinguishable. What if the button is pushed? Well, if at tick 10 onwards, we jump immediately to [effectively] tick 1. If at tick 9, then to tick 0 -- one more red tick, then turn green. Similarly, if at tick 8, then to tick -1, and so on. The only differences are that at ticks 1, 2 and 3 the push is ignored, and that if at tick 4, then the `lead-in' includes some green phase. So effectively, there are 17 states, corresponding to ticks -5 to 11, inclusive:

   	next state		output
   state\input	push	no push	push	no push
   -5	-4	-4	G	G
   -4	-3	-3	R	R
   -3	-2	-2	R	R
   -2	-1	-1	R	R
   -1	0	0	R	R
   0	1	1	R	R
   1	2	2	G	G
   2	3	3	G	G
   3	4	4	G	G
   4	-5	5	G	G
   5	-4	6	G	G
   6	-3	7	R	R
   7	-2	8	R	R
   8	-1	9	R	R
   9	0	10	R	R
   10	1	11	R	R
   11	2	11	G	R

   You can save a state by deleting state 11, making state 10 the looping one, at the expense of the lights turning green only one tick after the button is pushed. Either state 6 or state 10 or state 11 should be the start state, according to taste; this FSM clearly never halts [there perhaps should be another input corresponding to the power cable!]. In an ideal world, the states would be renumbered to start at 0.

   Adding more lights and phases is tedious rather than instructive. Doing it as a McCulloch-Pitts network is instructive. The running phases can be emulated by delay nodes, and the loop phase by a feedback cell [like the memory]. The button push should then trigger a firing that runs round the delays, feeding off to or-cells to control the lights. Some button pushes have no effects, so the delays should also have fibres running to inhibitors that cause the button push to be ignored.

   Marks: 5 each for a basic understanding, for a substantially correct solution, and for accuracy. All minor variants [such as in the start state, and in whether the loop state is at tick 10 or tick 11] equally acceptable.

2. Blank-tape Turing machine:

   The basic idea is to scan right for a bit, then left, then right again, scanning a bit wider each time. If the tape is non-blank, then eventually you will hit something and you can halt. If the tape is blank, then you will never know for sure, as you could always be about to find something no matter how long you've searched. The difficult bit is to scan wider each time; this must clearly be done by marking out how far you've searched each time, then you can explore a little further and move the mark out [or find something and halt]. Let us assume that we use X as the marker; let us further assume that X is a permitted symbol on the tape [how could it be otherwise?]; then in normal operation, we will arrange that the tape now contains a run of X's, bounded by blanks [otherwise we cannot guarantee to know where our X's end and those originally on the tape begin]. [Or we could arrange for the tape to consist of blanks bounded by X's, very similar to the states below and left as an exercise.] We can set this up with three initial states:

   state 0: [start] if current symbol is blank, then write blank, enter state 1 and move right, else halt
   state 1: if current symbol is blank, write X, enter state 2 and move right, else halt
   state 2: if current symbol is blank, write X, enter state 3 and move right, else halt

   At this stage, we check that our current symbol is blank, then start moving left, expecting a sequence of X's followed by a blank, which we overwrite:

   state 3: if current symbol is blank, write blank, enter state 4, and move left, else halt
   state 4: if current symbol is X, write X, stay in state 4 and move left; if it is blank, write X, enter state 5 and move left; anything else is impossible

   Now we are in the same position, having reached the left-hand end of the sequence, so states 5 and 6 are like 3 and 4, but moving right, and entering state 3 again on reaching the blank at the other end. Dotting the i's and crossing the t's left to the reader.

   Marks: Again, 5 each for a general awareness, including the brief explanation of how you can't halt on a blank tape, for the general design, and for accuracy. Full marks for just a smidgeon more than the above level of detail; an exact matrix specification of the FSM would be needed only if a question explicitly asked for it, but you should make it clear that you could do it if necessary.

3. Minimalist machine:

   We already know that a computer is universal if its repertoire of instructions is sufficient to increment and decrement two integers, and to compare them against zero in tests and loops. Given three integers but no decrement, we use m = a-c and n = b-c as the two integers. The comparisons in tests and loops are then given to be valid instructions; to increment m, we increment a, and to decrement it, we increment b and c; likewise for n. 5 marks.

top of page

G12FCO home page

Previous solutions

This coursework