Register Machine on Fibonacci Numbers

Question

This problem is easy to understand but I am struggling to come up with any solutions.

According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. A (processor) register is a small amount of storage available as part of a CPU or other digital processor.

We can simplify the problem by modelling the registers as empty buckets, and we can let marbles or rocks to be put into the register ("bucket"). The rule is to add or remove marbles from the bucket to perform computations.

The rules are:
1. A register machine uses of a finite number of buckets, and an unending supply of marbles.
2. Each bucket can be individually identified. The marbles need not be distinguishable.
3. A register machine program is a finite set of instructions:
- To add marble to a bucket (and then to go on to the next instruction).
- Or to take a marble away from a bucket (and to go on to one next instruction if you can, or another one, if you can’t).
4. The program can be written in a flowchart or in a list of instructions.

Here is an example of a register machine program that performs addition.
Let A, B, C be buckets.
1. (-B; 2,4) means take away one marble from bucket B, go to instruction 2 if can, or 4 if cannot
2. (+A; 3) means add one marble to bucket A, then go to instruction 3
3. (+C; 1) means add one marble to bucket C, then go to instruction 1
4. (-C; 5,-) means take away one marble from bucket C, go to instruction 2 if can, or exit if cannot
5. (+B; 4) means add one marble to bucket B, then go to instruction 4

It is easily shown that suppose we have 3 marbles in bucket A and 2 marbles in bucket B, and 4 marbles in bucket C. After performing this algorithm, there will be |A|+|B| = 3+2 = 5 marbles in bucket A and |B|+|C| = 2+4 = 6 marbles in bucket B.

Now, I would like to write a register machine code which when given an input of n in bucket A, returns (also in bucket A) the nth Fibonacci number. The Fibonacci numbers are 0 (the 0th), 1 (the 1st), 1 = 0 + 1 (the 2nd), etc. We can use any number of buckets, the goal is to write the code as simple as possible (i.e. with fewest instructions).

Here is my attempt and questions:
1. I know that it is necessary to use a bucket for the "counter".
2. The part that I am struggling is to consider the number of buckets needed. If the input digit is small, we can use less buckets. Since Fibonacci sequence is recursive, if the input digit is large, that means we have to recursively perform the addition and hence need more temporary storage? Or is there any simpler way?
3. I tried to analyse and mimic the algorithm from a programming language, but I found that any programming language is too "high level" and it is difficult to extract it to such simple operations.
4. Suppose we list the Fibonacci numbers with the input number:
0, 1, 1, 2, 3, 5, 8, 13
0, 1, 2, 3, 4, 5, 6, 7
I tried to observe a pattern (which is obvious): If n is 0 or 1, the Fibonacci number is the n itself. Suppose n=2, then the Fibonacci number is 0+1 = 1, where 0 and 1 is the Fibonacci number of n=0 and n=1 respectively. Now again suppose, n=3, the Fibonacci number is 1+1 = 2, where 1 and 1 is the Fibonacci number of n=1 and n=2 respectively. But when n is large to get the Fibonacci number of n-1 and n-2, we need to calculate from the base case. Is there any formula that give the Fibonacci number directly? Besides using golden ratio or similar approaches which I think are hard to program it into a register machine.

Many thanks in advance.

Answer 1

Start with $A=n$, $B=0$, $C=1$, $D=0$. (Or, if by definition all but $A$ are empty, preceed the code with a +C). We want to keep $B=F_{n-A}$, $C=F_{n+1-A}$, $D=0$.

1  while -A {  
2     while -B { 
3        +D 
      }  // that is: D:=B, B:=0
4     while -C {
5        +B
6        +D
      } // that is:  D:=D+C, B:=C, C:=0
7     while -D {
8        +C
      } // that is: C:=D, D:=0
   }
9  while (-B) {
10    +A
   } // that is: A:=B, B:=0
11

Each numbered line corresponds to a state. Lines with while -X mean that we perform -X and go to the next line on success, but to the line following the closing } on failure. Lines with +A mean that we perform +X and go to the next line of the same block, except for the last line before a } go to the enclosing while.