Macchina di Turing

Una macchina di Turing è un calcolatore idealizzato, si suppone cioè che non sia sottoposto ai limiti fisici dei normali calcolatori (di memoria, di spazio, di velocità, ecc).
Tale macchina è costituita da un nastro indefinitamente lungo e da una testina in grado di effettuare alcune operazioni sul nastro. In particolare la testina può leggere il simbolo contenuto nella attuale posizione del nastro, cancellarlo o scrivere al suo posto un altro simbolo, spostarsi a destra o a sinistra.
Volendo formalizzare questa descrizione sommaria di una macchina di Turing è possibile definire un'espressione in questo modo:
dato un alfabeto di simboli "s1,s2,s3,...,sn q1,q2,q3,...,qm D,S" un espressione è una successione finita di simboli presi da questa lista.
Una quintupla è un espressione della forma:
qi sj qk sl M

Una quintupla si interpreta in questo modo: Se la configurazione interna è "qi" e il simbolo osservato è "sj" allora passa nello stato "qk" e scrivi al suo posto "sl"; infine spostati di una casella a destra o sinistra a seconda che M valga D oppure S.

Definizione di macchina di Turing: una macchina di turing è un insieme finito (non vuoto) di quintuple che non coincidano in nessuno dei loro primi due simboli.

Tale definizione pone delle condizioni di finitezza e determinatezza alla macchina di Turing relativamente all'alfabeto di simboli da utilizzare e al fatto che la macchina potrà eseguire al più un'operazione alla volta.
Alcune macchine di Turing vengono dette "universali" perché sono in grado di simulare il comportamento di qualsiasi macchina di Turing.

Quello che la macchina di Turing esegue è un procedimento algoritmico che nei normali calcolatori viene specificato in qualche linguaggio di programmazione.
Turing diede anche una definizione di quelle che sono le funzioni calcolabili da una macchina di Turing: "qualsiasi funzione che possa essere specificata mediante procedimento algoritmico è calcolabile da una macchina di Turing". Tale tesi è stata elaborata indipendentemente da Church e Turing (essa infatti è anche nota come tesi di Church-Turing). Il lavoro che portò a tale tesi fu principalmente dovuto alla necessità di generalizzare i teoremi di incompletezza scoperti da Godel. Nella versione direttamente collegata al lavoro di Turing il primo teorema di incompletezza si può così enunciare: "dato un procedimento algoritmico che consente di operare in maniera corretta nell'ambito dell'aritmetica elementare, quindi consente di generare tutti gli enunciati veri, esso risulta essere incompleto, ovvero non consente al contempo di non generare alcun enunciato falso. Il problema di generare tutti e soli gli enunciati veri non è risolvibile nemmeno in linea di principio.