I don' think it could ever learn a general addition algorithm, because the algorithm they are using doesn't allow for a multi-step process. For example, to add 28 + 37, a simple approach would be:
1. first, look at the one's column and recall that 8 + 7 is 15.
2. Then take the value from the tens column of the answer
and add it to the tens column of the arguments.
But given the command : add 28 + 37, it can only execute a single step. It has no way of guessing at and then storing the values for the intermediate command, (take the 1 from the 15 and add it to the 2 from the 28 and the 3 from the 37), to be processed in the next round. Because so it can't ever generalize addition.
Whilst you are correct that the number of allowed computation steps is limited, LSTMs have still been used with success for such tasks. LSTMs have been used to perform addition with 99% accuracy^ on two 9-digit numbers[1]. The paper even shows that simple Python programs can be evaluated with some degree of accuracy.
Remember that even if the number of computation steps is limited, there can be multiple layers ([1] uses 2) and each neuron unit can perform a computation ([1] uses 400 cells per layer). It only needs to learn how to be an ALU. The work is in fact done by one of the people who established the sequence to sequence framework, Sutskever, and is referenced in the Neural Conversational Model paper.
^ They use "teacher forcing" for evaluation which inflates the accuracy to some degree, but it's still quite impressive.
Now for the kicker: recurrent network can implement arbitrary algorithms, including a type of GOFAI. It's quite possible that such an algorithm isn't learnable without supervision; that it was discovered by sheer luck at the dawn of humanity and has been passed down by language ever since.
