Tipicamente, si è abituati a vedere la computazione come un processo che conduce da un input a un output, ovvero come il calcolo di una funzione. Il modello di computazione considerato determina allora quali funzioni siano calcolabili.
Tra tutte le possibili funzioni, ci si può concentrare anche solo su quelle che corrispondono al problema del riconoscimento di un linguaggio $L$ su un alfabeto $\Sigma$. Ciascuna di queste funzioni ha la forma $\Sigma^*\rarr\{sì, \ no\}$: prende in input una stringa su $\Sigma$ e determina se essa appartenga o meno al linguaggio $L$. Concentrarsi solo sul riconoscimento dei linguaggi è sufficiente e vantaggioso perchè:
Come esempio per introdurre un primo modello di computazione, si consideri una porta automatica che viene attraversata in una sola direzione (dal lato anteriore della porta al lato posteriore). Su ciascun lato della porta è presente un tappetino in grado di rilevare la presenza di una persona. Quando arriva una persona sul rilevatore anteriore, la porta:
Inoltre, supponendo che la porta si apra verso il lato posteriore, per evitare situazioni pericolose essa non deve muoversi (aprirsi o chiudersi) fintanto che è presente una persona sul rilevatore posteriore (dato che questa potrebbe essere colpita dalla porta in movimento).
La porta è gestita da un apposito controller, che riceve in input le informazioni di presenza/assenza di persone sui rilevatori e produce in output un segnale di comando per l’attuatore che apre/chiude la porta. Mettendo insieme le informazioni fornite dai due rilevatori, si può definire l’alfabeto di tutti i possibili input:
Per poter reagire correttamente a questi input, il controller ha poi bisogno di memorizzare lo stato in cui si trova la porta, che può essere CLOSED oppure OPEN. La quantità di memoria di cui questo controller ha bisogno è dunque pari a un singolo bit.
In base allo stato corrente e all’input, il controller cambia stato (si ha una transizione) nel modo descritto dalla seguente tabella di transizione: