Escribir un lenguaje de programación de integridad desconocida

91

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 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

Asistente de trigo
fuente
Esta conversación se ha movido al chat .
Dennis
13
En general, las respuestas aquí me parecen decepcionantes. Son prácticamente "Comience con un lenguaje completo de Turing, luego pruebe si la conjetura X es Verdadero / Falso y, de ser así, finalice o deshabilite una característica clave".
xnor
1
@xnor Estoy de acuerdo con usted, esperaba que esta recompensa provocara algunas respuestas más interesantes, pero parece que eso no va a suceder.
Wheat Wizard
2
Creo que uno de los problemas es que se ha demostrado que la mayoría de las conjeturas son verdaderas para un número infinito de valores, pero los contraejemplos también serían ciertos para un número infinito de valores. Como resultado, se vuelve casi imposible probar la integridad de Turing si es cierto.
fəˈnɛtɪk
1
Creo que el requisito de que la integridad de Turing esté vinculada uno a uno con una conjetura dada es un requisito bastante fuerte. Creo que sería fácil si probar o refutar la integridad de Turing decidiera dos problemas abiertos diferentes, respectivamente. (es decir, probar la integridad de Turing decide el problema abierto A y la refutación decide el problema abierto B).
PyRulez

Respuestas:

48

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.

  • 0 (desconocido): elimine todos los elementos de la pila y combínelos en una nueva función, que ejecutará todos los comandos comenzando en la parte inferior original de la pila y terminando en la parte superior, accesible como un comando cuyo "número de comando" es igual a al que corresponde el siguiente entero en la fuente del programa.

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

1 2 1 3 1 10 4

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.

1 5 3 15 2 1 6 7

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.

1 1 1 5 ? 24 1 15 1 31 ? 31 24 31

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:
1 1 1 1 ? 24
x INC (A / B) y:

UNA:

1 y 1 24 1 ? 1 6 1 1 16 1 24 ? x

SI:

1 y 1 24 1 ? 1 10 1 6 1 1 16 1 10 1 24 ? x
x DEC (A / B) yz:

UNA:

1 4 1 10 1 15 1 10 1 31 1 1 1 10 1 z 1 1 1 16 1 24 1 31 1 ? 1 24 1 15 1 y 1 6 16 1 24 16 1 ? 1 1 16 1 10 1 1 16 1 24 ? x

SI:

1 4 1 10 1 15 1 10 1 31 1 1 1 10 1 z 1 1 1 16 1 24 1 31 1 ? 1 24 1 15 1 10 1 y 1 6 16 1 24 16 1 ? 1 1 16 1 10 1 1 16 1 10 1 24 ? x
x HALT:
1 25 ? x

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.

import sys
import argparse
import io

class I_need_missing(dict): #used to avoid try/except statements. Essentially a dict
    def __missing__(self,key):
        return None 

def appropriate(integer,prev): #returns number of primes between the square of the integer given and the next

    return_value = 0

    if prev[integer]:
        return prev[integer],prev
    if integer == "?":
        return 0,prev
    for i in range(integer ** 2, (integer + 1) ** 2):
        t = False
        if i > 1:
            t = True
            for j in range(2,int(i ** 0.5)+1):
                t = i/j != round(i/j)
                if not t:
                    break
        return_value += t

    prev[integer] = return_value
    return return_value,prev

def run_command(commandseries,stack,functions,prev): #Runs the appropriate action for each command.

    command,prev = appropriate(commandseries.pop(0),prev)

    halt = False

    if command == 0: #store in given number
        functions[appropriate(commandseries.pop(0),prev)[0]] = stack
        stack = []

    elif command == 2:#push
        stack.append(commandseries.pop(0))

    elif command == 3:#execute top instruction
        commandseries.insert(0,stack.pop())

    elif command == 4:#pop, add 1 to new top if popped value was 1
        if stack.pop() == 1:
            stack[-1] += 1

    elif command == 5:#swap top two integers/?
        stack[-1],stack[-2] = stack[-2],stack[-1]

    elif command == 6:#subtract 1 from top of stack
        stack[-1] -= 1
        if stack[-1] == 0:
            stack.pop()

    elif command == 7:#duplicate top of stack
        stack.append(stack[-1])

    elif command == 8:#halt
        halt = True

    else:#run custom
        try:
            commandseries[0:0] = functions[command]
        except TypeError:
            print("Warning: unassigned function " + str(command) + " is unassigned", file = sys.stderr)

    return commandseries,stack,functions,prev,halt

def main(stack,functions,prev):
    #Parser for command line options
    parser = argparse.ArgumentParser(description = "Interpreter for the Legendre esoteric programming language.")
    parser.add_argument("-a","--allowZero", action = "store_true")
    parser.add_argument("-f","--file")
    parser.add_argument("-s","--stackOut", action = "store_true")

    args = parser.parse_args()
    allow_zero = bool(args.allowZero)

    #Program decoding starts
    pre = ""

    if not args.file:
        pre = input()
        if pre == "":
            return
    else:
        pre = open(args.file).read()

    mid = pre.split()
    final = []

    for i in mid:
        if i == "?" and allow_zero:
            final.append("?")
        elif i != 0 or allow_zero: #and allow_zero)
            final.append(int(i))

    halt = False

    #Functional programming at its best
    while final and not halt:
        final,stack,functions,prev,halt = run_command(final,stack,functions,prev)

    #Halting and output
    else:
        if args.stackOut:
            print(stack)
        else:
            for i in stack:
                print(i == "?" and "?" or chr(i),end = "")
            print("")
        if args.file or halt:
            return
        else:
            main(stack,functions,prev)


if __name__ == '__main__':
    main([],I_need_missing(),I_need_missing())
ivzem
fuente
14

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

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.

fəˈnɛtɪk
fuente
Lo que haría en lugar de tener 3 operadores es tener un número infinito de valores y tomar el módulo 4 de cada uno para obtener una de las tres operaciones más un no-op. Cuando el programa se inicia, verifica que la unión de los conjuntos esté cerrada y luego elimina cualquier elemento que esté en más de la mitad de los conjuntos. Luego repite esto hasta que no haya tal elemento. Si la conjetura es cierta, todos los programas son iguales que el programa vacío, sin embargo, si es falso, puede expresar todos los programas posibles (es por eso que se incluye el no-op).
Wheat Wizard
@WheatWizard La determinación de la unión cerrada por el intérprete considera que el mismo operador en diferentes variables es diferente. Se considera que x ++ es diferente de y ++. Como resultado, hay una infinidad de conjuntos diferentes que se pueden crear. Con un número infinito de conjuntos posibles, si ninguno de los tres tipos principales está en más de la mitad de los conjuntos, entonces está completo.
fəˈnɛtɪk
Es posible que una prueba de la conjetura de conjuntos cerrados de la Unión deje una conversión a uno de los tres operadores como completa, ya que podría ser posible dejar a todos los operadores diferentes en el programa, solo necesitaría 3 de un número infinito de valores para permanecer.
fəˈnɛtɪk
13

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 -1al 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á -1en 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 programa
  • 0: Mueva la posición de la cinta de datos uno a la izquierda. Mueva la cinta de instrucciones posición uno a la derecha
  • 1: Mueva la posición de la cinta de datos una a la derecha. Mueva la cinta de instrucciones posición uno a la derecha
  • 2: Aumente el valor en la posición de la cinta de datos. Mueva la cinta de instrucciones posición uno a la derecha
  • 3: Disminuya el valor en la posición de la cinta de datos. Mueva la cinta de instrucciones posición uno a la derecha
  • 4: 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 coincidente 5(o mayor) en la cinta de instrucciones, o algo más pequeño que 0. Si es un 5(o más grande), mueva el puntero de instrucción hacia la derecha una vez más, si es más pequeño que 0luego 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 derecha
  • 5o más: mueva el puntero de instrucciones hacia la izquierda, hasta que alcance el 4valor correspondiente , o encuentre algo menor que 0. En el caso de este último, salga del programa.

(al hacer coincidir 5(o más) y 4valores significa que mientras busca el valor adecuado en la cinta de instrucciones cada vez que encuentra el mismo valor que el comando inicial (ya sea 5(o más) o 4), tendrá que omitir el número apropiado del otro valor ( 4o 5(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 0hasta la primera posición de la cinta que contiene un -1valor.

Prueba

Tenga en cuenta que el lenguaje se asigna esencialmente a un intérprete Brainfuck sin IO, donde F_5se 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). Si F_5existe, el lenguaje es Turing completo, ya que sabemos que Brainfuck es Turing completo. Sin embargo, sin F_5usted no podrá hacer bifurcaciones ni bucles, esencialmente bloqueándolo en programas muy simples.

Implementación

(probado con ruby ​​2.3.1)

#!/usr/bin/env ruby
require 'prime'

CHEAT_MODE = false
DEBUG_MODE = false
NUM_CACHE = {}

def determine_number(n)
  return n.to_i if CHEAT_MODE
  n = n.to_i
  -1 if n<3

  return NUM_CACHE[n] if NUM_CACHE[n]

  i = 0

  loop do
    num = 2**(2**i) + 1
    if num == n && Prime.prime?(n)
      NUM_CACHE[n] = i
      break
    end
    if num > n
      NUM_CACHE[n] = -1
      break
    end
    i += 1
  end

  NUM_CACHE[n]
end

data_tape = Hash.new(-1)
instruction_tape = Hash.new(-1)

STDIN.read.each_char.with_index { |c,i| data_tape[i] = c.ord }
File.read(ARGV[0]).split.each.with_index do |n,i|
  instruction_tape[i] = determine_number(n)
end

data_pos = 0
instruction_pos = 0

while instruction_tape[instruction_pos] >= 0
  p data_tape, data_pos, instruction_tape, instruction_pos,'------------' if DEBUG_MODE

  case instruction_tape[instruction_pos]
  when 0 then data_pos -= 1; instruction_pos += 1
  when 1 then data_pos += 1; instruction_pos += 1
  when 2 then data_tape[data_pos] += 1; instruction_pos += 1
  when 3 then data_tape[data_pos] -= 1; instruction_pos += 1
  when 4 then
    if data_tape[data_pos] == 0
      count = 1
      instruction_pos += 1
      while count>0 && instruction_tape[instruction_pos] >= 0
        count += 1 if instruction_tape[instruction_pos] == 4
        count -= 1 if instruction_tape[instruction_pos] >= 5
        instruction_pos += 1
      end
      break if count != 0
    else
      instruction_pos += 1
    end
  else
    count = 1
    instruction_pos -= 1
    while count>0 && instruction_tape[instruction_pos] >= 0
      count += 1 if instruction_tape[instruction_pos] >= 5
      count -= 1 if instruction_tape[instruction_pos] == 4
      instruction_pos -= 1 if count>0
    end
    break if count != 0
  end
end

data_pos = 0

while data_tape[data_pos] >= 0
  print data_tape[data_pos].chr
  data_pos += 1
end

Ejemplos:

Esto escribirá H(abreviatura Hello World!) en la pantalla con una nueva línea:

17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17 17 17 17 17 17 17 17
17 17 17
5
17 17 17 17 17 17 17 17 17 17
17

Guarde como example.fermaty ejecútelo así (nota: siempre necesita tener una entrada):

$ echo -n '' | ./fermat.rb example.fermat

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:

17 65537 5 17 ? 257

Puede probar que funciona al habilitar el modo trampa y usarlo 2 4 1 2 5 3como código fuente:

$ echo 'Hello' | ./fermat.rb example2_cheat.fermat
SztupY
fuente
2
Lo siento por el pobre codificador que tiene que escribir el número primo correspondiente para llegar 5. Espero que tengan un buen teclado.
AdmBorkBork
2
@AdmBorkBork No te preocupes. Simplemente tiene más bits que el universo tiene partículas elementales.
fəˈnɛtɪk
@LliwTelracs en realidad eso no tiene sentido ya que la cantidad de partículas elementales en el universo es Aleph-null (omega) y de omega, comienza a no significar el tamaño real del número. (A menos que sea Aleph One: P)
Matthew Roh
1
@MatthewRoh Me había equivocado. Me refería al universo observable.
fəˈnɛtɪk
2
@MatthewRoh En realidad, ¡podría ser finito, infinito, incontable o incluso inconsistente con la teoría de conjuntos! Sin embargo, nunca lo sabremos :(
CalculatorFeline
10

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

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

E   > V
    ^+R
      +
      A

actuará como un bucle for> contar hasta 1 (podría agregarse más código al bucle)

Del mismo modo, el código

Rv
^<

Actuará como un do hasta que sea igual al valor condicional establecido en R loop.

fəˈnɛtɪk
fuente
Tú también me ganaste, iba a hacer algo con la conjetura del collatz. Buen trabajo, en la interesante toma de él. Iba a crear un idioma que solo pudiera almacenar números si convergían a 1.
Rohan Jhunjhunwala
Estoy confundido. ¿Dónde figura la función Collatz en esto? De una segunda lectura, creo que quiere decir que la función se aplica contValen 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. ??
DLosc
Lo siento, mientras lo hace, creo que accidentalmente
eliminé
10

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ón

r(x): elimina el elemento x de la pila

k(x): devuelve el elemento xth en la pila

a(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 x

m(x, y): multiplica x e y. Si se usa con cadenas, multiplica x veces len y.

d(x, y): divide x por y

o(x): imprime x

i(x, y): si x se evalúa como verdadero, entonces ejecuta la función y

n(): devuelve el contador en el que se invoca el bloque de código.

q(): devuelve la longitud de la pila

t(): entrada del usuario

e(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. Para or, 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 en 0, 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.perfectpestañ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:

{p(t(),0)}{(p(t(),0)}{p(t(),0)}{p(t(),0)}{p(t(),0)}{p(0,0)}{c(i(e(k(s(q(),k(0))),0),c(r(q()),i(l(k(0),0),z(s(k(0),1),0)))),i(e(k(s(q(),k(0))),1),c(z(a(k(0),1),0),i(e(k(q()),1),p(k(s(q(),k(0))),1)))))}

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!

Camarada SparklePony
fuente
1
Creo que solo podría estar creando un nuevo valor para hacer un bucle local, ya que no se comparte con la función.
fəˈnɛtɪk
3
Tal como está, no tiene una prueba de TC. El artículo de ingeniería de software al que se vincula ofrece una serie de requisitos generales, sin embargo, TC no es solo un montón de casillas para marcar. Deberá implementar un autómata TC (como una máquina Minsky) o mostrar que su idioma es indecidible.
Wheat Wizard
2
@WheatWizard Allí, agregué un intérprete de etiqueta cíclica Bitwise. Se puede modificar para tomar cualquier cantidad de caracteres como entrada. Posiblemente podría tomar caracteres infinitos como entrada, ¡pero solo si hay números perfectos infinitos!
Camarada SparklePony
2
"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". ¿Entonces el intérprete cuenta directamente los números perfectos? Siento que esto va en contra del espíritu del desafío. La especificación real del idioma no importa mucho, puede ser cualquier cosa Turing-complete más "solo se ejecuta por un paso solo cuando se alcanza un número perfecto".
xnor
10

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

+(x)      Increment x (INC)   
-(x)      Decrement x (DEC)  
j(x,y)    Jump to instruction x if y is 0 (JZ)  
x         End program (HALT) 

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.

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,

"La cinta no se puede fijar en longitud, ya que eso no se correspondería con la definición dada y limitaría seriamente el rango de cálculos que la máquina puede realizar a los de un autómata lineal limitado",

el lenguaje no estaría completo si la conjetura de Scholz fuera falsa

fəˈnɛtɪk
fuente
1
+1, ya que esto realmente dificulta el requisito de conjeturas en el idioma, en lugar de agregar algo extraño para matar el idioma si la conjetura es verdadera / falsa
Gryphon
No lo entiendo Los comandos que proporciona son exactamente los que necesita para simular una máquina Minsky, por lo que si eso es todo, su idioma es Turing completo, independientemente de la conjetura de Scholz. Debes estar perdiendo algo de tu explicación.
Nathaniel
@Nathaniel Uno de los requisitos para un lenguaje completo de Turing es que el idioma puede terminar en un ciclo infinito (problema de detención). Mi código cuenta mientras ejecuta instrucciones y si la conjetura de Scholz es falsa, el programa siempre se detendrá después de un número determinado de instrucciones.
fəˈnɛtɪk
Sí, pero se ha olvidado de explicar qué hace que se detenga si la conjetura de Scholz es falsa. Eche otro vistazo a su respuesta: no está allí en absoluto.
Nathaniel
@Nathaniel El programa literalmente funciona verificando cada número si funciona en la conjetura de scholz. Sale automáticamente cuando encuentra un número que no está de acuerdo con la conjetura.
fəˈnɛtɪk
9

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:

V. PROOF OF TURING COMPLETENESS

Now, no language can be Turing Complete with bounded program size. Therefore, if Betrothed
is Turing Complete, it must have unbounded program size. Since the lengths of the lines of
a Betrothed program must be twin prime pairs or betrothed pairs, and since both sequences
are unproven to be infinite or finite, Betrothed has unbounded program size if and only if
there are infintie betrothed pairs, there are infinite twin prime pairs, or both.

    Next: to prove that if Betrothed has an unbounded program size, then it is Turing
Complete. I will use the op-codes from the above table to demonstrate key factors of a
Turing Complete language; they are of the form  [index]<[ld]> .

  1. Conditional goto: 6<> 5<>, or if-popjump. This can be used to form a loop.
  2. Inequality to a constant K: 10<K> 
  3. Arbitrarily large variable space: you can use some separator constant C.

    With this, I have sufficient reason to believe that Betrothed is Turing Complete.
Conor O'Brien
fuente
44
"Ahora, ningún idioma puede ser Turing completo con un tamaño de programa acotado". Estoy confundido acerca de esta declaración ... Por un lado, es cierto que con un tamaño de programa acotado solo podemos escribir un número finito de programas diferentes, pero por otro lado, una prueba común de Turing Completeness es escribir un intérprete para un programa diferente Turing Lenguaje completo, que no necesita un tamaño de programa ilimitado en absoluto ...
Leo
1
Bueno, el programa pasado al intérprete no necesita ser puesto en el código del intérprete, debe ser entregado al intérprete como entrada
Leo
77
@León. Me gustaría decir que, con el fin de que el lenguaje sea TC, debe ser capaz de codificar el programa para ser pasado al intérprete (es decir, imaginar que esta lengua no tiene ninguna orden de entrada.) Imagínese un idioma con un solo comando: b. Esto interpreta un programa BF, que se coloca después de él, como b+++++.. 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.
Conor O'Brien
3
@EriktheOutgolfer el problema principal con su problema es "puede poner el programa BF que recibe de la entrada ..." Si el lenguaje solo es Turing completo en función de la entrada, entonces ¿cómo puede, sin ninguna entrada, ser Turing completo? Es decir, para que el lenguaje esté completo, es el propio programa del lenguaje el que debe codificar el programa. De lo contrario, se encuentra que están codificando el programa en la entrada, lo cual no es una forma válida de programación.
Conor O'Brien
1
No creo que este sea un punto establecido. Este artículo de Esolang discute el tema. (También está la cuestión de si un programa que imprime todos los programas de terminación posibles en un lenguaje completo de Turing , junto con su salida, es una demostración de integridad de Turing; eso no requiere entrada y puede hacerse con un programa finitamente largo .)
5

Paridad amistosa

Este lenguaje se basa en si hay números amigables con paridad opuesta .

Comandos

x : End program if not on top line  
+ : increment stored value  
- : decrement stored value  
{ : set next goto x value to current x value
} : goto previous x value set by {  
j : Go down one line if the special value is an amicable number and the
    parity is opposite to the matching number (loops back to top). If the
    special value is not an amicable number and not on the top line, go up
    one line.  

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

fəˈnɛtɪk
fuente
2

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\npasar a un operador y \nluego a otro operador, estamos en 3 líneas nuevas. Ahora, el siguiente es el 5, por lo que debe agregar \n\ny 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.

+ adds
- subtracts
/ divide
* multiply 
s sqrt
% mod
a push to vars
g sets stack to numbers
q pushes value of stack to numbers
i increment 
d decrement
r stops subtraction at 0
w turns back on subtraction past 0
[ starts loop
] ends loop runs until stack is 0
{ starts loop
} ends loop and loops until loops[ln] is 0
k increment loops

Mientras tengamos números primos ilimitados que sigan las reglas, este lenguaje tendrá una cinta no finita.

Máquina Minsky

\n\ng\nr\n\n[\n\nd\n\n\n\n]

Cómo funciona:

\n\ng     # the first two newlines are to get to a prime number of newlines (2) then sets the value of stack to the first variable in the array numbers (see code in link)

\nr       # gets to the next number and makes it so subtraction stops at 0

\n\n[     # starts the loop

\n\nd     # decrements stack 

\n\n\n\n] # ends loop

Pruébalo en KhanAcademy .

Christopher
fuente
@ trigo no necesita recorrer con memoria no finita
Christopher
Solo funciona si es cierto. No puedo terminar la redacción en este momento ya que estoy en el móvil, pero lo haré esta noche
Christopher
Incluso si tiene memoria infinita, aún necesita poder hacer un bucle infinito.
Pavel
Tengo bucles Tratando de hacerlos infinitos
Christopher
En este momento se estrellan
Christopher
2

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 aaaimplementa el problema 3n + 1, donde las iteraciones están representadas por un número correspondiente de asy el paso 3n + 1 se reemplaza con (3n + 1) / 2 [1], lo que lleva a la salida del programa:

aaa // 3
  abc
    cbc
      caaa
        aaaaa // 5
          aaabc
            abcbc
              cbcbc
                cbcaaa
                  caaaaaa
                    aaaaaaaa // 8
                      aaaaaabc
                        aaaabcbc
                          aabcbcbc
                            bcbcbcbc
                              bcbcbca
                                bcbcaa
                                  bcaaa
                                    aaaa // 4
                                      aabc
                                        bcbc
                                          bca
                                            aa // 2
                                              bc
                                                a // 1 and halt because we then begin an infinite loop
                                                 HALT

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

def taggis(inp, a, b, c):
    current = inp
    seen = set()
    while True:
        seen.add(tuple(current))

        yield current

        head = current[0]

        current = current[2:]

        current.extend([a, b, c][head])

        if tuple(current) in seen:
            return

def parse():
    program = input().split(" ")

    assert len(program) == 3, "There has to be exactly 3 production rules!" 

    productions = []

    for production in program:

        production = [{"a": 0, "b": 1, "c": 2}[x] for x in production]
        productions.append(production)  

    program_input = [{"a": 0, "b": 1, "c": 2}[x] for x in input()]

    k = 0   

    for step in taggis(program_input, *productions):
        print(' ' * k +''.join(['abc'[x] for x in step]))

        k += 2
    print(' ' * (k - 1) + 'HALT')

parse()
  1. que es equivalente a la función Collatz original ya que 3n + 1 de un impar nsiempre será par y, por lo tanto, la división se puede aplicar automáticamente

  2. Sistemas de etiquetas y funciones tipo Collatz, Liesbeth De Mol ,

ThePlasmaRailgun
fuente