Determinar si un idioma se está completando es muy importante al diseñar un idioma. Para empezar, es una tarea bastante difícil para muchos lenguajes de programación esotéricos, pero vamos a mejorarla. Creemos algunos lenguajes de programación que son tan difíciles de probar Turing Complete que incluso los mejores matemáticos del mundo no podrán probarlos de ninguna manera. Su tarea es idear e implementar un lenguaje cuya integridad de Turing se base en un importante problema no resuelto en matemáticas .
Reglas
El problema que elija debe haberse planteado al menos hace 10 años y no debe haber sido resuelto, a partir de la publicación de esta pregunta. Puede ser cualquier conjetura demostrable en matemáticas, no solo una de las que figuran en la página de Wikipedia .
Debe proporcionar una especificación del idioma y una implementación en un idioma existente.
El lenguaje de programación debe ser Turing completo si y solo si la conjetura se cumple. (o si y solo si la conjetura no se cumple)
Debe incluir una prueba de por qué sería Turing completo o incompleto según la conjetura elegida. Puede asumir el acceso a la memoria ilimitada al ejecutar el intérprete o el programa compilado.
Dado que estamos interesados en Turing Completeness I / O no es necesario, sin embargo, el objetivo es hacer el lenguaje más interesante para que pueda ayudar.
Este es un concurso de popularidad lo que la respuesta con más votos ganará.
Criterios de destino
¿Qué debe hacer una buena respuesta? Aquí hay algunas cosas a tener en cuenta al votar, pero no son técnicamente necesarias
No debería ser un simple parche de un idioma existente. Cambiar un idioma existente para que se ajuste a las especificaciones está bien, pero se desaconseja parchear una condición porque es aburrida. Como dijo ais523 en el Byte Nineteeth:
Prefiero hacer que los trucos de mis esolangs estén más integrados en el idioma
Debería ser interesante como lenguaje esotérico independiente.
fuente
Respuestas:
Legendre
Este lenguaje es solo Turing completo si y solo si la conjetura de Legendre es falsa, es decir, existe un número entero n> 0 tal que no hay números primos entre n ^ 2 y (n + 1) ^ 2. Este lenguaje se inspira en Underload, aunque en algunos aspectos es muy diferente.
Los programas en Legendre están formados por una serie de enteros positivos (0 está especialmente prohibido, porque esencialmente niega todo el propósito del lenguaje). Cada entero corresponde a un comando base en Legendre, o uno potencial definido por el usuario. El comando al que está asignado se basa en el número de primos entre su cuadrado y el siguiente entero (equivalente a la secuencia OEIS A014085 ).
Los comandos del lenguaje modifican una pila, que puede contener enteros positivos arbitrariamente grandes. Si la pila alguna vez contiene 0, el 0 se elimina inmediatamente. En detalle, los comandos son:
2 (número entero más pequeño que produce este comando: 1): inserte el siguiente número entero en el programa en la pila.
3 (entero productor más pequeño: 4): aparece el entero superior en la pila y ejecuta el comando asociado con él.
4 (el más pequeño: 6): resalta el entero superior. Si fue 1, incremente el número entero superior en la pila.
5 (10): intercambia los dos primeros elementos de la pila.
6 (15): disminuye el número entero superior en la pila. Si eso da como resultado 0, saque el 0 y deséchelo.
7 (16): Duplica el entero superior en la pila.
8 (25): Detiene la ejecución e imprime el contenido de la pila.
Este es el conjunto de instrucciones básicas, que no puede hacer nada interesante, y mucho menos bucle. Sin embargo, hay otro comando, al que solo se puede acceder si la conjetura de Legendre es falsa.
Si este comando es accesible de alguna manera, el lenguaje se convierte en Turing completo, ya que uno puede simular una máquina Minsky en él.
Cuando se ejecuta el comando 8 o se alcanza el final del programa, el programa termina y se imprime el carácter (Unicode) correspondiente a cada entero en la pila.
Programas de ejemplo
Este programa simple empuja el número 2, luego el 3 y finalmente un 10, antes de ejecutar un 4 (comando: 3), lo que hace que el 10 (comando: 5) aparezca y se ejecute, intercambiando el 2 y el 3.
Este programa demuestra el uso de la correspondencia indirecta de entero a comando. Primero, se empuja un 5, luego un 15 y un 1, usando tres formas diferentes de codificar el comando 2. Luego, el 1 aparece y, como resultado, el 15 se incrementa a 16 y finalmente se ejecuta. El programa termina con dos instancias del número 5 en la pila.
Este programa demuestra el uso del comando 0, usando? como un número de marcador de posición. El programa primero almacena '1 5' en la función 9, luego '15 31 'en 10, antes de ejecutar la función 9 (usando 24), que empuja 5 a la pila, y la disminuye repetidamente, hasta que llega a 0 y se elimina . Entonces, el programa se detiene.
Máquina Minsky
Para convertir una máquina Minsky a código Legendre, se debe usar el comando 0 . Debido a que este comando es inaccesible a menos que la conjetura de Legendre sea falsa, ¿he usado un marcador de posición? en lugar.
Tenga en cuenta que todos los nombres de línea de instrucciones de máquina de Minsky deben tener enteros con diferentes correspondencias A014085 entre sí y los comandos base, así como 24 (9) y 31 (10).
Inicializacion: x INC (A / B) y:UNA:
SI:
x DEC (A / B) yz:UNA:
SI:
x HALT:Para crear el programa final, agregue todas las partes (con x, y, z reemplazadas por sus contrapartes) y agregue un número entero para comenzar la primera instrucción en la cadena. Esto debería demostrar la integridad del lenguaje Turing en caso de que la conjetura de Legendre se demuestre falsa por contraejemplo.
Interprete
Este intérprete está escrito en Python (3) y ha sido probado en los tres ejemplos anteriores. ¿Usar las banderas -a / - allowZero para permitir? para ser utilizado, archivo -f / - para ejecutar código directamente desde un archivo y -s / - stackOut para generar la pila como una lista de Python. Si no se proporciona ningún archivo, el intérprete ingresa a una especie de modo REPL, que se utiliza mejor con --stackOut.
fuente
Unión cerrada
Este lenguaje de programación está Turing completo si la conjetura de Conjuntos cerrados de unión es incorrecta.
Controles
Lista de comandos:
x ++ Incremento x (INC)
x-- Decremento x (DEC)
j (x, y) Agregue el conjunto de instrucciones x si y es 0 al final de la cola de instrucciones
Todas las variables se inicializan como 0
Sintaxis
Los programas se escriben como un conjunto de conjuntos de comandos.
Comando1 Comando2 Comando3 ...
Comando1 Comando2 ...
...
Para determinar si el programa está cerrado por unión, cada conjunto solo tiene en cuenta la lista de comandos diferentes que están en el conjunto
j (x, y)! = J (a, b)
+ (x)! = + (Y)
Si aparece algún tipo de comando (+, -, j) en al menos la mitad de los conjuntos, no hace nada.
Los programas pueden finalizar si no hay instrucciones al final de la cola de instrucciones
Se pueden lograr bucles infinitos, incluido el bucle vacío, usando j (x, y)
Interprete
Mostrar fragmento de código
Integridad de Turing
Si los tres comandos, j (x, y), incrementan, disminuyen, los comandos están disponibles, por lo que se puede simular una máquina Minsky.
Cualquier conjunto con solo j (x, y) que se alcanza usando j (x, y) es HALT
x ++ es INC
x-- es DEC
j (x, y) es JZ
Si la conjetura de conjuntos cerrados de unión es correcta, al menos uno de los tres comandos siempre estará deshabilitado, por lo que es imposible que este lenguaje se complete.
fuente
Fermat primos
El lenguaje funciona en dos cintas potencialmente infinitas, donde cada ubicación de la cinta puede almacenar un número entero arbitrario. Ambas cintas se rellenan
-1
al inicio. También hay dos cabezales de cinta que comienzan en la posición 0 en ambas cintas.El intérprete primero leerá la entrada y almacenará los valores en la primera cinta (de datos), comenzando en la posición 0.
Luego leerá el programa suministrado. Por cada número que encuentre, primero verificará si el valor es un primo de Fermat o no. En caso afirmativo, escribirá en la segunda cinta (instrucción) que Fermat prime es, de lo contrario, escribirá
-1
en la cinta de instrucciones.Luego verifique el valor en el puntero de instrucción y realice una de las siguientes acciones:
-1
o menos: salga del programa0
: Mueva la posición de la cinta de datos uno a la izquierda. Mueva la cinta de instrucciones posición uno a la derecha1
: Mueva la posición de la cinta de datos una a la derecha. Mueva la cinta de instrucciones posición uno a la derecha2
: Aumente el valor en la posición de la cinta de datos. Mueva la cinta de instrucciones posición uno a la derecha3
: Disminuya el valor en la posición de la cinta de datos. Mueva la cinta de instrucciones posición uno a la derecha4
: Si el valor en la posición actual de la cinta de datos es cero, mueva la cinta de instrucciones hacia la derecha, hasta que alcance un valor coincidente5
(o mayor) en la cinta de instrucciones, o algo más pequeño que0
. Si es un5
(o más grande), mueva el puntero de instrucción hacia la derecha una vez más, si es más pequeño que0
luego salga del programa. Si el valor de la posición actual de la cinta de datos no es cero, simplemente mueva la cinta de instrucciones una a la derecha5
o más: mueva el puntero de instrucciones hacia la izquierda, hasta que alcance el4
valor correspondiente , o encuentre algo menor que0
. En el caso de este último, salga del programa.(al hacer coincidir
5
(o más) y4
valores significa que mientras busca el valor adecuado en la cinta de instrucciones cada vez que encuentra el mismo valor que el comando inicial (ya sea5
(o más) o4
), tendrá que omitir el número apropiado del otro valor (4
o5
(o más) respectivamente) en la búsqueda)Bucle, hasta que las instrucciones indiquen que debe salir del programa.
Cuando el programa sale, envíe los valores en la cinta de datos desde la posición
0
hasta la primera posición de la cinta que contiene un-1
valor.Prueba
Tenga en cuenta que el lenguaje se asigna esencialmente a un intérprete Brainfuck sin IO, donde
F_5
se requiere poder hacer cualquier tipo de bucles adecuados.Sin embargo, según la conjetura del primer Fermat, solo hay 5 primos Fermat (
F_0
-F_4
). SiF_5
existe, el lenguaje es Turing completo, ya que sabemos que Brainfuck es Turing completo. Sin embargo, sinF_5
usted no podrá hacer bifurcaciones ni bucles, esencialmente bloqueándolo en programas muy simples.Implementación
(probado con ruby 2.3.1)
Ejemplos:
Esto escribirá
H
(abreviaturaHello World!
) en la pantalla con una nueva línea:Guarde como
example.fermat
y ejecútelo así (nota: siempre necesita tener una entrada):El siguiente ejemplo hará un cifrado simple de estilo César al incrementar cada valor de la entrada en uno. Obviamente tiene que reemplazar
?
con el quinto Fermat Prime:Puede probar que funciona al habilitar el modo trampa y usarlo
2 4 1 2 5 3
como código fuente:fuente
5
. Espero que tengan un buen teclado.Golondrinas con coco v2
Como la versión anterior tenía errores que la hicieron inválida para este concurso, y no quiero que los votos a favor del recuento de versiones anteriores para esta versión que sea significativamente diferente, esta versión se envíe como una nueva publicación.
Este lenguaje no está completo en Turing si la Conjetura de Collatz puede probarse para todos los enteros positivos. De lo contrario, el lenguaje es Turing completo.
Este lenguaje se basó en Cardinal .
Primero, el contVal del programa se calcula usando la fórmula
contVal = sum (sum (valores ASCII de la fila) * 2 ^ (fila número-1))
A continuación, se crean 2 Golondrinas en direcciones opuestas en cada A o E y todas las instrucciones de giro condicionales están configuradas para esperar la inicialización.
Las golondrinas creadas en una E se dirigen hacia la izquierda / derecha y las golondrinas creadas en una A se dirigen hacia arriba / abajo.
Finalmente, el código realizará pasos hasta que se hayan eliminado todos los punteros o se haya reducido contVal a uno.
En cada paso, si contVal% 2 == 0 se dividirá entre 2; de lo contrario, se multiplicará por tres y se incrementará por uno.
Comandos:
0: establezca el valor en 0
+: incremente el valor en 1
>: cambie la dirección hacia la derecha
v: cambie la dirección hacia abajo
<: cambie la dirección hacia la izquierda
^: cambie la dirección hacia arriba
R: Los punteros posteriores después del primer puntero se comparan con el valor del primer puntero Si es igual, siga recto, de lo contrario gire a la derecha.
L: Los punteros posteriores después del primer puntero se comparan con el valor del primer puntero. Si es igual, siga recto, de lo contrario gire a la izquierda.
E: Duplique el puntero pero vaya en las direcciones izquierda y derecha
A: ¿Duplique el puntero pero vaya en las direcciones hacia arriba y hacia abajo
? : Elimine el puntero si el valor es 0
Mostrar fragmento de código
Explicación:
Si la Conjetura de Collatz puede probarse para todos los enteros positivos, la duración de cualquier programa ejecutado en este lenguaje es finita, ya que contVal siempre convergerá a 1, terminando así el programa.
De lo contrario, simplemente necesito demostrar que este lenguaje puede implementar las siguientes funciones
Incremento: que está representado por +
Constante 0: que está representado por 0
Acceso variable: las variables se almacenan como punteros a medida que viajan
Concatenación de declaraciones: al cambiar la distancia recorrida a las operaciones, el orden en que se realizan las operaciones se puede cambiar
Para el bucle: En este idioma
actuará como un bucle for> contar hasta 1 (podría agregarse más código al bucle)
Del mismo modo, el código
Actuará como un do hasta que sea igual al valor condicional establecido en R loop.
fuente
contVal
en cada paso (y, por lo tanto, si la conjetura es verdadera, no hay bucles infinitos), pero no veo que se indique explícitamente en ninguna parte de la respuesta. ??Perfección / Imperfección
Menos mal, eso fue divertido.
La perfección / imperfección solo se completa si hay infinitos números perfectos. Si las hay, se llama Perfección, y si no las hay, se llama Imperfección. Hasta que se resuelva este misterio, tiene ambos nombres.
Un número perfecto es un número cuyos divisores suman el número, entonces seis es un número perfecto porque
1+2+3=6
.La perfección / imperfección tiene las siguientes funciones:
La perfección / imperfección se basa en la pila, con una pila de índice cero.
Comandos:
p(x, y)
: empuja x a la pila en la posición y.z(x, y)
: empuja x a la pila en la posición y, se deshace de lo que estaba previamente en la posiciónr(x)
: elimina el elemento x de la pilak(x)
: devuelve el elemento xth en la pilaa(x, y)
: agrega x e y. Cuando se usa con cadenas, las pone en orden xy.s(x, y)
: resta y de x. con cadenas, elimina la última len (y) de xm(x, y)
: multiplica x e y. Si se usa con cadenas, multiplica x veces len y.d(x, y)
: divide x por yo(x)
: imprime xi(x, y)
: si x se evalúa como verdadero, entonces ejecuta la función yn()
: devuelve el contador en el que se invoca el bloque de código.q()
: devuelve la longitud de la pilat()
: entrada del usuarioe(x, y)
: Si x es un número entero, si x e y tienen el mismo valor, entonces devuelve 1. si y es una cadena, entonces obtiene la longitud de y. si x es una cadena, convierte y en una cadena y comprueba si son iguales, y si lo son, devuelve 1. De lo contrario, devuelve 0.l(x, y)
: si x es mayor que y, entonces devuelve 1. Si hay una cadena, entonces usa la longitud de la cadena.b()
: detiene el programa.c(x, y)
: ejecuta x, luego y.Para obtener el equivalente de un Python
and
, multiplique los dos valores juntos. Paraor
, agregue los valores y paranot
, reste el valor de 1. Esto solo funciona si el valor es 1 o 0, lo que se puede lograr dividiendo el número por sí mismo.Tipos de datos: enteros y cadenas. Las cadenas se denotan por
''
, y todos los números no enteros se redondean.Sintaxis:
El código consta de funciones anidadas dentro de diez
{}
s. Por ejemplo, un programa que llegaría a los insumos y los imprime añaden sería:{o(a(t(), t()))}
. En el fondo del programa hay un contador que comienza en 0 y progresa en 1 cada vez que ejecuta un bloque de código. El primer bloque de código se ejecuta en0
, y así sucesivamente. Una vez que se ejecutan los diez bloques de código, el sexto se ejecuta cada vez que el contador alcanza un número perfecto. No necesita tener los diez bloques de código para que el programa funcione, pero necesita 7 si desea hacer un bucle. Para entender mejor cómo funciona este lenguaje, ejecute el siguiente programa, que imprime el contador cada vez que el contador llegue a un número perfecto:{}{}{}{}{}{}{o(n())}
.El intérprete se puede encontrar aquí: repl.it/GL7S/37 . Seleccione 1 y escriba su código en la terminal, o pegue su código en la
code.perfect
pestaña y seleccione 2 cuando ejecute. Tendrá sentido cuando lo intentes.Prueba de integridad de Turing / falta de integridad de Turing.
De acuerdo con este artículo de intercambio de pila de ingeniería de software , un Turing completo debe poder tener una forma de repetición condicional de salto y tener una forma de leer o escribir memoria. Puede leer / escribir memoria en forma de pila, y puede hacer un bucle debido al hecho de que el sexto bloque de código se ejecuta cada vez que el contador alcanza un número perfecto. Si hay un número infinito de números perfectos, puede repetirse indefinidamente y está completando Turing, y de lo contrario no lo está.
Intérprete de etiqueta cíclica bit a bit que toma 5 caracteres, 1 o 0, como entrada:
Se puede expandir para tomar cualquier número de caracteres como entrada. ¡Podría tomar una entrada infinita, pero solo si hay números perfectos infinitos!
fuente
Suelas
Este lenguaje de programación está Turing completo si la conjetura de Scholz es verdadera.
Escribí este lenguaje porque @SztupY decía que no habría ningún resultado que se basara en que la conjetura sea cierta para que Turing sea completa
Lista de comandos
Con estos comandos, este lenguaje puede simular una máquina Minsky
Interprete
Recomiendo no ejecutar esto. Utiliza un método extraordinariamente lento para verificar la cadena de adición.
Mostrar fragmento de código
Integridad de Turing
El lenguaje usa un contador para la cantidad de comandos ejecutados que verifica contra la conjetura de Scholz para modificar la integridad del lenguaje.
Si la conjetura de Scholz es cierta, este programa funciona exactamente como una máquina Minsky normal con
Incremento
Decremento
Salto si Cero
Detener
Sin embargo, si la conjetura de Scholz es falsa, el contador eventualmente alcanzará un valor para el cual la conjetura de Scholz no es verdadera. Como el lenguaje ha sido diseñado para salir al llegar a un número cuya conjetura de Scholz es falsa, el programa se cerrará cada vez que ejecute tantos comandos. Por lo tanto, todos los programas tendrán una duración limitada. Como esto no está de acuerdo con los requisitos para que el idioma se complete en Turing,
el lenguaje no estaría completo si la conjetura de Scholz fuera falsa
fuente
Prometido
Github prometido .
El archivo Léame y las especificaciones están en el github, en "README.txt".
En general, un programa de compromiso se compone de pares de líneas, cuyas longitudes son pares primos gemelos distintos o pares de compromiso (no pueden ocurrir duplicados). El programa se ejecuta buscando "subconjuntos flexibles" de la primera línea en el par dentro de la segunda línea. El número de tales subconjuntos, combinado con la distancia levenshtein entre la segunda línea original y la segunda línea sin los subconjuntos flexibles, determina el comando a ejecutar.
Extraeré la prueba de esta publicación:
fuente
b
. Esto interpreta un programa BF, que se coloca después de él, comob+++++.
. Sin embargo, el tamaño del programa está limitado a 10 caracteres. Si bien puede interpretar BF, no puede calcular todos los programas que puede hacer una máquina Turing.Paridad amistosa
Este lenguaje se basa en si hay números amigables con paridad opuesta .
Comandos
Flujo de control
El programa realiza ciclos repetidos de izquierda a derecha antes de volver al inicio. Si encuentra una "j", verifica el valor para determinar si debe cambiar las filas. Si el número es un número amigable con paridad opuesta a su coincidencia, baja una fila (regresando hacia arriba), de lo contrario, si el número es un número amigable, sube una fila si aún no está en la fila superior.
El programa solo puede finalizar si el programa alcanza una x en cualquier fila fuera de la fila superior.
Integridad de Turing
Este programa se puede utilizar para simular una máquina Minsky suponiendo que hay un par de números amigables con paridad opuesta.
j, {y} se pueden usar para simular JZ (r, x) aunque verificaría números amigables en lugar de cero.
+ es INC (r)
- es DEC (r)
x es HALT
Si no puede salir de la primera fila, los comandos x y} no hacen nada. Esto hace que el programa no pueda ingresar a un estado HALT a menos que sea un programa vacío. Por lo tanto, bajo la descripción de que la integridad de Turing requiere un estado HALT , el lenguaje sería Turing incompleto.
Interprete
Mostrar fragmento de código
fuente
Nueva línea
Descargo de responsabilidad: es un poco desordenado y bastante simple. Este es el primer idioma que he escrito y la conjetura es la única que he entendido. Sé que otro usuario tuvo una respuesta más larga con la misma, pero decidí escribir esto de todos modos.
Para escribir en Newline debes tener mucho tiempo y nuevas líneas (
\n
). Esto funciona a partir de la conjetura de Legendre siendo cierta. Cada operador debe caer en un número en la conjetura de Legendre que comencemos con n = 1. Cada vez que tenga un operador, tome la cantidad de \ n's y la conecte a la Conjetura de Legendre y obtenga el rango que corresponde a la siguiente cantidad de \ las n deben caer. Entonces, para comenzar, debe\n\n
pasar a un operador y\n
luego a otro operador, estamos en 3 líneas nuevas. Ahora, el siguiente es el 5, por lo que debe agregar\n\n
y en el operador asegurándose de que la última línea del operador tenga la cantidad correcta de líneas nuevas que está en una cantidad principal que cae en la conjetura de Legendre que comenzamos.Los números (la matriz) son como las variables. Cada vez que se ejecuta un operador (que usa números) se incrementa.
Mientras tengamos números primos ilimitados que sigan las reglas, este lenguaje tendrá una cinta no finita.
Máquina Minsky
Cómo funciona:
Pruébalo en KhanAcademy .
fuente
Taggis
Taggis es un lenguaje basado en sistemas de etiquetas .
La integridad de Turing de Taggis se basa en la conjetura de Collatz
Sintaxis
La sintaxis de un programa Taggis es simplemente tres cadenas (reglas de producción) que consisten enteramente en las letras a, byc, separadas por espacios.
Ejecución
El único estado del programa de Taggis es una cadena que consta de los mismos tres caracteres.
Taggis implementa un sistema de etiquetas TS (3, 2), donde en cada paso se eliminan las 2 primeras letras de la "etiqueta" actual, y la primera letra que estaba en esa porción eliminada obtiene su regla de producción correspondiente añadida al final de la cuerda.
Por ejemplo, el programa Taggis
bc a aaa
implementa el problema 3n + 1, donde las iteraciones están representadas por un número correspondiente dea
sy el paso 3n + 1 se reemplaza con (3n + 1) / 2 [1], lo que lleva a la salida del programa:Integridad de Turing
Por supuesto, este sistema simple puede parecer demasiado simple para emular la integridad de Turing, pero resulta que cualquier máquina de Turing con 2 símbolos (una clase que incluye máquinas universales) puede convertirse en un sistema de etiquetas con 2 caracteres eliminados de la cabeza, y reglas de producción de 32 * m, donde
m
es el número de estados en la máquina Turing.La máquina Turing universal más pequeña conocida con solo 2 símbolos utiliza 18 estados y, por lo tanto, el sistema de etiquetas correspondiente contiene 576 reglas de producción [2].
Sin embargo, la clase computacional del conjunto de todos los sistemas de etiquetas con 3 producciones y 2 símbolos eliminados está vinculada a la Conjetura de Collatz [2]. Si se demuestra que la Conjetura de Collatz es falsa, entonces Taggis es Turing completo. De lo contrario, se basa en OTRO problema no resuelto en matemáticas, encontrando una máquina de Turing más pequeña que
que es equivalente a la función Collatz original ya que 3n + 1 de un impar
n
siempre será par y, por lo tanto, la división se puede aplicar automáticamenteSistemas de etiquetas y funciones tipo Collatz, Liesbeth De Mol ,
fuente