G12FCO -- Formal Computation

Coursework 3 -- Computability

[Very simplified pelican crossing!] A finite-state machine has one input, a button which, at each `tick' is either pressed or not pressed. There is also one output, which is either red or green. It turns green either when the button is pressed or five ticks after the output turned red, whichever is the later, stays green for five ticks, then turns red. Button pushes are ignored if they occur during the first three ticks of the green phase. Construct a matrix description of this FSM.
[Brownie points, but no extra credit, for doing this as a McCulloch-Pitts network, and/or for extending this to `proper' pelican crossings, with flashing green men and controlling also the associated traffic lights.]
Design a Turing machine which halts if and only if it is started on a non-blank tape. Explain briefly why it is not possible to design one which determines whether or not it was started on a blank tape.
[The detailed matrices for the Turing machine are not required. but you should explain the states used in enough detail to make the working clear.]
A computer can increment [but not decrement] any of three variables, say a, b and c, and can compare any two of these variables in instructions such as if a > b then ... endif , and similarly for while. No other instructions are permitted. Show that such a computer is universal.

Hand in no later than Monday, May 17th.

Complete the solutions of the problems from problem class 5.