Cos'è una macchina astratta?
Le macchine astratte, chiamate anche automi, sono un elemento di informatica teorica. Una macchina astratta ricorda una funzione in matematica. Riceve input e produce output secondo le regole specifiche. Le macchine astratte differiscono da più macchine letterali perché si presume che funzionino perfettamente e indipendentemente dall'hardware. Sono suddivisi in tipi sulla base di caratteristiche come il modo in cui eseguono 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 sono autorizzate a eseguire in un determinato punto. Una macchina astratta è chiamata deterministica se c'è sempre solo un 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 rispondere a loro da One 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é può emergere una sola configurazione da qualsiasi altra. Questo gioco utilizza una griglia in cui ogni scatola, o cella, può avere lo stato "vivente" o "morto". Lo stato dell'intera griglia è determinato sulla base dello stato precedente. Se una cellula vivente tocca esattamente due o tre altre 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, Turing Machine, è una delle macchine astratte più elementari e fondamentali nell'informatica. Una macchina Turing esegue operazioni su un nastro - una stringa di simboli—di dimensioni illimitate. Contiene istruzioni sia per cambiare i simboli sia per cambiare il simbolo su cui opera. Una semplice macchina Turing potrebbe avere solo l'istruzione "trasforma il simbolo in 1, quindi spostarsi a destra". Questa macchina non produrrebbe altro che una stringa di 1. Questa semplice macchina Turing è deterministica, ma è anche possibile costruire macchine Turing non deterministiche in grado di eseguire diverse operazioni diverse date 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.