FRACTRAN

FRACTRAN es un lenguaje de programación esotérico completo de Turing propuesto por John Conway .

Descripción

Un programa FRACTRAN se escribe como una lista ordenada de fracciones positivas junto con una entrada de entero positivo inicial n . El programa se inicia actualizando el entero n de la siguiente manera:

para la primera fracción en la lista para la cual el producto es un número entero, reemplace con $F$ ${\ estilo de visualización n \ c punto f}$ $norte$ ${\ estilo de visualización n \ c punto f}$
repita esta regla hasta que ninguna de las fracciones en la lista produzca un número entero cuando se multiplique por , luego deténgase. $norte$

Por ejemplo, el siguiente programa genera números primos :

\left({\frac {17}{91)),{\frac {78}{85)),{\frac {19}{51)),{\frac {23}{38)), {\frac {29}{33)),{\frac {77}{29)),{\frac {95}{23)),{\frac {77}{19)),{\frac {1} {17)),{\frac {11}{13)),{\frac {13}{11)),{\frac {15}{2)),{\frac {1}{7)),{ \frac{55}{1}}\derecha)

Comenzando con n = 2, este programa genera la siguiente secuencia de números enteros:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... Secuencia OEIS A007542

Después de 2, esta secuencia contiene las siguientes potencias de 2:

2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048 ,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\puntos

secuencia A034785 en OEIS

que son potencias primas de 2.

Entendiendo el programa FRACTRAN

El programa FRACTRAN se puede considerar como un tipo de máquina de Minsky , donde los registros se almacenan en exponentes simples en el argumento n .

Usando la numeración de Gödel , un entero positivo n puede codificar un número arbitrario de variables enteras positivas arbitrariamente grandes. El valor de cada variable se codifica como un exponente de un número primo en una factorización de entero simple. Por ejemplo, un número entero

60=2^{2}\times 3^{1}\times 5^{1}

representa el estado de un registro en el que una variable (a la que llamaremos ) contiene el valor 2 y otras dos variables ( y ) contienen el valor 1. Todas las demás variables contienen el valor 0. $v_{2}$ $v_{3}$ ${\ estilo de visualización v_ {5}}$

El programa FRACTRAN es una lista ordenada de fracciones positivas. Cada fracción es una instrucción que prueba una o más variables representadas por los factores primos de su denominador . Por ejemplo:

{\displaystyle f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1))))

comprueba dos variables y . Si y , entonces se realizan las asignaciones , , . Por ejemplo: $v_{2}$ ${\ estilo de visualización v_ {5}}$ $v_{2}\geq 2$ $v_{5}\geq 1$ $v_{2}:=v_{2}-2$ $v_{5}:=v_{5}-1$ $v_{3}:=v_{3}+1$ $v_{7}:=v_{7}+1$

60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3\times 7}{2^{2}\times 5 ^{1}}}=3^{2}\veces 7^{1}

Dado que el programa FRACTRAN es solo una lista de fracciones, estas instrucciones de prueba y asignación son las únicas instrucciones válidas en el lenguaje FRACTRAN. Además, se aplican las siguientes restricciones:

Cada vez que se ejecuta una instrucción, las variables que se prueban también se reducen.
La misma variable no puede ser decrementada e incrementada en la misma instrucción (de lo contrario, la fracción que representa esa instrucción no sería irreducible ).
La instrucción FRACTRAN no puede verificar directamente si una variable es igual a 0. Sin embargo, hay una forma indirecta de hacerlo mediante la creación de una instrucción que se coloca después de otras instrucciones que verifican una variable en particular.

Enlaces

"Patología de los Números Primos: Fractran"
Weisstein, Eric W. "FRACTRÁN". mundo matemático.
Patología de números primos
FRACTRAN
Implementación de Ruby y programas de ejemplo.
Proyecto Euler Problema 308
"Construyendo Fizzbuzz en Fractran desde abajo hacia arriba"
Chris Lomont, "Un intérprete universal de FRACTRAN en FRACTRAN"