# Problem on finite state machines in the feynman textbook

I'm currently reading Feynman Lectures on Computation and got stuck in problem 3.1 which says

Suppose we feed a sequence of 1's and 0's - a binary number - into a machine. Design a machine which performs a pairwise sum of the digits, that is, one which takes the incoming digits two at a time and adds them, spitting the result out in two steps. So, if two digits come in as 00, it spits out 00; a 10 or 01 results in a 01 (1+0 = 10+11!); but a 11 results in binary 10: 1+1 = 2, in decimal, 10 in binary. I will give you a hint: the machine will require four states.

I don't ask you the answer. Just I don't understand what this is asking. For example, when the input sequences are (00)(01)(10)(11)(10)(00), output sequences should be what?

Thanks in advance.

## 2 Answers

The numbers are encoded LSB first. In your example, $(00)(01)(10)(11)(10)(00)$ corresponds to the addition $011100 + 001010$, and the answer should be $011001(0)$, corresponding to the binary answer $(0)100110$. The bit in parentheses is the carry bit, which I don't think Feynman intended you to output.

More generally, Feynman wasn't very accurate, so you should think of a reasonable concrete interpretation of the problem which will result in an automaton which has a small number of states; I can think of several, some of which requiring less than four states. (It depends whether $(00)$ is a single digit or a pair of consecutive digits.) I don't think it's very important to guess what Feynman intended exactly.

I agree that Feynman was not very accurate. But I am not sure Yuval's interpretation is correct, particularly because in problem 3.3 in the same section Feynman asks for the binary adder Yuval describes.

For problem 3.1, it isn't clear to me if the sequence (00) is entered as a single digit or two consecutive digits. It is also unclear to me if the input is (11) that the output (10) needs to be output over two states (e.g. output '1' at t=n, and then '0' at t=n+1) or over a single state (output '10' at t=n). If the sequence is entered 1 digit at a time, and the output must also be 1 digit at a time, then there is no way to make this machine using 4 states and not incorporating a delay.

The question RFP was asking remains ambiguous...