Come vi ho annunciato nel precedente articolo, ecco il primo articolo riguardante la teoria della calcolabilità e della complessità.

Impossibile per me iniziare questa serie di articoli se non con una citazione:

Studia prima la scienza, e poi seguita la pratica, nata da essa scienza.
Quelli che s’innamoran di pratica senza scienza son come ’l nocchier ch’entra in navilio senza timone e bussola, che mai ha certezza dove si vada.

Cit. Leonardo da Vinci.

Partiamo con una prima idea degli argomenti che tratterò.

La teoria della calcolabilità si occupa di categorizzare i problemi in due grandi categorie: quelle dei problemi calcolabili e problemi non calcolabili. Un problema appartiene alla categoria dei problemi calcolabili se e soltanto se esiste una funzione calcolabile in grado di risolverlo. Quindi ci serve una definizione rigorosa di funzione calcolabile che corrisponde all’idea intuitiva di algoritmo.

La teoria della calcolabilità, però, non si preoccupa di stabilire quanto sia “difficile” o “costoso” calcolare una data funzione calcolabile. Qua entra in gioco la teoria della complessità che si occupa di classificare i problemi calcolabili in base a quanto sia complicato risolverli. In particolare vengono definite due grandi categorie eterogenee: quelle dei problemi trattabili e problemi intrattabili. Un problema trattabile è “facilmente” calcolabile, mentre per uno intrattabile non esiste una funzione calcolabile che lo risolva in tempo “utile”.

Ovviamente ognuna di queste definizioni intuitive ha bisogno di una sua definizione rigorosa e formale, tanto più che ci troviamo in territorio matematico.

Teoria della Calcolabilità

Iniziamo a trattare la calcolabilità. Per prima cosa abbiamo bisogno di definire che cosa sia un algoritmo. Iniziamo con una prima definizione facile da capire e informale.

Definizione: un algoritmo è una sequenza finita di istruzioni (scelte da un insieme finito di istruzioni accettabili) che definiscono in modo non ambiguo le operazioni da eseguire per raggiungere un risultato.

Più schematicamente abbiamo:

• un insieme finito di istruzioni disponibili, ognuna ha un effetto limitato su dati discreti
• una sequenza finita di istruzioni (passi discreti dell’algoritmo)
• ogni istruzione richiede un tempo finito
• ogni passo dipende solo dal passato e da una porzione finita di dati
• nessuna limitazione al numero di passi della computazione ne alla dimensione dei dati

Come avevo scritto all’inizio, la calcolabilità non si preoccupa della trattabilità del problema, quindi permettiamo agli algoritmi di metterci tutto il tempo e lo spazio di cui hanno bisogno per risolvere il problema.

Per formalizzare questa definizione, sono stati proposti molti formalismi diversi, ma il più celebre resta, senza ombra di dubbio, la macchina di Turing.

Macchina di Turing

Una macchina di Turing (da qui in poi talvolta abbreviato in MdT) è un formalismo con il quale si definisce un’ipotetica macchina ideale costituita da un nastro infinito e da una testina mobile. La testina è in grado di leggere e/o scrivere dal e sul nastro un simbolo appartenente ad un alfabeto predefinito. La macchina usa la testina per leggere un simbolo dal nastro e decidere se e come modificare il simbolo e se e come spostarsi sul nastro. In ogni momento la testina si trova sopra una cella ben definita del nastro. In base a come “programmiamo” la MdT possiamo far si che la macchina modifichi il nastro a nostro piacimento, fino ad ottenere il risultato del calcolo che ci interessa sul nastro.

NB: non è detto che la macchina si fermi! Inoltre, come dimostreremo, nei casi non banali non possiamo saperlo a priori, senza eseguire gli stessi passi che compirà la macchina.

Definizione di macchina di Turing: una macchina di Turing M è una tupla o sequenza ordinata \((Q, \Sigma, \delta, q_0, h)\) dove:

• Q è un insieme finito di stati \(q_i\) , in particolare \(q_0 \in Q\) è lo stato iniziale, quello da cui parte la computazione della MdT.
• Σ è un insieme finito di simboli (un alfabeto) composto da almeno questi simboli speciali #, ▷, L, R, ―. Il # rappresenta una cella vuota del nastro (la MdT può scrivere un # per cancellare un simbolo dal nastro); il respingente o marca di inizio stringa ▷ si trova sempre all’inizio del nastro; L è il comando per spostare a sinistra la testina, R sposta a destra e ― lascia la testina in posizione.
• δ è la relazione di transiszione, una funzione che prende in input lo stato attuale della MdT e il simbolo sul nastro appena letto dalla testina dall Mdt e restituisce un nuovo stato, un nuovo simbolo da scrivere sul nastro e uno spostamento della testina. Non è altro che il “programma” in esecuzione sulla MdT. Contiamo 2 input e 3 output, quindi possiamo descrivere questa funzione con un insieme di quintuple così definite: \(\delta \subseteq (Q\times\Sigma) \times (Q \cup \{h\}) \times \Sigma \times \{L,R,-\}\) . Inoltre deve essere vero che se \((q, \triangleright, q', \sigma, D) \in \delta\) allora \(\sigma = \triangleright, D = R\) . Quest’ultima condizione impone il fatto che la testina non può mai trovarsi a sinistra di un respingente ▷ (infatti ▷ respinge la testina a destra).
• h (da halt) è lo stato finale, cioè quello che una volta raggiunto fa terminare la computazione della MdT e \(Q \notni h\) .

Per oggi è tutto. A domani.