Cos'è una macchina astratta?
Le macchine astratte, chiamate anche automi, sono un elemento dell'informatica teorica. Una macchina astratta ricorda una funzione in matematica. Riceve input e produce output secondo le regole specificate. Le macchine astratte differiscono dalle macchine più letterali perché si presume funzionino perfettamente e indipendentemente dall'hardware. Sono suddivisi in tipi sulla base di caratteristiche come 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 è definita 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 rispondere semplicemente ad uno ad uno nell'ordine in cui appaiono.
Wolfram MathWorld offre 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 griglia viene 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 otto possibili), muore. Una cellula 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 Turing esegue operazioni su un nastro, una serie di simboli, di dimensioni illimitate. Contiene istruzioni sia per cambiare i simboli sia per cambiare il simbolo su cui sta operando. Una semplice macchina di Turing potrebbe avere solo l'istruzione "trasforma il simbolo in 1, quindi sposta 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 in grado di eseguire diverse operazioni con lo stesso input.
Queste macchine astratte possono servire a molti scopi. Possono essere divertenti giocattoli teorici, ma possono anche servire da modelli per sistemi informatici reali. La macchina astratta è al centro dell'informatica come disciplina.