Fondamenti di calcolo e relazione con i computer moderni [chiuso]

0

Voglio capire in che modo le basi teoriche della computazione si riferiscono ai computer del mondo reale. Per quanto ne so, le macchine di Turing, le funzioni ricorsive, le macchine a stati finiti, il calcolo lambda, la logica combinatoria e altri modelli sono tutti teoricamente equivalenti nel modo in cui rappresentano il calcolo. Per me, questi modelli sembrano essere alla base di ciò che realmente è la computazione, al livello più elementare.

Quindi, la mia domanda principale è, in che modo questi modelli puramente teorici di computazione si riferiscono all'architettura del computer reale? Come passare da questi modelli teorici a uno strumento del mondo reale, che utilizza l'ingegneria elettrica e la fisica, aspetti che non vengono presi in considerazione nei modelli di calcolo? Ad esempio, il computer del mondo reale è un'incarnazione fisica avanzata della macchina di Turing, o è completamente fuori luogo?

EDIT: La mia domanda è diversa rispetto alla semplice domanda su come funzionano i computer. Mi sto chiedendo in particolare della relazione tra computer e modelli di calcolo della vita reale e pratica.

    
posta Wesley 19.01.2016 - 04:52
fonte

1 risposta

2

how do these purely theoretical models of computation relate to real-world computer architecture?

Non lo fanno.

Sia λ-calculus che Turing Machines sono stati progettati per modellare il modo in cui un umano calcola. Non sono stati progettati per modellare le macchine informatiche.

Questo è più ovvio nella Turing Machine, che è stata pesantemente modellata sul modo in cui un "computer" (che durante il tempo di Alan Turing era una descrizione del lavoro per un umano!) funzionava: mantenendo un una quantità limitata di informazioni nella sua testa e scrivere il resto su un foglio di carta. Turing ha reso la quantità di informazioni arbitrariamente grande (ma finita), e ha permesso infinite quantità di carta (e ha tagliato i fogli a strisce e li ha incollati insieme per ottenere un nastro unidimensionale semplificato), tuttavia, anche ammettendo quantità disumane di informazioni e nastri infiniti fisicamente impossibili, potrebbe provare che ci sono certe cose che non possono essere calcolate.

Il calcolo λ si sviluppa in modo analogo al desiderio di formalizzare il significato del calcolo, in questo caso invece di partire dall'atto fisico di come un umano scrive calcoli su carta, si basa più sull'intuizione di come si valutare una funzione nella propria testa.

Turing ha dimostrato che può esistere una Universal Turing Machine, cioè una Turing Machine in grado di leggere la descrizione di una macchina di Turing arbitraria dal nastro ed eseguire le operazioni della macchina di Turing. Questo può essere considerato il primo interprete e il primo computer con programmi memorizzati.

Tuttavia , le persone che sono state effettivamente coinvolte nello sviluppo dei primi computer digitali sostengono che il lavoro dei logici sui modelli di calcolo ha avuto poca influenza sul lavoro degli ingegneri elettrici e matematici applicati che hanno costruito il primo computer digitali, nonostante la sorprendente somiglianza.

Ci sono sono modelli di calcolo che sono molto più vicini a ciò che assomigliano ai computer mainstream attuali. La Random Access Machine, ad esempio, è un modello di costo per l'analisi degli algoritmi che modella più da vicino come si accede alla memoria in un tipico computer, cioè con accesso casuale a tempo costante, al contrario di una Turing Machine, dove il tempo di accesso è lineare nel distanza dalla posizione di memoria corrente a quella a cui si desidera accedere (è necessario spostare la testa attraverso il nastro una cella alla volta).

Si noti che si usa il termine "architettura del computer reale" come se ce ne fosse solo uno. Ci sono infatti molte diverse architetture. Ad esempio, Reduceron è una CPU a riduzione di grafi specificamente progettata per i linguaggi Haskell-like, funziona in modo molto diverso, ad esempio, da una tipica CPU x86. Esistono architetture che modellano esplicitamente i costi di comunicazione sul chip, come l'architettura FLEET. L'Harvard Architecture separa strettamente codice e dati rispetto all'architettura von Neumann, che non fa distinzioni tra loro. E così via.

    
risposta data 20.01.2016 - 10:50
fonte

Leggi altre domande sui tag