I concetti fondamentali introdotti indipendentemente dal modello di Von Neumann sono, in sintesi:
- L’algoritmo come concetto intuitivo: una sequenza finita di azioni elaborative da eseguire automaticamente: l’algoritmo necessita di un esecutore per essere eseguito;
- IL modello di automa: ciascun automa esegue un algoritmo, ottenuto come sequenza di “uscite”, in risposta ad analoghi “ingressi”;
con l’automa si introduce il concetto di stato - IL modello di Turing: ciascuna macchina esegue un algoritmo, come sequenza di alcune precisate azioni elaborative elementari (destra, sinistra, leggi, scrivi, …) e, sorprendentemente, la tesi di Church ha affermato che questo semplice modello consente in realtà di fornire una definizione di algoritmo: è algoritmo ciò che può essere calcolato da una macchina di Turing;
- Esiste una distinta macchina di Turing per ciascun distinto problema da calcolare.
Il concetto che caratterizza un calcolatore è quello di possedere un programma registrato in memoria: la medesima macchina fisica (il calcolatore), attrezzata con differenti “programmi” è in grado di rappresentare tutte le possibili macchine di Turing (fatti salvi soltanto alcune questioni di natura puramente teorica sulla “capacità” di memoria).
Un “programma” è la descrizione formalizzata di un algoritmo, espressa in un linguaggio di programmazione: è questo il nuovo concetto che verrà introdotto con i prossimi modelli.
In un modello alternativo, la stessa macchina di Turing potrebbe in effetti essere una macchina “a programma”: basterebbe in proposito concepire un “linguaggio” formale con il quale esprimere la sequenza delle azioni elaborative elementari ed un organo che interpretasse tali “istruzioni” eseguendole; la descrizione della macchina avverrebbe attraverso tale “programma” piuttosto che attraverso la tabella delle transizioni classica dei modelli di automa e di Turing.