G12FCO -- Formal Computation

Problem Class 5 -- Machines

Construct a network of McCulloch-Pitts cells that adds two binary numbers. Specifically, there are two input fibres, one for each number, each of which fires or not according as the corresponding digit is 1 or 0, and there is to be one output fibre, which fires similarly according to the digit in the sum. Assume that the numbers are presented with their least-significant digits first -- else it can't be done by a FSM!
[Hint: You also need internally to construct the `carry', which fires if at least two of the inputs and the previous carry fire. The output should fire if either exactly one or all three of these fire.]
Construct a Turing machine which adds two binary numbers. E.g., you could start with X1101+111X on the tape, using X as a marker, and the read head over, say, the left-most X, and finish with X10100X on the tape.
A Turing machine is started with a blank tape. Show that it is not possible, in general, to determine whether or not it ever again has a blank tape.