La ramificazione condizionale è un requisito della completezza di Turing?

Question

Ho cercato sul web e trovo risposte un po 'contraddittorie. Alcune fonti affermano che una lingua/macchina/cosa-hai-tu è Turing completa se e solo se ha entrambe le diramazioni condizionali e incondizionate (che credo sia ridondante), alcuni dicono che è richiesto solo incondizionato, altri che è richiesto solo un condizionale.

Leggendo il tedesco Z3 e ENIAC, Wikipedia dice:

La Z3 tedesca (mostrato a lavorare maggio 1941) creata da Konrad Zuse. Esso stato il primo general-purpose digitale calcolatore, ma era elettromeccanico, anziché elettronico, come un tempo relè per tutte funzioni. Calcolato logicamente usando la matematica binario . Era programmabile tramite il nastro perforato , ma mancava del ramo condizionale . Sebbene non sia stato progettato per la completezza di Turing, lo è stato accidentalmente, come è stato scoperto nel 1998 (ma per sfruttare questo Turing-completezza, erano necessari gli hacker complessi ).

Quali hack complessi, intelligenti, esattamente?

Un 1998 Documento astratto di R. Rojas afferma anche (Si noti che non ho letto questo documento, è solo un frammento da IEEE.):

La macchina di calcolo Z3, costruito da Konrad Zuse tra il 1938 e il 1941, operazioni aritmetiche in virgola mobile operazioni di aritmetica in virgola mobile (addizione, sottrazione, radice) moltiplicazione, divisione e radice quadrata ) codificate in un nastro perforato. Una domanda interessante da porre, dal punto di vista della storia dell'informatica, è se queste operazioni sono o meno sufficienti per il calcolo universale. Il documento mostra che, in effetti, un loop di programma singolo contenente queste istruzioni aritmetiche può simulare qualsiasi macchina di Turing il cui nastro è di tipo con dimensioni finite. Questo è fatto da simulando la ramificazione condizionale e l'indirizzamento indiretto con mezzi aritmetici puramente . Z3 di Zuse è quindi, almeno in linea di principio, come universale come i computer di oggi che hanno uno spazio di indirizzamento limitato.

In breve, SOers, quale tipo di diramazione è esattamente richiesto per la completezza della Turing? Supponendo che la memoria infinita, una lingua con solo un goto o jmp ramo di costruzione (no if o jnz costrutti) essere considerato Turing-completo?

Answer 1

Il documento originale Rojas può essere trovato here. L'idea di base è che la Z3 supporta solo un loop singolo incondizionato (incollando le estremità del nastro di istruzioni insieme). Costruisci la sua esecuzione condizionale mettendo tutte le sezioni di codice una dopo l'altra nel ciclo e disponendo di una variabile z che determina quale sezione eseguire. All'inizio della sezione di j, si imposta

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

e poi fare ogni assegnazione a = b op c in questa sezione leggere

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

(vale a dire ogni assegnazione è un no-op, fatta eccezione per la sezione attiva). Ora, questo include ancora un compito condizionale: come confrontare z == j? Si propone di utilizzare la rappresentazione binaria di z (z1..zm) insieme alla rappresentazione binaria negata j (c1..cm), quindi calcolare

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

Questo prodotto sarà 1 solo se c e z differiscono in tutti i bit, cosa che succederà solo se z == j. Un'assegnazione a z (che essenzialmente è un salto indiretto) deve anche assegnare a z1..zm.

Rojas ha anche scritto Conditional Branching is not Necessary for Universal Computation in von Neumann Computers. Lì propone una macchina con codice auto-modificante e relativo indirizzamento, in modo che tu possa leggere le istruzioni di Turing dalla memoria e modificare il programma per saltare di conseguenza. In alternativa, propone l'approccio sopra (per Z3), in una versione che utilizza solo LOAD (A), STORE (A), INC e DEC.

Answer 2

Lo Z3 era solo Turing completo da un punto di vista astratto. Puoi avere un nastro di programma arbitrariamente lungo e farlo calcolare entrambi i lati di ogni ramo condizionale. In altre parole, per ogni ramo, calcolerebbe entrambe le risposte e dirà quale ignorare.Ovviamente questo crea programmi esponenzialmente più grandi per ogni ramo condizionale che avresti, quindi non potresti mai usare questa macchina in modo completo da Turing.

Answer 3

Hai bisogno di qualcosa che può derivare in base all'input (dai risultati).

Un modo per simulare i rami condizionali è con il codice auto-modificante: si esegue un calcolo che deposita i suoi risultati nel flusso di istruzioni in esecuzione. È possibile inserire il codice operativo per un salto incondizionato nel flusso di istruzioni e fare calcoli matematici su un input per creare l'obiettivo corretto per quel salto, a seconda di alcune condizioni per l'input. Ad esempio, sottrai x da y, passa a destra a 0-fill se era positivo, o 1-fill se era negativo, quindi aggiungi un indirizzo di base e memorizza quel risultato immediatamente dopo il codice operativo jmp. Quando arrivi a quella jmp, andrai a un indirizzo se x == y, e un altro se x! = Y.

Answer 4

Se si dispone solo di espressioni aritmetiche, è possibile utilizzare alcune proprietà delle operazioni aritmetiche. Ad esempio, A è 0 o 1 a seconda di alcune condizioni (che è stata precedentemente calcolata), quindi A*B+(1-A)*C calcola l'espressione if A then B else C.

Answer 5

Se è possibile calcolare l'indirizzo per il proprio goto o jmp, è possibile simulare condizionali arbritari. Occasionalmente ho usato questo per simulare "ON x GOTO a, b, c" in ZX Basic.

Se "true" ha il valore numerico 1 e "false" 0, quindi una costruzione simile:

if A then goto B else goto C 

è identico a:

goto C+(B-C)*A 

Quindi, sì, con un "calcolata goto "o la capacità di auto-modificarsi, un goto o jmp può agire come un condizionale.

Answer 6

Non è necessaria la ramificazione condizionale per costruire una macchina completa di Turing, ma ovviamente qualsiasi macchina completa di Turing fornirà la ramificazione condizionale come caratteristica principale.

È stato dimostrato che sistemi semplici come Rule 110 Cellular Automaton possono essere utilizzati per implementare una macchina di Turing. Di sicuro non hai bisogno di una ramificazione condizionale per estrarre un tale sistema dal bit bucket. In realtà si potrebbe semplicemente usare a bunch of rocks.

Il punto è che una macchina di Turing fornirà la ramificazione condizionale, quindi ciò che state facendo in ogni caso provando la completezza di Turing sta in qualche modo implementando la ramificazione condizionale. Devi farlo senza ramificazioni condizionali ad un certo punto, che si tratti di rocce o giunzioni PN nei semiconduttori.

Answer 7

Se una macchina può diramazione, allora sì Turing completa.

Hoever ci sono anche macchine che non possono saltare ramo o anche SE, ma sono ancora complete di Turing.

Il motivo della ramificazione condizionale rende automaticamente completo qualsiasi computer di Turing.

L'elaborazione è solo il processo di identificazione degli ingressi in ordine per selezionare le uscite.

La ramificazione è un modo per mentalizzare questo processo, la condizione del salto è ciò che può classificare gli input, il punto in cui si dirama memorizza l'output corretto per quell'input.

Quindi per chiarire finalmente; Se si dispone di una diramazione condizionale, il computer è necessariamente equivalente dal punto di vista computazionale. TUTTAVIA, ci sono molti altri modi in cui un computer può raggiungere la completezza. (lambda, IF's, CL)