PGA - ProGram Algebra

# Fibonacci numbers with the use of state machines

Fibonacci numbers are defined as follows:
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) for n >= 2

Here we show how to calculate Fibonacci numbers with the use of natural number counters as state machines. As instruction set we use PGLEcw (PGLE with conditional constructs and while loops).

```    smnnc:y.succ;
{*;
- smnnc:x.isZero {*;
smnnc:z.succ;
smnnc:x.pred;
*};
- smnnc:y.isZero {*;
smnnc:x.succ;
smnnc:y.pred;
smnnc:z.succ;
*};
- smnnc:z.isZero {*;
smnnc:y.succ;
smnnc:z.pred;
*};
smnnc:y.dump;
*}
```
We assume that `x` and `y` are the last two Fibonacci numbers. The next number is calculated as follows:
```    z = x
x = y
y = y + z
```
The only operations the natural number counter provide are `succ`, `pred`, and `isZero`. So these assignments are done in a more primitive way.

Initially, a natural number counter has the value `0`, so we start with only setting `y` to the value `1`.
Next, we start an unconditional while loop which consist of three parts.

• assign the value of `x` to `z` after which the value of `x` is `0`
• assign the value of `y` to `x` after which `y` becomes zero,
at the same time, the value of `y` is added to `z` which now has the value of `x + y`
• assign the value of `z` to `y` after which `z` has the value `0`

The last instruction of the while loop outputs the value of counter `y`.

We can start the simulator with the following command:

gensim -P PGLEcw -B FMN -l fibonacci
Running the program gives the following output:
```    natural number counter y: 1
natural number counter y: 2
natural number counter y: 3
natural number counter y: 5
natural number counter y: 8
natural number counter y: 13
natural number counter y: 21
natural number counter y: 34
natural number counter y: 55
natural number counter y: 89
natural number counter y: 144
natural number counter y: 233
natural number counter y: 377
natural number counter y: 610
.
.
.
```