E’ un sistema di controllo a stati finiti con una testina e un nastro (virtualmente infinito) composto da tante celle, ognuna contenente un simbolo proveniente da un alfabeto finito.
Esempio di nastro di una TM
Definizione: Si definisce formalmente una TM come la quintupla:
$$ M = (Q, \Sigma, q_0, \delta) $$
$Q$: insieme finito di stati
$\Sigma$: un alfabeto finito (con dei caratteri di controllo: $\rhd$ e $\sqcup$)
Il simbolo $\sqcup$ specifica che non ho un simbolo e il simbolo $\rhd$ specifica che da lì parte l’input.
uno stato iniziale $q_0 \in Q$
una funzione di transizione $\delta : Q \times \Sigma \rarr Q \times \Sigma \times \{\larr, \rarr,\ \_\}$
Mappa uno stato e un simbolo in uno stato, un simbolo e un movimento.
Teorema: Non esiste nessun formalismo di calcolo che sia più potente della Macchina di Turing.
“Se un problema è umanamente calcolabile, allora esisterà una macchina di Turing in grado di risolverlo (cioè di calcolarlo)”
E’ una tesi che non ha dimostrazione formale (non avendo chiara la definizione di calcolo) ma è stata dimostrata empiricamente nel corso degli anni, portando quindi a dire che il calcolo è ciò che può essere eseguito con una TM (anche se non tutti i meccanismi di calcolo sono equivalenti ad una TM, ad esempio gli automi a stati finiti).
Quindi, ciò che è computabile è computabile è computabile da una TM o da un suo equivalente (come un linguaggio di programmazione). Banalmente anche una rete neurale lo è.
Una configurazione di una TM è definita da: