¿Es la ramificación condicional un requisito de Turing-completitud?

Question

He estado buscando en la web y estoy encontrando respuestas algo contradictorias. Algunas fuentes afirman que un lenguaje/máquina/lo que-tiene-usted es Turing completo si y solo si tiene tanto ramificación condicional e incondicional (que supongo que es un poco redundante), algunos dicen que solo se requiere incondicional, otros que solo se requiere condicional.

La lectura sobre la Z3 alemán y ENIAC, Wikipedia dice:

El Z3 Alemán (se muestra hábil de mayo 1941) fue diseñado por Konrad Zuse. Fue fue la primera computadora digital de uso general , pero era electromecánica, en lugar de electrónica, ya que utilizaba relés para todas las funciones . Se calculó lógicamente usando matemática binaria. Fue programable por cinta perforada, pero carecía de la rama condicional . Aunque no se diseñó para Turing-completitud, fue accidentalmente, ya que se descubrió en 1998 (pero para explotar esto Turing-completeness, complex, astutos hacks eran necesarios).

¿Qué complejos, ingeniosos hacks, exactamente?

Un documento de 1998 Resumen de R. Rojas también Unidos (Tenga en cuenta que no he leído este documento, es sólo un fragmento de IEEE.):

La máquina de computación Z3, construido por Konrad Zuse entre 1938 y 1941, solo pudo ejecutar secuencias fijas de operaciones aritméticas de coma flotante (suma, resta, multiplicación, división y raíz cuadrada ) codificadas en una cinta perforada. Una pregunta interesante de , desde el punto de vista de la historia de la informática, es si estas operaciones son o no suficientes para el cálculo universal. El documento muestra que, de hecho, un solo bucle de programa que contiene estas instrucciones aritméticas puede simular cualquier máquina de Turing cuya cinta es de un tamaño finito dado . Esto se hace por simulando la derivación condicional y direccionamiento indirecto por medios aritméticos puramente . Zuse's Z3 es por lo tanto, al menos en principio, como universal, ya que las computadoras de hoy en día que tienen un espacio de direccionamiento limitado.

En resumen, SOers, ¿qué tipo de ramificación se requiere exactamente para Turing-completitud? Suponiendo que la memoria es infinita, ¿puede considerarse un lenguaje con un constructo de ramificación goto o jmp (sin construcciones if o jnz) como Turing-complete?

Answer 1

El documento original de Rojas se puede encontrar here. La idea básica es que el Z3 solo admite un solo bucle incondicional (pegando los extremos de la cinta de instrucciones). Usted construye la ejecución condicional de la misma poniendo todas las secciones de código una tras otra en el ciclo, y teniendo una variable z que determina qué sección ejecutar. Al principio de la sección j, se establece

if (z==j) then t=0 else t=1 

y luego hacer cada asignación a = b op c en esta sección leer

a = a*t + (b op c)*(1-t) 

(es decir, cada asignación es un no-op, excepto en la sección activa). Ahora, esto todavía incluye una asignación condicional: cómo comparar z == j? Se propone el uso de la representación binaria de z (z1..zm), junto con la representación binaria negada de j (c1..cm), y luego calcular

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm)) 

Este producto será 1 sólo si c y z difieren en todos los bits, lo que sucederá solo si z == j. Una asignación a z (que esencialmente es un salto indirecto) también debe asignarse a z1..zm.

Rojas también ha escrito Conditional Branching is not Necessary for Universal Computation in von Neumann Computers. Allí propone una máquina con código de modificación automática y direccionamiento relativo, para que pueda leer las instrucciones de Turing de la memoria y modificar el programa para saltar en consecuencia. Como alternativa, propone el enfoque anterior (para Z3), en una versión que solo usa LOAD (A), STORE (A), INC y DEC.

Answer 2

El Z3 solo se completa desde un punto de vista abstracto. Puede tener una cinta de programa arbitrariamente larga y simplemente hacer que calcule ambos lados de cada rama condicional. En otras palabras, para cada sucursal, calcularía ambas respuestas y le diría cuál ignorar.Obviamente, esto crea programas exponencialmente más grandes para cada rama condicional que tendría, por lo que nunca podría utilizar esta máquina de una manera completa de Turing.

Answer 3

Necesita algo que pueda derivar en función de (resultados de) la entrada.

Una forma de simular ramas condicionales es con código de modificación automática: realiza un cálculo que deposita su resultado en la secuencia de instrucciones que se está ejecutando. Puede poner el código de operación para un salto incondicional en la secuencia de instrucciones y hacer cálculos en una entrada para crear el objetivo correcto para ese salto, dependiendo de un conjunto de condiciones para la entrada. Por ejemplo, resta x de y, cambia a la derecha a 0-fill si fue positivo, o 1-fill si es negativo, luego agrega una dirección base y almacena ese resultado inmediatamente después del código de operación jmp. Cuando llegue a ese jmp, irá a una dirección si x == y, y otra si x! = Y.

Answer 4

Si solo tiene expresiones aritméticas, puede usar algunas propiedades de operaciones aritméticas. Por ejemplo, A es 0 o 1 dependiendo de alguna condición (que se calculó previamente), luego A*B+(1-A)*C calcula la expresión if A then B else C.

Answer 5

Si puede calcular la dirección para su goto o jmp, puede simular condicionales arbritary. De vez en cuando lo usé para simular "ON x GOTO a, b, c" en ZX Basic.

Si "verdadero" tiene el valor numérico 1 y "falso" 0, a continuación, una construcción como:

if A then goto B else goto C 

es idéntica a:

goto C+(B-C)*A 

Así que, sí, con un "computarizada goto "o la capacidad de auto-modificar, un goto o jmp puede actuar como un condicional.

Answer 6

No es necesario bifurcación condicional para construir una máquina de Turing completo, pero por supuesto cualquier máquina de Turing completo va a proporcionar la bifurcación condicional como una característica central.

Se demostró que los sistemas tan simple como la Rule 110 Cellular Automaton pueden utilizarse para implementar una máquina de Turing. Seguramente no necesita una bifurcación condicional para extraer dicho sistema del cubo de bits. En realidad, uno podría simplemente usar a bunch of rocks.

El punto es que una máquina de Turing proporcionará la bifurcación condicional, así que lo que está haciendo de todos modos, demostrando Turing completo está implementando un tanto bifurcación condicional. Tienes que hacerlo sin ramificación condicional en algún punto, ya sea rocas o uniones PN en semiconductores.

Answer 7

Si una máquina puede bifurcarse, entonces sí, está completa.

Hoever También hay máquinas que no pueden saltar sucursal o incluso si, pero todavía están Turing completo.

La razón por la que tiene condicional de ramificación Hace automáticamente todos Turing computadora completa es así.

El procesamiento es solo el proceso de identificación de entradas para seleccionar salidas.

ramificación es una forma de mentalizar este proceso, la condición de que el salto es lo que se puede clasificar entradas, el lugar en el que la rama también almacena la salida correcta para esa entrada.

Para aclarar finalmente; Si tiene una bifurcación condicional, su computadora es necesariamente computacionalmente equivalente. SIN EMBARGO, hay muchas otras formas en que una computadora puede completar. (lambda, IF's, CL)