1. Comportamento della macchina di Turing

È un modello di calcolo introdotto dall’ing. Alan Turing nel 1936, per simulare il processo di calcolo umano. Analogamente ai calcolatori di oggi essa possiede una memoria su cui poter leggere e scrivere e un'unità di elaborazione centrale (CPU, dall’inglese Central Processing Unit). La memoria è composta da un nastro infinito, suddiviso in celle al quale la CPU può accedervi attraverso una testina di lettura/scrittura). La CPU di una macchina di Turing è composta da un registro di stato il quale contiene lo stato attuale della macchina e da un programma contenente le istruzioni che deve eseguire. 

Inizialmente, nel nastro è contenuta la stringa di input preceduta e seguita da una serie infinita di simboli vuoti, la testina è posizionata sul primo simbolo della stringa di input e la CPU si trova nellostato iniziale. A seconda dello stato in cui si trova la CPU e del simbolo letto dalla testina, la macchina esegue un’istruzione del programma che può:

modificare il simbolo attualmente letto;

spostare la testina a destra oppure a sinistra;

cambiare lo stato della CPU. 

La macchina prosegue nell’esecuzione del programma fino a quando la CPU non si trova nello stato finale, oppure non esistono istruzioni del programma che sia possibile eseguire.

Quando l’esecuzione termina la stringa di output sarà racchiusa in quella parte di nastro delimitata dalla testina e dal primo simbolo vuoto alla sua destra.

2. Macchina di Turing universale e tesi di Church

Nel 1854, il matematico britannico George Boole, elaborò la matematica algebrica. Nell'algebra booleana un simbolo può assumere solo uno dei due seguenti valori: vero o falso. Analogamente alle leggi della logica, le operazioni di calcolo si possono eseguire utilizzando gli operatori matematici(OR, AND, NOT, ecc.)

Grazie a Boole il matemat...