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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.