FRACTRAN es un lenguaje de programación esotérico completo de Turing inventado por el matemático John Conway . Un programa FRACTRAN es una lista ordenada de fracciones positivas junto con un número entero positivo inicial n . El programa se ejecuta actualizando el entero n de la siguiente manera:
- para la primera fracción f en la lista para la cual nf es un número entero, reemplace n por nf
- repita esta regla hasta que ninguna fracción en la lista produzca un número entero cuando se multiplique por n , luego deténgase.
Conway 1987 da la siguiente fórmula para números primos en FRACTRAN: [nota 1]
Comenzando con n = 2, este programa FRACTRAN genera la siguiente secuencia de números enteros:
Después de 2, esta secuencia contiene las siguientes potencias de 2:
que son los poderes primarios de 2.
Comprensión de un programa FRACTRAN
Un programa FRACTRAN puede verse como un tipo de máquina de registro donde los registros se almacenan en exponentes primos en el argumento n .
Usando la numeración de Gödel , un número entero positivo n puede codificar un número arbitrario de variables enteras positivas arbitrariamente grandes. [nota 2] 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
representa un estado de registro en el que una variable (que llamaremos v2) tiene el valor 2 y otras dos variables (v3 y v5) tienen el valor 1. Todas las demás variables tienen 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:
pruebas v2 y v5. Si y , luego resta 2 de v2 y 1 de v5 y suma 1 a v3 y 1 a v7. Por ejemplo:
Dado que el programa FRACTRAN es solo una lista de fracciones, estas instrucciones de prueba-decremento-incremento son las únicas instrucciones permitidas 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 disminuyen.
- La misma variable no se puede disminuir ni aumentar en una sola instrucción (de lo contrario, la fracción que representa esa instrucción no estaría en sus términos más bajos ). Por lo tanto, cada instrucción FRACTRAN consume variables mientras las prueba.
- No es posible que una instrucción FRACTRAN pruebe directamente si una variable es 0 (sin embargo, se puede implementar una prueba indirecta creando una instrucción predeterminada que se coloca después de otras instrucciones que prueban una variable en particular).
Creando programas simples
Adición
El programa FRACTRAN más simple es una sola instrucción como
Este programa se puede representar como un algoritmo (muy simple) de la siguiente manera:
Instrucción FRACTRAN | Condición | Acción |
---|---|---|
v2> 0 | Restar 1 de v2 Sumar 1 a v3 | |
v2 = 0 | Detener |
Dada una entrada inicial del formulario , este programa calculará la secuencia , , etc., hasta que finalmente, después pasos, no quedan factores de 2 y el producto con ya no produce un número entero; la máquina luego se detiene con una salida final de. Por lo tanto, suma dos números enteros.
Multiplicación
Podemos crear un "multiplicador" haciendo un "bucle" a través del "sumador". Para hacer esto, necesitamos introducir estados en nuestro algoritmo. Este algoritmo tomará un número y producir :
Estado actual | Condición | Acción | Estado siguiente |
---|---|---|---|
A | v7> 0 | Restar 1 de v7 Sumar 1 a v3 | A |
v7 = 0 y v2> 0 | Restar 1 de v2 | B | |
v7 = 0 y v2 = 0 y v3> 0 | Restar 1 de v3 | A | |
v7 = 0 y v2 = 0 y v3 = 0 | Detener | ||
B | v3> 0 | Restar 1 de v3 Sumar 1 a v5 Sumar 1 a v7 | B |
v3 = 0 | Ninguno | A |
El estado B es un bucle que agrega v3 a v5 y también mueve v3 a v7, y el estado A es un bucle de control externo que repite el bucle en el estado B v2 veces. El estado A también restaura el valor de v3 de v7 después de que se haya completado el ciclo en el estado B.
Podemos implementar estados usando nuevas variables como indicadores de estado. Los indicadores de estado para el estado B serán v11 y v13. Tenga en cuenta que requerimos dos indicadores de control de estado para un bucle; una bandera primaria (v11) y una bandera secundaria (v13). Debido a que cada indicador se consume cada vez que se prueba, necesitamos un indicador secundario que diga "continuar en el estado actual"; este indicador secundario se cambia de nuevo al indicador principal en la siguiente instrucción, y el ciclo continúa.
Añadiendo los indicadores de estado e instrucciones de FRACTRAN a la tabla del algoritmo de multiplicación, tenemos:
Instrucción FRACTRAN | Estado actual | Indicadores de estado | Condición | Acción | Estado siguiente |
---|---|---|---|---|---|
A | Ninguno | v7> 0 | Restar 1 de v7 Sumar 1 a v3 | A | |
v7 = 0 y v2> 0 | Restar 1 de v2 | B | |||
v7 = 0 y v2 = 0 y v3> 0 | Restar 1 de v3 | A | |||
v7 = 0 y v2 = 0 y v3 = 0 | Detener | ||||
B | v11, v13 | v3> 0 | Restar 1 de v3 Sumar 1 a v5 Sumar 1 a v7 | B | |
v3 = 0 | Ninguno | A |
Cuando escribimos las instrucciones de FRACTRAN, debemos poner 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. Entonces, como programa FRACTRAN, el multiplicador se convierte en:
Con la entrada 2 a 3 b, este programa produce la salida 5 ab . [nota 3]
Resta y división
De manera similar, podemos crear un "restador" de FRACTRAN, y las restas repetidas nos permiten crear un algoritmo de "cociente y resto" de la siguiente manera:
Instrucción FRACTRAN | Estado actual | Indicadores de estado | Condición | Acción | Estado siguiente |
---|---|---|---|---|---|
A | v11, v13 | v2> 0 y v3> 0 | Restar 1 de v2 Restar 1 de v3 Sumar 1 a v7 | A | |
v2 = 0 y v3> 0 | Restar 1 de v3 | X | |||
v3 = 0 | Agregar 1 a v5 | B | |||
B | v17, v19 | v7> 0 | Restar 1 de v7 Sumar 1 a v3 | B | |
v7 = 0 | Ninguno | A | |||
X | v3> 0 | Restar 1 de v3 | X | ||
v3 = 0 | Detener |
Al escribir el programa FRACTRAN, tenemos:
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 de generación principal de Conway anterior es esencialmente un algoritmo de cociente y resto dentro de dos bucles. Dada la entrada del formulariodonde 0 ≤ m < n , el algoritmo intenta dividir n +1 por cada número desde n hasta 1, hasta que encuentra el número más grande k que es un divisor de n +1. Luego devuelve 2 n +1 7 k -1 y se repite. Las únicas veces 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 que solo ocurre si el exponente de 2 es un primo. Se puede encontrar una explicación paso a paso del algoritmo de Conway en Havil (2007).
Otros ejemplos
El siguiente programa FRACTRAN:
calcula el peso de Hamming H ( a ) de la expansión binaria de a, es decir, el número de unos en la expansión binaria de a . [1] Dada la entrada 2 a , su salida es 13 H ( a ) . El programa se puede analizar de la siguiente manera:
Instrucción FRACTRAN | Estado actual | Indicadores de estado | Condición | Acción | Estado siguiente |
---|---|---|---|---|---|
A | v5, v11 | v2> 1 | Restar 2 de v2 Sumar 1 a v3 | A | |
v2 = 1 | Restar 1 de v2 Sumar 1 a v13 | B | |||
v2 = 0 | Ninguno | B | |||
B | Ninguno | v3> 0 | Restar 1 de v3 Sumar 1 a v2 | B | |
v3 = 0 y v7> 0 | Restar 1 de v7 Sumar 1 a v2 | A | |||
v3 = 0 y v7 = 0 y v2> 0 | Restar 1 de v2 sumar 1 a v7 | B | |||
v2 = 0 y v3 = 0 y v7 = 0 | Detener |
Notas
- ^ En El libro de los números , John Conway y Richard Guy dieron una secuencia ligeramente diferente:
- ^ La numeración de Gödel no se puede usar directamente para números enteros negativos, números de coma 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 .
- ^ Un algoritmo multiplicador similar se describe en la página Esolang FRACTRAN .
Referencias
- ↑ John Baez, Puzzle # 4 , The n -Category Café
- Conway, John H. (1987). "FRACTRAN: Un sencillo lenguaje de programación universal para aritmética". Problemas abiertos en comunicación y computación . Springer-Verlag New York, Inc .: 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 Nueva York, Inc. ISBN 0-387-97993-X.
- Havil, Julian (2007). ¡Desconcertado! . Prensa de la Universidad de Princeton. ISBN 978-0-691-12056-0.
- Roberts, Siobhan (2015). "Criterios de virtud". Genius At Play - La mente curiosa de John Horton Conway . Bloomsbury. págs. 115-119. ISBN 978-1-62040-593-2.
Ver también
enlaces externos
- "Patología de números primos: Fractran"
- Weisstein, Eric W. "FRACTRAN" . MathWorld .
- Patología de números primos
- FRACTRAN - (Esolang wiki)
- 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"