Hispanopedia Wiki
Articulo de referencia

FRACTRAN

FRACTRAN es un lenguaje de programación esotérico Turing-completo inventado por el matemático John Conway . Un programa FRACTRAN es una lista ordenada de fracciones positivas ju...

Hispanopedia WikiContenido en espanolLectura gratuita

FRACTRAN es un lenguaje de programación esotérico Turing-completo inventado por el matemático John Conway . Un programa FRACTRAN es una lista ordenada de fracciones positivas junto con un entero positivo inicial n . El programa se ejecuta actualizando el entero n de la siguiente manera:

  1. Para la primera fracción f de la lista para la cual nf es un número entero, reemplace n por nf.
  2. Repite esta regla hasta que ninguna fracción de la lista produzca un número entero al multiplicarse por n , y luego detente.

Conway (1987) presenta el siguiente programa FRACTRAN, llamado PRIMEGAME, que encuentra números primos sucesivos :

(1791,7885,1951,2338,2933,7729,9523,7719,117,1113,1311,152,17,551){\displaystyle \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}}\right)}

A partir de n = 2, este programa FRACTRAN genera la siguiente secuencia de números enteros:

  • 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (secuencia A007542 en el OEIS ) , es decir, la secuencia de números de PRIMEGAME

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

22=4,23=8,25=32,27=128,211=2048,213=8192,217=131072,219=524288,…{\displaystyle 2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\dots }(secuencia A034785 en el OEIS )

La parte exponencial de estas potencias de dos son números primos: 2, 3, 5, etc.

Comprender un programa FRACTRAN

Un programa FRACTRAN puede considerarse como un tipo de máquina de registros donde los registros se almacenan en exponentes primos en el argumento.norte{\displaystyle n}.

Utilizando la numeración de Gödel , un número entero positivonorte{\displaystyle n}puede codificar un número arbitrario de variables enteras positivas arbitrariamente grandes. [ nota 1 ] El valor de cada variable se codifica como el exponente de un número primo en la factorización prima del entero. Por ejemplo, el entero

60=22×31×51{\displaystyle 60=2^{2}\times 3^{1}\times 5^{1}}

representa un estado de registro en el que una variable (que llamaremosv2{\displaystyle v_{2}}) contiene el valor 2 y otras dos variables (v3{\displaystyle v_{3}}yv5{\displaystyle v_{5}}) mantiene el valor 1. Todas las demás variables mantienen el valor 0.

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

F1=2120=3×722×51{\displaystyle f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1}}}}

pruebasv2{\displaystyle v_{2}}yv5{\displaystyle v_{5}}. Siv2≥2{\displaystyle v_{2}\geq 2}yv5≥1{\displaystyle v_{5}\geq 1}, luego resta 2 dev2{\displaystyle v_{2}}y 1 dev5{\displaystyle v_{5}}y suma 1 av3{\displaystyle v_{3}}y 1 av7{\displaystyle v_{7}}. Por ejemplo:

60⋅F1=22×31×51⋅3×722×51=32×71{\displaystyle 60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3\times 7}{2^{2}\times 5^{1}}}=3^{2}\times 7^{1}}

Dado que el programa FRACTRAN es simplemente una lista de fracciones, estas instrucciones de prueba, decremento e incremento son las únicas permitidas en el lenguaje FRACTRAN. Además, se aplican las siguientes restricciones:

  • Cada vez que se ejecuta una instrucción, las variables que se están evaluando también se decrementan.
  • Una misma variable no puede ser incrementada y decrementada simultáneamente en una sola instrucción (de lo contrario, la fracción que representa dicha instrucción no estaría en su mínima expresión ). Por lo tanto, cada instrucción FRACTRAN consume variables a medida que las evalúa.
  • No es posible que una instrucción FRACTRAN compruebe directamente si una variable es 0 (sin embargo, se puede implementar una comprobación indirecta creando una instrucción predeterminada que se coloque después de otras instrucciones que comprueben una variable en particular).

Creación de programas sencillos

Suma

El programa FRACTRAN más simple es una sola instrucción como por ejemplo:

(32){\displaystyle \left({\frac {3}{2}}\right)}

Este programa se puede representar como un algoritmo (muy simple) de la siguiente manera:

Dado un ingreso inicial de la forma2a3b{\displaystyle 2^{a}3^{b}}Este programa calculará la secuencia2a−13b+1{\displaystyle 2^{a-1}3^{b+1}},2a−23b+2{\displaystyle 2^{a-2}3^{b+2}}, etc., hasta que finalmente, despuésa{\displaystyle a}pasos, no quedan factores de 2 y el producto con32{\displaystyle {\frac {3}{2}}}ya no produce un número entero; el programa se detiene entonces con una salida final de3a+b{\displaystyle 3^{a+b}}Por lo tanto, suma dos números enteros.

Multiplicación

Podemos crear un "multiplicador" mediante un "bucle" a través del "sumador". Para ello, necesitamos introducir estados en nuestro algoritmo. Este algoritmo tomará un número2a3b{\displaystyle 2^{a}3^{b}}y producir5ab{\displaystyle 5^{ab}}:

El estado B es un bucle que añadev3{\displaystyle v_{3}}av5{\displaystyle v_{5}}y también se muevev3{\displaystyle v_{3}}av7{\displaystyle v_{7}}y el estado A es un bucle de control externo que repite el bucle en el estado B.v2{\displaystyle v_{2}}veces. El estado A también restablece el valor dev3{\displaystyle v_{3}}dev7{\displaystyle v_{7}}una vez que el bucle en el estado B se haya completado.

Podemos implementar estados utilizando nuevas variables como indicadores de estado. Los indicadores de estado para el estado B serán:v11{\displaystyle v_{11}}yv13{\displaystyle v_{13}}. Tenga en cuenta que requerimos dos indicadores de control de estado para un bucle; un indicador primario (v11{\displaystyle v_{11}}) y una bandera secundaria (v13{\displaystyle v_{13}}Dado que cada indicador se consume cada vez que se prueba, necesitamos un indicador secundario que indique "continuar en el estado actual"; este indicador secundario se reemplaza por el indicador principal en la siguiente instrucción y el bucle continúa.

Al agregar los indicadores de estado e instrucciones de FRACTRAN a la tabla del algoritmo de multiplicación , tenemos:

Cuando escribimos las instrucciones FRACTRAN, debemos colocar las instrucciones del estado A al final, porque el estado A no tiene indicadores de estado; es el estado predeterminado si no se establecen indicadores de estado. Por lo tanto, como programa FRACTRAN, el multiplicador queda así:

(45533,1113,111,37,112,13){\displaystyle \left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)}

Con la entrada 2 a 3 b este programa produce la salida 5 ab . [ nota 2 ]

El programa FRACTRAN anterior, que calcula 3 veces 2 (de modo que su entrada es23×32=72{\displaystyle 2^{3}\times 3^{2}=72}y su resultado debería ser56{\displaystyle 5^{6}}porque 3 por 2 es igual a 6.

Resta y división

De manera similar, podemos crear un "restador" FRACTRAN, y las restas repetidas nos permiten crear un algoritmo de "cociente y resto" como sigue:

Al escribir el programa FRACTRAN, tenemos:

(9166,1113,133,8511,57119,1719,1117,13){\displaystyle \left({\frac {91}{66}},{\frac {11}{13}},{\frac {1}{33}},{\frac {85}{11}},{\frac {57}{119}},{\frac {17}{19}},{\frac {11}{17}},{\frac {1}{3}}\right)}

y la entrada 2 n 3 d 11 produce la salida 5 q 7 r donde n = qd + r y 0 ≤ r < d .

El algoritmo principal de Conway

El algoritmo generador de primos de Conway descrito anteriormente es esencialmente un algoritmo de cociente y resto dentro de dos bucles. Dada una entrada de la forma2norte7metro{\displaystyle 2^{n}7^{m}}donde 0 ≤ m < n , el algoritmo intenta dividir n + 1 por cada número desde n hasta 1, hasta encontrar el mayor número k que sea divisor de n + 1. Luego devuelve 2 n + 1 7 k - 1 y repite el proceso. La única vez que la secuencia de números de estado generada por el algoritmo produce una potencia de 2 es cuando k es 1 (de modo que el exponente de 7 es 0), lo cual solo ocurre si el exponente de 2 es un número primo. Una explicación paso a paso del algoritmo de Conway se puede encontrar en Havil (2007).

Para este programa, llegar al número primo 2, 3, 5, 7... requiere respectivamente 19, 69, 281, 710,... pasos (secuencia A007547 en el OEIS ) .

También existe una variante del programa de Conway, [ 1 ] que difiere de la versión anterior en dos fracciones: (1791,7885,1951,2338,2933,7729,9523,7719,117,1113,1311,1514,152,551){\displaystyle \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}{14}},{\frac {15}{2}},{\frac {55}{1}}\right)}

Esta variante es un poco más rápida: llegar a 2, 3, 5, 7... le lleva 19, 69, 280, 707... pasos (secuencia A007546 en el OEIS ) . Una sola iteración de este programa, que comprueba si un número N es primo, requiere la siguiente cantidad de pasos: norte−1+(6norte+2)(norte−b)+2∑d=bnorte−1⌊norted⌋,{\displaystyle N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor ,} dóndeb<norte{\displaystyle b<N}es el mayor divisor entero de N y⌊incógnita⌋{\displaystyle \lfloor x\rfloor }es la función piso . [ 2 ]

En 1999, Devin Kilminster demostró un programa más corto de diez instrucciones: [ 3 ](73,9998,1349,3935,3691,10143,4913,711,12,911).{\displaystyle \left({\frac {7}{3}},{\frac {99}{98}},{\frac {13}{49}},{\frac {39}{35}},{\frac {36}{91}},{\frac {10}{143}},{\frac {49}{13}},{\frac {7}{11}},{\frac {1}{2}},{\frac {91}{1}}\right).} Para una entrada inicial n = 10, se generan números primos sucesivos mediante potencias de 10 subsiguientes.

Otros ejemplos

El siguiente programa FRACTRAN:

(3⋅1122⋅5,511,132⋅5,15,23,2⋅57,72){\displaystyle \left({\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}},{\frac {13}{2\cdot 5}},{\frac {1}{5}},{\frac {2}{3}},{\frac {2\cdot 5}{7}},{\frac {7}{2}}\right)}

Calcula el peso de Hamming H( a ) de la expansión binaria de a, es decir, el número de 1s en la expansión binaria de a . [ 4 ] Dado un valor de entrada de 2a , su salida es 13H ( a ) . El programa se puede analizar de la siguiente manera:

Notas

  1. ↑ La numeración de Gödel no se puede utilizar directamente para enteros negativos, números de punto flotante o cadenas de texto, aunque se podrían adoptar convenciones para representar estos tipos de datos indirectamente. Las extensiones propuestas para FRACTRAN incluyen FRACTRAN++ y Bag .
  2. ↑ En la página de Esolang FRACTRAN se describe un algoritmo multiplicador similar .

Véase también

Referencias

  1. ↑ Guy 1983 , pág. 26 ; Conway y Guy 1996 , pág. 147  
  2. ↑ Guy 1983 , pág. 33 
  3. ↑ Havil 2007 , pág. 176 
  4. ↑ John Baez, Rompecabezas n.° 4 , Elcafé de las n categorías
  • Guy, Richard K. (1983). "La máquina productora de números primos de Conway" . Mathematics Magazine . 56 (1). Taylor & Francis : 26–33 . doi : 10.1080/0025570X.1983.11977011 .
  • Conway, John H. (1987). «FRACTRAN: Un lenguaje de programación universal y sencillo para la aritmética». Problemas abiertos en comunicación y computación . Springer-Verlag New York, Inc. pp. 4–26 . doi : 10.1007/978-1-4612-4808-8_2 . ISBN  978-1-4612-9162-6.
  • Conway, John H.; Guy, Richard K. (1996). El libro de los números . Springer-Verlag New York, Inc. ISBN 0-387-97993-X.
  • Havil, Julian (2007). ¡Desconcertado! Princeton University Press. ISBN 978-0-691-12056-0.
  • Roberts, Siobhan (2015). «Criterios de virtud». Genius At Play - The Curious Mind of John Horton Conway . Bloomsbury. pp. 115–119 . ISBN  978-1-62040-593-2.
  • Conferencia de John Conway: "Fractran: Un lenguaje lógico ridículo"
  • "Patología de los números primos: Fractran"
  • Weisstein, Eric W. "FRACTRAN" . MathWorld .
  • Patología de los números primos
  • FRACTRAN - (wiki de Esolang)
  • Implementación en Ruby y programas de ejemplo
  • Problema 308 del Proyecto Euler
  • "Desarrollar Fizzbuzz en Fractran desde la base"
  • Chris Lomont, "Un intérprete universal de FRACTRAN en FRACTRAN"