Mi sento sempre disconnesso tra macchine astratte (come le macchine di Turing) e architetture di computer (incluse le architetture di macchine virtuali, l'architettura di Von Neumann). Quindi mi piacerebbe sapere come sono correlati? Come si influenza l'altro? Anche i riferimenti sono apprezzati. Grazie.
Le macchine di Turing e simili "macchine" sono modelli di calcolo , hanno lo scopo di investigare problemi come:
A tale scopo, la macchina stessa deve essere il più semplice possibile. La praticità del programmatore o le fastidiose preoccupazioni di implementazione non contano, dal momento che si tratta di oggetti matematici e solo pochissimi programmi vengono mai scritti direttamente per loro.
Al contrario, l'architettura della macchina virtuale e l'attuale architettura della macchina basata sul silicio sono centrate su eseguendo un determinato programma . La macchina è resa più complicata di quanto strettamente necessario per le preoccupazioni di cui sopra, e a sua volta richiede meno (e più ovvie) istruzioni per fare cose interessanti. Non troppo complicati, in quanto devono essere ancora comprensibili (e implementabili in modo efficiente), ma più complicati.
Quindi i due approcci sono fondamentalmente in disaccordo. Oltre ad essere entrambi nel campo dell'informatica, non hanno molto a che fare l'uno con l'altro.
La relazione principale è che puoi simulare il costrutto teorico in quello fisico.
Il fatto che quello fisico sia capace di tutto ciò che è teorico dà origine alla capacità di test teorici e di analisi della macchina teorica da riconoscere come implementabili nel mondo reale.
Il problema dell'arresto è un perfetto esempio di qualcosa che è stato mostrato su una macchina di turazione per essere irrisolvibile, e con la prova sulla macchina di turazione può quindi essere noto come irrisolvibile su una macchina reale che rispetta le leggi della macchina di turing .
È la differenza tra sommare le cose contando e facendolo scrivendolo su carta, è stato dimostrato che la realtà del conteggio soddisfa le stesse regole della sommatoria su un pezzo di carta. Quindi, quando simuli il conteggio fisico delle cose, i tuoi risultati sono riconosciuti come applicabili al mondo reale, quindi sai quanto costano due barrette di caramelle simulando mentalmente il conteggio senza dover contare il denaro fisico per ottenere il risultato. / p>
Attualmente le persone stanno elaborando analisi e test di un modello teorico noto come "Quantum Turing Machine" per vedere quali strutture saranno disponibili con le macchine di calcolo quantistico. È logico che le persone lavorino con questi modelli quando la versione fisica del loro modello è eccessivamente costosa, rara e le implementazioni attuali sono ancora molto carenti. I modelli teorici sono usati per mostrare ciò che potremmo essere in grado di fare quando le nostre implementazioni fisiche miglioreranno.
Sono imparentati all'incirca nello stesso modo in cui la navetta spaziale è collegata a un pallone gonfiato con il tuo respiro e poi lasciato andare e guardare volare via.
Il principio fondamentale di espellere qualcosa in una direzione per spingere qualcosa nella direzione opposta è lì.
Ecco dove finiscono le somiglianze.
Vedo le macchine teoriche come colmare il divario tra il calcolo del mondo reale e la matematica. Una macchina di Turing è abbastanza potente da simulare qualsiasi architettura del mondo reale o linguaggio di programmazione, abbastanza semplice da essere simulata facilmente e, soprattutto, abbastanza semplice da essere oggetto di ragionamenti matematici ragionevolmente semplici e prove.
È importante sapere che la definizione di computazione non è "quelle cose che fanno i computer". Il calcolo precede i computer. I computer hanno ricevuto il loro nome perché sono stati creati per aiutare il compito del calcolo, non perché lo definiscono.
Quindi la Turing Machine non riguarda il modo in cui funzionano i computer. Riguarda se un problema è computable - cioè, risolvibile da una logica formale / processo matematico. Non dice nulla su come questo processo possa essere implementato. Se è calcolabile, può essere risolto da esseri umani con matite e carta, dato un tempo sufficiente, o con computer o (questa è la cosa importante) con qualsiasi sistema che può essere mostrato come Turing completo .
Quindi la macchina di Turing fa due cose molto importanti:
Il primo punto ci consente di pensare ai problemi senza essere distratti dalle implementazioni del mondo reale. Questa è una buona cosa perché il vero hardware spesso distrae le persone con dettagli irrilevanti (come "cosa succede se esauriamo la memoria o lo spazio di archiviazione?", Dal momento che le macchine di Turing hanno una risorsa infinita). Una soluzione teorica dimostrabile può essere sviluppata per una Turing Machine e quindi tutto ciò che qualcuno deve fare è tradurlo in qualcosa che funzioni su una data architettura.
Il secondo punto ci consente di verificare la capacità di qualsiasi implementazione senza dover eseguire molti test diversi su di essa. Se può simulare una macchina di Turing, può fare qualsiasi cosa che la Turing Machine può fare. Dato che Turing Machines è in grado di calcolare qualsiasi cosa computabile, così può.
Il che significa che la relazione tra la Macchina di Turing e qualsiasi architettura di computer realmente pratica (anche virtuale) è solo una cosa: possono calcolare.
L'architettura di Von Neumann era un tentativo di creare un modello di progettazione per computer elettronici elettronici generici efficaci. Il lavoro di Turing ha fornito la prova della sua validità
Se ci pensi, le architetture sono macchine astratte. Descrivono come un grumo di silicio fatto con cura dovrebbe "comportarsi". La differenza tra le architetture e le macchine di Turing è più una questione di scala che un cambiamento fondamentale nell'approccio.
Il vantaggio delle macchine di Turing è che esiste una serie di prove utili che sono molto facili da fare usando una macchina di Turing. È semplice provare che qualsiasi macchina abbastanza potente da simulare una macchina di Turing può risolvere qualsiasi problema che una macchina di Turing può (duh). Tuttavia, diventa più interessante quando si definisce una funzione Computable . Risulta che ci sono molte definizioni compatibili di una funzione computabile. Se puoi definire tutto il tuo comportamento come funzioni computabili, puoi essere simulato in una macchina di Turing.
Quindi diciamo che hai un'architettura che supporta direttamente i programmi in stile LISP, e un'altra come la x86 che è più procedurale. Il tuo amico afferma "LISP è più espressivo, quindi puoi scrivere programmi su questa macchina che non potresti mai scrivere su x86." Questo è brutale da contrastare (specialmente perché probabilmente non conosci abbastanza LISP). Tuttavia, puoi abusare di diverse macchine astratte come la macchina di Turing:
Ci sono, naturalmente, molti altri esempi. Il gioco della vita di Conway ha dimostrato di essere completo Turing, il che significa che teoricamente potrebbe fare qualsiasi cosa il tuo computer possa fare. Il modo più semplice per farlo era creare un Turing machine in Life . Ne parlo perché questo sarebbe il caso di ciò che hai definito una macchina astratta trattata come un'architettura letterale! Puoi immaginare quanto sia dura l'affermazione di computabilità nella vita senza l'aiuto di modelli astratti (sono sicuro che non sto modellando un x64, completo di sbirciare nella cache, solo per dimostrare che Life è calcolabile!)
Alla fine, la grande differenza tra architetture e macchine astratte è che le architetture sono solitamente interessate alle prestazioni. Le architetture vogliono sapere quanto velocemente puoi fare qualcosa. Le macchine astratte tendono ad accontentarsi di sapere se è possibile. Considera il Costruttore universale sviluppato per le macchine a stati von Neuman. È stato sufficiente per dimostrare che l'UC potrebbe funzionare, ma che gli autori non hanno mai avuto abbastanza potenza di calcolo per vederlo effettivamente.
Le architetture di prezzo pagano per dimostrare quanto velocemente possono funzionare è che è spesso terribilmente difficile dimostrare di poter calcolare tutto . Per questo, le architetture tornano indietro e iniziano a usare macchine astratte.
Leggi altre domande sui tag architecture