Registrar la máquina en los números de Fibonacci

Question

Este problema es fácil de entender, pero me cuesta encontrar una solución.

Según la Wikipedia, una máquina de registro es una clase genérica de máquinas abstractas que se utilizan de forma similar a una máquina de Turing. Un registro (de procesador) es una pequeña cantidad de almacenamiento disponible como parte de una CPU u otro procesador digital.

Podemos simplificar el problema modelando los registros como cubos vacíos, y podemos dejar que las canicas o las piedras se introduzcan en el registro ("cubo"). La regla es añadir o quitar canicas del cubo para realizar cálculos.

Las reglas son:
1. Una máquina registradora utiliza un número finito de cubos y un suministro interminable de canicas.
2. Cada cubo puede identificarse individualmente. No es necesario que las canicas sean distinguibles.
3. Un programa de máquina de registro es un conjunto finito de instrucciones:
- Para añadir canicas a un cubo (y pasar a la siguiente instrucción).
- O para quitar una canica de un cubo (y pasar a una siguiente instrucción si puedes, u otra, si no puedes).
4. El programa puede estar escrito en un diagrama de flujo o en una lista de instrucciones.

Este es un ejemplo de un programa de máquina registradora que realiza una suma.
Sean A, B, C los cubos.
1. (-B; 2,4) significa quitar una canica del cubo B, pasar a la instrucción 2 si se puede, o a la 4 si no se puede
2. (+A; 3) significa añadir una canica al cubo A, y luego pasar a la instrucción 3
3. (+C; 1) significa que se añade una canica al cubo C y se pasa a la instrucción 1
4. (-C; 5,-) significa quitar una canica del cubo C, pasar a la instrucción 2 si se puede, o salir si no se puede
5. (+B; 4) significa que se añade una canica al cubo B y se pasa a la instrucción 4

Se demuestra fácilmente que supongamos que tenemos 3 canicas en el cubo A y 2 canicas en el cubo B, y 4 canicas en el cubo C. Después de realizar este algoritmo, habrá |A|+|B| = 3+2 = 5 canicas en el cubo A y |B|+|C| = 2+4 = 6 canicas en el cubo B.

Ahora, me gustaría escribir un código máquina de registro que cuando se le da una entrada de n en el cubo A, devuelve (también en el cubo A) el enésimo número de Fibonacci. Los números de Fibonacci son 0 (el 0º), 1 (el 1º), 1 = 0 + 1 (el 2º), etc. Podemos utilizar cualquier número de cubos, el objetivo es escribir el código lo más sencillo posible (es decir, con el menor número de instrucciones).

Aquí está mi intento y mis preguntas:
1. Sé que es necesario utilizar un cubo para el "contador".
2. La parte que me cuesta es considerar el número de cubos necesarios. Si el dígito de entrada es pequeño, podemos utilizar menos cubos. Dado que la secuencia de Fibonacci es recursiva, si el dígito de entrada es grande, significa que tenemos que realizar recursivamente la adición y por lo tanto necesitamos más almacenamiento temporal? ¿O hay alguna forma más sencilla?
3. Intenté analizar e imitar el algoritmo desde un lenguaje de programación, pero descubrí que cualquier lenguaje de programación es demasiado "de alto nivel" y es difícil extraerlo a operaciones tan simples.
4. Supongamos que enumeramos los números de Fibonacci con el número de entrada:
0, 1, 1, 2, 3, 5, 8, 13
0, 1, 2, 3, 4, 5, 6, 7
Intenté observar un patrón (que es obvio): Si n es 0 o 1, el número de Fibonacci es el propio n. Supongamos n=2, entonces el número de Fibonacci es 0+1 = 1, donde 0 y 1 es el número de Fibonacci de n=0 y n=1 respectivamente. Ahora supongamos de nuevo, n=3, el número de Fibonacci es 1+1 = 2, donde 1 y 1 es el número de Fibonacci de n=1 y n=2 respectivamente. Pero cuando n es grande para obtener el número de Fibonacci de n-1 y n-2, tenemos que calcular desde el caso base. ¿Existe alguna fórmula que dé el número de Fibonacci directamente? Además de utilizar la proporción áurea o enfoques similares que creo que son difíciles de programar en una máquina de registro.

Muchas gracias de antemano.

Answer 1

Comience con $A=n$ , $B=0$ , $C=1$ , $D=0$ . (O, si por definición todos menos $A$ están vacíos, preceda el código con un +C ). Queremos mantener $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

Cada línea numerada corresponde a un estado. Las líneas con while -X significa que realizamos -X y pasar a la siguiente línea en caso de éxito, sino a la línea que sigue al cierre } en el fracaso. Las líneas con +A significa que realizamos +X y pasar a la siguiente línea del mismo bloque, excepto la última línea antes de un } ir al recinto while .