¿Por qué se completa FRACTRAN turing?

Traté de buscar en Google una explicación, pero la mayoría de los enlaces solo dicen cosas como "FRACTRAN se está completando. Como ejemplo, veamos la multiplicación".

Recuerdo haber visto una publicación en el foro xkcd que decía que FRACTRAN ayudó al afiche a comprender la integridad de Turing. Estoy buscando una explicación intuitiva de por qué este esolang está Turing completo, ya que no es muy obvio mirar la mecánica del lenguaje.

Para que un lenguaje imperativo sea Turing completo debe tener:

1. Bucle condicional
2. Número arbitrario de variables

FRACTRAN es un lenguaje que se compone de una serie de fracciones que almacena sus datos en los exponentes de los números primos.

Digamos que desea agregar dos números: 2 ^a 3 ^{b se} convierte en 5 ^ab

455 11 1 3 11 1
---, -, -, -, -, -
 33 13 11 7 2 3

Ese es un programa FRACTRAN para hacer ese cambio anterior.

Empiezas con un número como 72 (2 ³ 3 ² ). El programa 'avanza' hasta que encuentra un número que cuando se multiplica por la instrucción es otro número entero (no se permiten restos).

72correrá hacia adelante hasta que llegue 11/2. Luego dividirá el número por 2y lo multiplicará por 11(la potencia en 11 es una variable). Esto da 396. 396es divisible por 33 (reduciendo la potencia 3 y la 11) y multiplica por 455 (incrementando 5, 7 y 13 variables). Y así. La descripción completa de este programa y su tabla de estado se puede leer en la página de Wikipedia de FRACTRAN , incluido un gif animado realmente agradable del programa anterior.

Se puede encontrar otro material de FRACTRAN en Stack Exchange que toca la integridad de Turing en: Convertir Fractran en Brainfuck (ok, es un uso realmente productivo del tiempo)

La razón por la que Fractran es Turing completo es porque simula una máquina de registro. La factorización prima del número almacena el contenido de los registros, mientras que la división y multiplicación es una forma de sumar y restar condicionalmente de los registros.

Parte del truco aquí (y esto comienza a desviarse de la teoría) es que detrás de escena, esta es una máquina de registro Minsky para la cual se demostró que ciertas cintas (programas) son máquinas de Turing SI la cinta se representa como un número de Gödel que es exactamente cuál es el número de FRACTRAN (de la página vinculada de Wikipedia):

Gödel utilizó un sistema basado en la factorización prima. Primero asignó un número natural único a cada símbolo básico en el lenguaje formal de la aritmética con el que estaba tratando.

Entonces, tenemos bucles condicionales, variables arbitrarias almacenadas como números de Gödel, tenemos una máquina de Turing.

¿Alguna otra lectura divertida que toque el Collatz como la naturaleza de FRACTRAN se puede leer en Can't Decide? Indeciso! que relacionan la conjetura de Collatz con FRACTRAN y el problema de detención.

FRACTRAN es un poco difícil de entender.

Considere el programa algo así como:

LABEL: start
    block1
    block2
    block3
    ...
END

En esto, cada bloque tiene la forma:

IF(registers X >= a, Y >= b)  # or any combination of registers
THEN
    X -= a
    Y -= b

    I += n
    J += m

    goto start

La primera declaración del programa de multiplicación anterior:

455
---
 33

Se escribiría de esta forma como:

IF(register `3` >= 1 && `11` >= 1)
THEN
     `3` -= 1
    `11` -= 1

     `5` += 1
     `7` += 1
    `13` += 1

    goto start

Y así puede ver claramente el almacenamiento de datos y las construcciones de bucle necesarias para la integridad de Turing. Es muy rudimentario, pero existe y funciona como una máquina de registro simple, pero eso es todo lo que realmente necesita para poder hacer.

¿Todavía no está convencido?

Esto se basa principalmente en una conferencia de Dimitri Hendricks sobre Modelos de computación

Esto toma el programa muy simple (2/3)que es un sumador (2 ^a 3 ^b -> 3 ^{a + b} ) Pero es destructivo: el valor en 2 se borra como parte del proceso.

Vamos a escribir un FRACTRAN de nivel superior que hace que sea fácil no hacer tal destrucción.

El programa original podría considerarse como:

   2
α: - → α
   3

En F ₂ , uno puede especificar 'funciones' de una especie.

   10 1
α: - → α, - → β
    3 1

   3
β: - → β
   5 5 

Para convertir un programa F ₂ (P) en un programa FRACTRAN estándar, uno hace:

1. Borrar P de bucles de longitud 1
2. Reemplazar letras griegas (funciones) con números primos nuevos
3. Reemplazar las transiciones:

   as
p: - → q, - → r, - -> s, ...
   bdf

se convierte en:

aq cr es
-, -, -, ...
bp dp fp

Lo que esto ha hecho es usar los primos p, q, r y s para almacenar el estado del programa.

Y luego tenemos la máquina de registro ... tiene un número finito de registros que almacenan grandes números arbitrarios y dos instrucciones:

• inc (x _i , m): incremente el registro i y vaya a la línea m
• jzdec (x _i , m ₁ , m ₂ ): si el registro i es 0, vaya a la línea m, de lo contrario disminuya i, y vaya a la línea m2.

Se ha demostrado que esta máquina de registro está completa.

Luego muestra el proceso en varias diapositivas de compilación de un programa de máquina de registro en un programa FRACTRAN como parte de un proceso mecánico.

Básicamente:

                       Pi)
inc (x (i), m) = ---- → m
                        1

                        1 1
jzdec (x (i), m1, m2) = ---- → m2, - → m1
                       p (i) 1

Y así, debido a la equivalencia entre estos dos modelos de computación, FRACTRAN está completando Turing.

Por cierto, si realmente quieres que te vuelvas loco, lee Code Golf: Fractran en el que algunas personas escribieron un programa FRACTRAN para ejecutar otro programa FRACTRAN.