Cos'è una macchina astratta?

Le macchine astratte, anche chiamate 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 a cui è consentito eseguireogni 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 automobile pushdown è uno che ha la capacità di manipolare la sua pila di input, piuttosto che semplicemente rispondere a loro uno per uno nell'ordine in cui appaiono.

Wolfram Mathworld

dà due famosi esempi di macchine astratte.Uno di questi esempi è Conways Game of Life, 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 che vive 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, la macchina Turing, è una delle macchine astratte più elementari e fondamentali nell'informatica.Una macchina Turing esegue operazioni su un nastro mdash; una stringa di simboli mdash; 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 il simbolo di trasformazione delle istruzioni su 1, quindi spostarsi a destra.Questa macchina non produrrebbe altro che una stringa di 1s.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.