Il problema dell'arresto e l'indecidibilità: un'analisi costruttiva

Il concetto di indecidibilità ha una lunga e complessa storia nella teoria della computazione, e uno degli esempi più significativi e concreti di indecidibilità è il cosiddetto problema dell'arresto (Halting Problem). La sua importanza risiede non solo nella sua dimostrazione rigorosa, ma anche nel modo in cui essa fornisce una base solida per comprendere i limiti intrinseci dei sistemi algoritmici e computazionali.

Il problema dell'arresto riguarda la domanda: esiste un algoritmo che, dato qualsiasi programma (algoritmo) M e un input w, possa determinare se M si fermerà o continuerà a eseguire all'infinito quando applicato a w? In altre parole, è possibile costruire un algoritmo che, per ogni possibile programma e ogni possibile input, possa prevedere se l'esecuzione del programma si concluderà o meno? La risposta a questa domanda è stata fornita da Alan Turing nel 1936, quando dimostrò che il problema dell'arresto è indecidibile, cioè non esiste un algoritmo che possa risolverlo in generale per tutti i programmi.

Per comprendere questa conclusione, è utile considerare una delle dimostrazioni più famose, quella basata sull'argomento diagonale, che ha le sue radici nella famosa prova di Cantor sull'indecidibilità dell'insieme dei numeri reali. La prova di Turing sfrutta una variante del metodo diagonale per mostrare che non esiste alcun algoritmo che possa risolvere universalmente il problema dell'arresto.

Immaginiamo, per un momento, di avere una lista infinita di programmi algoritmici, ciascuno con il suo rispettivo Gödel number, una rappresentazione univoca dell'algoritmo come stringa. Supponiamo che esista un algoritmo, chiamato M, che possa decidere se un programma si ferma o meno per un dato input. Ora, costruiamo un nuovo algoritmo, N, che utilizza M in modo indiretto: N esegue M sul proprio Gödel number. Se M decide che il programma si ferma, N entrerà in un ciclo infinito; se M decide che il programma non si ferma, N si fermerà subito. Quando proviamo a determinare il comportamento di N nel caso in cui venga eseguito con il proprio Gödel number come input, ci troviamo in una contraddizione: N si ferma se e solo se non si ferma, il che è chiaramente impossibile. Questa contraddizione implica che non esiste alcun algoritmo M che possa decidere in modo corretto il problema dell'arresto per tutti i programmi e tutti gli input.

Questo argomento è molto potente, ma la sua applicabilità va ben oltre il singolo esempio del problema dell'arresto. In effetti, possiamo generalizzare l'idea e affermare che esistono insiemi di decisione che sono fondamentalmente non decidibili, ovvero per i quali non esiste nessun algoritmo che possa determinare la risposta corretta in tutti i casi. Un esempio di questo è dato dai sottoinsiemi di numeri naturali: se supponiamo che ci siano solo un numero finito di sottoinsiemi di N, arriviamo a una contraddizione simile a quella del problema dell'arresto.

Una delle implicazioni più profonde di queste dimostrazioni riguarda il concetto di algoritmicità e la comprensione dei limiti della computazione. Questi limiti non sono solo teorici, ma hanno applicazioni pratiche in molte aree della scienza computazionale, come la crittografia, l'intelligenza artificiale e il riconoscimento dei pattern. La consapevolezza di tali limiti è fondamentale per evitare l'errore di pensare che ogni problema possa essere risolto tramite un algoritmo.

Un altro aspetto cruciale da comprendere è che, mentre il problema dell'arresto è indecidibile in modo assoluto, questo non significa che sia impossibile decidere se un particolare programma si ferma su un dato input. Esistono algoritmi che possono risolvere il problema per molti casi specifici, ma non esiste una soluzione universale che funzioni per ogni possibile programma e input. Inoltre, la questione dell'efficienza computazionale gioca un ruolo significativo: anche se un problema fosse teoricamente decidibile, potrebbe essere computazionalmente impraticabile risolverlo in tempi ragionevoli per input di grandi dimensioni.

Infine, è importante sottolineare che il problema dell'arresto è solo uno dei tanti esempi di indecidibilità che esistono nel panorama della teoria della computazione. Altri problemi, come la determinazione di soluzioni di equazioni di diophantine, presentano analoghe difficoltà, mostrando che i limiti della computazione non si esauriscono nel semplice problema dell'arresto, ma riguardano tutta una classe di problemi che sono fondamentalmente irrisolvibili.

Come rappresentare funzioni e relazioni in una teoria aritmetica: la teoria R e la sua estensione

La teoria R è una delle pietre miliari nella logica matematica e nella teoria della computazione, poiché fornisce una base formale per comprendere come le relazioni e le funzioni possono essere rappresentate all'interno di un sistema aritmetico. La rappresentazione di relazioni e funzioni aritmetiche in una teoria come R è un passo cruciale per comprendere la potenza e i limiti di un sistema formale.

Consideriamo innanzitutto come la teoria R rappresenta la relazione di uguaglianza e la relazione di ordine parziale. La formula che rappresenta l'uguaglianza tra due variabili $x$ e $y$ è la semplice formula $x = y$. Per dimostrare che questa formula rappresenta correttamente la relazione di uguaglianza, dobbiamo verificare due condizioni fondamentali. La prima condizione, indicata come (a), afferma che per ogni numero naturale $n$, la teoria R prova che $n = n$. Questo è un caso dell'assioma di uguaglianza. La seconda condizione, indicata come (b), stabilisce che per ogni coppia di numeri distinti $n$ e $m$, la teoria R prova che $n \neq m$, il che è un corollario dell'assioma $R \neq$.

Analogamente, la relazione di ordine $\leq$ è rappresentata dalla formula $\exists z (z + x = y)$, dove la somma di $x$ e $z$ deve essere uguale a $y$. Per dimostrare che questa formula rappresenta correttamente la relazione $\leq$, dobbiamo ancora una volta mostrare due condizioni. La prima, (a), stabilisce che per ogni $m \leq n$, la teoria R prova che $m \leq n$. La seconda condizione, (b), afferma che per ogni $m > n$, la teoria R prova che $\neg m \leq n$. La dimostrazione di questa seconda condizione si fonda sull'assioma $R \neq$, che garantisce che per ogni $m' \leq n$, la teoria R dimostri $m \neq m'$.

Le definizioni e i teoremi successivi sono strettamente legati al concetto di rappresentabilità. Una funzione $k$-aria $f$ su $N$ è rappresentabile in una teoria $T$ se esiste una formula $A_f(x_1, x_2, \dots, x_k, y)$ tale che, per ogni $n_1, \dots, n_k \in N$, e per ogni $m = f(n_1, n_2, \dots, n_k)$, la teoria $T$ prova la formula $\forall y [A_f(n_1, n_2, \dots, n_k, y) \leftrightarrow y = m]$. Questo definisce formalmente il concetto di una funzione rappresentabile in una teoria.

Il Teorema VII.15, che fornisce una formulazione equivalente della rappresentabilità, afferma che una funzione $f$ è rappresentata in $T$ dalla formula $A_f$ se e solo se si verificano tre condizioni. La prima condizione (a) stabilisce che $T$ prova $A_f(n_1, n_2, \dots, n_k, m)$. La seconda condizione (b) garantisce che per ogni $m' \neq m$, $T$ prova $\neg A_f(n_1, n_2, \dots, n_k, m')$. La terza condizione (c) assicura che, per ogni $x, y$, se $A_f(n_1, n_2, \dots, n_k, x)$ e $A_f(n_1, n_2, \dots, n_k, y)$ sono veri, allora $x = y$.

Un esempio semplice di funzione rappresentabile è la funzione successore. La formula $A_S(x_1, y)$ che rappresenta la funzione successore $n \mapsto n + 1$ è semplicemente $S(x_1) = y$. La verifica di questa rappresentazione è immediata, poiché per ogni $n$, la teoria R prova che $S(n) = n + 1$, e quindi $\forall y (S(n) = y \rightarrow y = n+1)$, che sono entrambi immediati dall'assioma di uguaglianza.

Allo stesso modo, la funzione di somma e la funzione di moltiplicazione sono anch'esse rappresentabili in $R$. La formula $A_+ (x_1, x_2, y)$ che rappresenta la somma $\langle n_1, n_2 \rangle \mapsto n_1 + n_2$ è semplicemente $x_1 + x_2 = y$, e la verifica è simile a quella della funzione successore, in quanto la somma di due numeri è definita in modo esplicito. Analogamente, la formula $A_{\cdot} (x_1, x_2, y)$ rappresenta la moltiplicazione $\langle n_1, n_2 \rangle \mapsto n_1 \cdot n_2$, e la dimostrazione segue lo stesso schema.

La rappresentabilità, come illustrato in vari teoremi, implica che una relazione rappresentata in $R$ è decidibile e che una funzione rappresentata in $R$ è computabile. In particolare, ogni relazione rappresentabile in una teoria consistente e axiomatizzabile $T$ che estende $R$ è decidibile, e ogni funzione rappresentabile in tale teoria è computabile. Questo è un concetto fondamentale che collega la logica formale alla computabilità e all'algoritmicità, ponendo le basi per il successivo sviluppo del teorema di incompletezza di Gödel.

Infine, la teoria R e le sue estensioni forniscono un quadro rigoroso per esplorare la computabilità delle funzioni e delle relazioni, ma anche per comprendere i limiti intrinseci di qualsiasi sistema formale. La relazione tra rappresentabilità e decidibilità è cruciale per il passaggio successivo alla comprensione delle limitazioni di ogni teoria formale, inclusa la famosa incompletitudine di Gödel.

Come la Teoria Q Implica la Teoria R: Un'Analisi di Incompletezza e Indefinibilità

La teoria aritmetica Q si sviluppa all'interno di un contesto di incompletezza che solleva questioni fondamentali riguardo alla decidibilità e alla definibilità all'interno degli insiemi numerici. Il teorema di incomplettezza di Gödel ci mostra che in sistemi formali sufficientemente complessi non è possibile definire un algoritmo universale che decida la verità o la falsità di ogni proposizione aritmetica. L'esempio della teoria PA (Peano Aritmetica) è particolarmente illuminante in questo contesto, in quanto ci dimostra che esistono affermazioni aritmetiche che, pur essendo vere, non possono essere provate all'interno del sistema stesso. La teoria ThN, che descrive la verità in N (insieme dei numeri naturali), ci invita a riflettere sul concetto di "verità" come qualcosa di intrinsecamente indefinibile all'interno della stessa struttura aritmetica.

Il teorema di Tarski sull'indefinibilità della verità è uno dei risultati più rilevanti in questo ambito. Esso stabilisce che non esiste una formula che possa essere considerata una "definizione di verità" per l'aritmetica naturale. Non esiste una formula Tr(x1) tale che per ogni proposizione A, l'affermazione N ⊧ A se e solo se N ⊧ Tr(⌜A⌝) è vera. La dimostrazione di questo teorema avviene per contraddizione. Supponiamo che esista una definizione di verità Tr(x1). Secondo il teorema della diagonale, esisterebbe una proposizione D¬Tr che sarebbe equivalente a ¬Tr(⌜D¬Tr ⌝). Se Tr fosse una definizione di verità, allora dovremmo avere che la proposizione D¬Tr è vera in N, ma contemporaneamente non dovrebbe esserlo, portando a una contraddizione. Di conseguenza, il teorema ci dice chiaramente che una definizione di verità globale per l'aritmetica naturale non è possibile.

In questo scenario, la teoria Q svolge un ruolo cruciale. La teoria Q, che è una forma di aritmetica di ordine inferiore, è capace di modellare concetti aritmetici ma è intrinsecamente legata alla stessa logica di incompletezza che caratterizza la teoria PA. La sezione successiva della discussione si concentra su come la teoria Q implica la teoria R, cioè come Q può essere utilizzata per derivare proprietà fondamentali della teoria aritmetica, come gli assiomi R+, R● e R≠.

L'emergere del risultato Q ⊧ R è significativo. Esso stabilisce che Q è in grado di derivare gli assiomi R+ che trattano le proprietà aritmetiche basilari come l'addizione. Ad esempio, attraverso l'induzione, si dimostra che Q è in grado di provare affermazioni come m + n = m + n, una proprietà che si estende a numeri naturali tramite l'assioma Q4 e la proprietà induttiva. Analogamente, l'induzione su m e n permette a Q di provare che m ⋅ n = m ⋅ n per qualsiasi m e n appartenenti ai numeri naturali.

La teoria Q inoltre conferma che le disuguaglianze tra numeri naturali, come m ≠ n, sono anch'esse provabili. Attraverso l'induzione su n, si mostra che Q è in grado di dimostrare che, per ogni coppia di numeri m e n, se m è diverso da n, allora questa disuguaglianza è vera in Q. La combinazione di questi risultati stabilisce la capacità di Q di dedurre la teoria R, confermando che una base formale come Q può essere estesa per comprendere proprietà numeriche fondamentali che sono essenziali per il funzionamento della teoria aritmetica più complessa.

Inoltre, l'interconnessione tra la teoria Q e la teoria R apre una riflessione più profonda sulla natura dell'aritmetica formale. Seppur Q possa derivare gli assiomi di base dell'aritmetica, come l'addizione e la moltiplicazione, non si può ignorare che la teoria stessa si fonda su un sistema che non è completo, come dimostrato dal primo teorema di incompletezza di Gödel. Ogni sistema formale che include l'aritmetica naturale, come Q, è soggetto a limitazioni intrinseche che impediscono la completa risoluzione di ogni problema aritmetico all'interno di quel sistema. Il lavoro con la teoria Q, pertanto, non solo approfondisce la nostra comprensione delle fondamenta dell'aritmetica, ma ci invita a riconoscere i confini naturali della logica matematica.

È cruciale per il lettore comprendere che, sebbene la teoria Q e la sua capacità di derivare gli assiomi R possa sembrare un progresso nella formalizzazione matematica, queste teorie non risolvono i problemi fondamentali legati all'incompletezza. In effetti, ogni sistema formale che si applica all'aritmetica naturale è destinato a essere incompleto, come evidenziato dal teorema di Gödel. Allo stesso modo, l'indefinibilità della verità in questi sistemi ci spinge a riconoscere che la verità matematica non può essere racchiusa in una definizione univoca all'interno di un sistema formale. Ciò implica che la matematica, seppur potente, rimane sempre aperta a interpretazioni che trascendono le strutture formali, portando alla consapevolezza della sua natura incompleta e potenzialmente infinita.