Le macchine astratte, chiamate anche automi, sono un elemento dell’informatica teorica. Una macchina astratta assomiglia a una funzione in matematica. Riceve input e produce output secondo regole specificate. Le macchine astratte differiscono dalle macchine più letterali perché si presume che funzionino perfettamente e indipendentemente dall’hardware. Sono suddivisi in tipologie in base a caratteristiche quali il modo in cui svolgono le loro operazioni e quali tipi di input possono ricevere.
Quando si classificano le macchine astratte, una delle distinzioni più semplici riguarda il numero di operazioni che possono eseguire in un dato punto. Una macchina astratta è detta deterministica se c’è sempre un solo modo per procedere. Non è deterministico se esistono più possibilità per la macchina in almeno uno dei suoi possibili stati. Un automa “pushdown” è uno che ha la capacità di manipolare la sua pila di input, piuttosto che semplicemente rispondervi uno per uno nell’ordine in cui appaiono.
Wolfram MathWorld fornisce due famosi esempi di macchine astratte. Uno di questi esempi è il gioco della vita di Conway, che è una macchina astratta deterministica perché solo una configurazione può emergere da qualsiasi altra. Questo gioco utilizza una griglia in cui ogni casella, o cella, può avere lo stato “vivo” o “morto”. Lo stato dell’intera rete è determinato sulla base dello stato precedente. Se una cellula vivente tocca esattamente altre due o tre cellule viventi, continua a vivere. Se ha uno, due o più di tre vicini (fino a un possibile otto), muore. Una cella morta con esattamente tre vicini prenderà vita; altrimenti, rimarrà morto.
Un altro esempio, la macchina di Turing, è una delle macchine astratte più basilari e fondamentali nell’informatica. Una macchina di Turing esegue operazioni su un nastro, una stringa di simboli, di dimensioni illimitate. Contiene istruzioni sia per cambiare i simboli che per cambiare il simbolo su cui sta operando. Una semplice macchina di Turing potrebbe avere solo l’istruzione “trasforma il simbolo in 1, quindi spostati a destra”. Questa macchina non produrrebbe altro che una stringa di 1. Questa semplice macchina di Turing è deterministica, ma è anche possibile costruire macchine di Turing non deterministiche che possono eseguire diverse operazioni date lo stesso input.
Queste macchine astratte possono servire a molti scopi. Possono essere divertenti giocattoli teorici, ma possono anche servire come modelli per sistemi informatici reali. La macchina astratta è al centro dell’informatica come disciplina.