windows - para - ¿Se completó el lote de turing?

tag rename

Question

No puedo encontrar si lo es o no y tengo mucha curiosidad: si no califica, ¿qué funcionalidad le falta para calificar? He hecho una cantidad decente de lotes y no veo ningún error obvio en la capacidad.

Answer 1

Acabo de ''probar'' que el lote está completo, al crear un intérprete de brainfuck en conjunto (porque se ha demostrado que el brainfuck está completo):

https://github.com/YoYoYonnY/Brainfuck-In-Batch

Por cierto, un lenguaje de programación completo y completo significa:

• imposible crear un programa que pueda determinar si otro programa (en el mismo idioma) se detendrá o continuará ejecutándose para siempre (no sé cómo funciona éste, y creo que nadie lo usó para demostrar que Turing lo completo).
• posible crear un programa que pueda ejecutar todos los programas posibles en el idioma (un intérprete: Brainfuck intérprete en Brainfuck (hay una versión mejor, que desafortunadamente no puedo encontrar. Este es terriblemente lento))
• Posible actuar como o simular una máquina de Turing, y por lo tanto contiene al menos los siguientes aspectos:
  • Escribir en la memoria (es decir, cambiar un valor de variable a cualquier otro valor; solo se puede cambiar de true a false y al revés sigue siendo válido. En el caso de un lote: SET A=5 )
  • La memoria "infinita" (es decir, debe haber más de un bit / byte, también puede escribir, preferiblemente infinitamente). Cadenas, matrices, tablas, campos de bits o incluso solo enteros son válidos, siempre y cuando podamos escribir en todo el objeto. Tenga en cuenta que debe ser posible leer y escribir en una variable por dirección: debe haber cambios de bits si desea que los enteros sean válidos, y debe poder indexar su matriz, por lo que algo como array[index]; )
  • Declaraciones de salto condicional (es decir, IF %A%==0 GOTO LABEL (Saltar a etiqueta si A es cero), while (var) {/*code*/} (Saltar de nuevo al principio del código mientras que var no es cero) o jmp0 exit; (Salta para salir si el valor actual en la pila es cero)

La máquina tradicional de Turing requiere que usted tenga una cinta que sea infinita en ambos lados, pero también funcionará una matriz simple, cadena, tabla (objeto) o número binario (campo de bits). En mi "Brainfuck in Batch", por ejemplo, utilicé un objeto similar a una matriz / tabla para almacenar la memoria (ya que batch le permite cambiar la clave de un valor, así: SET ARRAY[%KEY%]=%VALUE% )

Answer 2

Creo que califica. Se cree que los requisitos básicos de la integridad de Turing se pueden reducir a unas pocas operaciones simples, que incluyen: la capacidad de almacenar el estado (variables), la capacidad de ramificarse (condicionales) y la capacidad de iterar (bucles). El lote tiene todos estos elementos, por lo tanto, a menos que haya algún requisito aún no descubierto para la integridad de Turing, los scripts por lotes califican.