Macchina di Turing vs macchina di Von Neumann

Question

Sfondo

Von-Neumann architettura descrive il computer a programma memorizzato in cui le istruzioni ed i dati vengono memorizzati e la macchina funziona cambiando il suo stato interno, cioè un'istruzione opera su alcuni dati e modifica i dati . Così intrinsecamente, v'è stato mantenuto nel sistema.

Turing architettura della macchina funziona manipolando simboli su un nastro. cioè Un nastro con un numero infinito di slot esiste, e in qualsiasi punto nel tempo, la macchina di Turing è in un particolare slot. Sulla base del simbolo leggere a quello slot, la macchina può cambiare il simbolo e passare a un altro slot. Tutto questo è deterministica.

---

Domande

1. C'è qualche relazione tra questi due modelli? Era il modello di Von Neuman basa su o ispirato al modello di Turing?

2. Si può dire che il modello di Turing è un superset di modello di Von Newman?

3. si adatta programmazione funzionale nel modello di Turing? Se é cosi, come? Presumo programmazione funzionale non si presta bene al modello di Von Neuman.

Answer 1

Le macchine di Turing sono concetti teorici inventato per esplorare il dominio di problemi computabili matematicamente e di ottenere modi di descrivere questi calcoli.

L'architettura di Von Neumann è un'architettura per la costruzione di i computer attuali (che implementare quello che la macchina di Turing descrive in teoria).

La programmazione funzionale si basa sul lambda-calcolo , che è un altro metodo di calcolo che descrivono o - più precisamente - funzioni calcolabili. Anche se utilizza un approccio completamente diverso, è altrettanto potente per macchina di Turing (si dice di essere turing completa ).

Ogni programma lambda-calcolo (termine) T è scritto solo utilizzando una combinazione di

• variabili come x
• funzioni anonime come λx. T
• applicazioni funzione T T

Nonostante sia stateless, questo è sufficiente per ogni calcolo di un computer può fare. Turing macchine e lambda termini può emulare l'altro, e un computer Von-Neumann può eseguire sia (a parte limitazioni tecniche come a deposito infinito, quale una macchina di Turing potrebbe richiedere).

Ma a causa della loro apolidi e più astratta della natura, programmi funzionali potrebbero essere meno efficiente e meno "intuitivo" sui computer Von-Neumann rispetto al programmi imperativi che seguono il suo stile di binario, la memoria e l'aggiornamento .

Answer 2

Generalmente si riferisce all'architettura Von Neumann , in contrasto con il Harvard architettura. La prima ha codice ei dati memorizzati nello stesso modo, mentre il secondo è percorsi memoria e bus separati per codice e dati. Tutti i PC desktop moderni sono Von Neumann, la maggior parte dei microcontrollori sono Harvard. Entrambi sono esempi di design del mondo reale che tentano di emulare una macchina di Turing teorica (che è impossibile, perché una vera macchina di Turing richiede memoria infinita).

Answer 3

modello di Turing definisce capacità di calcolo senza entrare in profondità nella realizzazione, nessuno potrà mai creare computer che sarà simile a Turing Machine letteralmente. (Tranne gli appassionati di http://www.youtube.com/watch?v=E3keLeMwfHY ).

Turing modella non è Architettura .

Von Neuman è una guida come costruire i computer. Non dice nulla circa le capacità di calcolo. A seconda set di istruzioni del computer prodotto può o non può essere Turing completi (mezzi in grado di risolvere stessi compiti Macchina di Turing)

La programmazione funzionale (lambda calcolo) è un altro modello di calcolo che è Turing completa, ma non può essere in forma in modo nativo in architettura di Von Neumann.

Answer 4

Non so quale rapporto storico che c'è tra macchine di Turing e le architetture von Neuman. Sono sicuro, tuttavia, che von Neuman era a conoscenza di macchine di Turing quando ha sviluppato l'architettura di von Neuman.

Per quanto capacità di calcolo, tuttavia, macchine di Turing e macchine von Neuman sono equivalenti. Ciascuna delle quali può emulare l'altro (IIRC, emulando un programma von Neuman su una macchina di Turing è un O (n ^ 6) operazione). programmazione funzionale, in forma di lambda calcolo, è anche equivalente. Infatti, tutti i framework di calcolo noti almeno altrettanto potente come macchine di Turing sono equivalenti:

• macchine di Turing
• Lambda calcolo (programmazione funzionale)
• macchine von Neuman
• funzioni ricorsive parziali

Non c'è differenza nel set di funzioni che possono essere calcolate con uno di questi modelli.

La programmazione funzionale deriva dal lambda calcolo, in modo che non mappa direttamente a uno o macchine di Turing von Nemuan. Uno di loro può eseguire programmi funzionali, hoewver, tramite l'emulazione. Credo che il mapping per le macchine di Turing è probabilmente più noioso il mapping per macchine von Neuman, quindi la mia risposta alla terza domanda sarebbe "no, in realtà è peggio."

Answer 5

Il "modello" di Turing non è un modello architettonico a tutti. Era solo una macchina inesistente che Turing ipotizzato per servire come veicolo per la sua prova del problema di decisione .