💬 NLP

Turing or Cantor: That is the Question

Questo articolo stabilisce il ruolo fondamentale di Georg Cantor negli sviluppi di Alan Turing, proponendo una nuova misura di indecidibilità basata sulla probabilità, estendendo i modelli di calcolo super-Turing e definendo tre nuove classi di complessità per problemi indecidibili (U-completa, D-completa e H-completa), concludendo che la classe U-completa non è equivalente alla classe NP-completa.

Autori originali: Eugene Eberbach

Pubblicato 2026-04-14

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Eugene Eberbach

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina il mondo dell'informatica come un enorme laboratorio di cucina. In questo laboratorio, il compito principale è cucinare (risolvere problemi) seguendo ricette precise (algoritmi).

1. I Due Grandi Cuochi: Turing e Cantor

Il titolo del paper si chiede: "Chi è il vero padre della cucina moderna? Alan Turing o Georg Cantor?"

Alan Turing è il famoso Chef. Ha inventato la "macchina da cucina" universale (la Macchina di Turing). Questa macchina può seguire qualsiasi ricetta scritta su un foglio. Se la ricetta è chiara e finita, la macchina cucina il piatto. Ma Turing ha scoperto una cosa terribile: ci sono alcune ricette che, per quanto tu provi, la macchina non riuscirà mai a finire. Si bloccherà per sempre o non capirà mai se il piatto è pronto. Questo è il problema della "decidibilità": ci sono piatti che non si possono cucinare con le regole attuali.
Georg Cantor è il Matematico Silenzioso che ha scoperto le dimensioni dell'infinito. Prima di Turing, Cantor aveva già dimostrato che ci sono "infiniti" più grandi di altri. Immagina di avere un numero infinito di ingredienti (i numeri interi) e un numero infinito di ricette (i numeri reali). Cantor ha dimostrato che le ricette sono molto più numerose degli ingredienti. C'è un "buco" enorme tra ciò che possiamo scrivere e ciò che esiste.

La tesi del paper: Senza la scoperta di Cantor (che ci sono più ricette possibili di quante ne possiamo scrivere), Turing non avrebbe mai potuto dimostrare che la sua macchina non può cucinare tutto. Quindi, Cantor è il "nonno dimenticato" dell'informatica.

2. Il Problema della "Cucina Infinita"

Turing ha detto: "Ehi, c'è un problema! Non posso cucinare tutto".
Il paper dice: "Aspetta, non fermiamoci qui! Dobbiamo misurare quanto è impossibile cucinare certe cose".

L'autore propone una nuova idea: invece di dire semplicemente "questo problema è impossibile", chiediamoci: "Quanti ingredienti di questo problema sono impossibili da cucinare?"

Se il 100% degli ingredienti è impossibile, è un disastro totale.
Se solo il 10% è impossibile, forse possiamo cucinare il resto usando un po' di fortuna o approssimazione.

È come dire: "Non possiamo prevedere il meteo per sempre, ma possiamo dire che il 90% delle volte la nostra previsione funziona".

3. Tre Nuove Categorie di "Ricette Impossibili"

L'autore introduce tre nuove classi di problemi impossibili, ispirandosi a come classificiamo i problemi difficili (come il famoso P vs NP), ma portandole nel regno dell'impossibile. Immagina tre livelli di "cucina impossibile":

A. U-Completo (Il "Mezzo Impossibile")

Cos'è: Sono problemi che possiamo iniziare a cucinare. Se la ricetta funziona, la macchina si ferma e dice "Ecco il piatto!". Ma se la ricetta è sbagliata o infinita, la macchina gira in eterno senza mai dirti che non funziona.
L'analogia: È come cercare un ago in un pagliaio. Se trovi l'ago, sei felice e ti fermi. Se non lo trovi, continui a cercare per sempre senza sapere se è nascosto o se non c'è.
Esempi: Il problema della fermata (sapere se un programma si blocca), il problema della corrispondenza di Post.

B. D-Completo (Il "Completamente Impossibile")

Cos'è: Qui la situazione è peggiore. Non solo la macchina non si ferma, ma non c'è nemmeno modo di riconoscere se stai cercando la ricetta giusta o quella sbagliata. È come se il foglio della ricetta fosse scritto in una lingua che nessun cuoco può nemmeno leggere.
L'analogia: È come cercare di contare i punti di una stella che non esiste. Non puoi nemmeno dire "sto cercando bene" o "sto cercando male". È il livello della "diagonalizzazione" (un trucco matematico di Cantor che mostra che ci sono più cose di quante ne possiamo elencare).
Esempi: Il linguaggio della diagonalizzazione, problemi che nemmeno una macchina può riconoscere.

C. H-Completo (L'"Iper-Impossibile")

Cos'è: Questo è il livello superiore, dove entrano in gioco le "Macchine Oracolo" (una macchina che ha un mago che le dice la risposta). Anche con un mago che ti dà le risposte, ci sono problemi che rimangono irrisolvibili.
L'analogia: Immagina di avere un oracolo che ti dice la risposta a qualsiasi domanda. Ebbene, c'è ancora una domanda che nemmeno l'oracolo può rispondere. È un livello di complessità che richiede risorse infinite, quasi come cercare di scrivere l'intero universo su un foglio di carta.
Esempi: Problemi che richiedono un'infinità di infiniti (gerarchie di Cantor).

4. La Conclusione: Perché è Importante?

Il paper ci dice che per anni abbiamo pensato che se un problema era "impossibile" per un computer, allora era morto e sepolto.
L'autore dice: "No! È solo l'inizio!".

Invece di buttare via i problemi difficili, dovremmo classificarli:

Quali sono "semi-impossibili" (U-complete)?
Quali sono "totalmente impossibili" (D-complete)?
Quali sono "impossibili anche per i maghi" (H-complete)?

Questo ci aiuta a capire che l'informatica non è finita con Turing. Proprio come Cantor ha mostrato che l'infinito ha molti livelli, anche i problemi che i computer non possono risolvere hanno una loro gerarchia.

In sintesi:
Alan Turing ci ha dato la macchina, ma Georg Cantor ci ha dato la mappa per capire perché quella macchina non può andare ovunque. E ora, invece di arrenderci di fronte ai problemi che la macchina non risolve, stiamo imparando a misurare quanto sono irrisolvibili, creando una nuova mappa per esplorare i limiti della nostra intelligenza artificiale e della logica.

Titolo: Turing o Cantor: La Domanda

Autore: Eugene Eberbach (Rensselaer Polytechnic Institute)
Data: Aprile 2026 (Preprint)

1. Il Problema e il Contesto

Il paper affronta i limiti fondamentali della computabilità e della decidibilità nell'informatica teorica. Sebbene Alan Turing sia universalmente riconosciuto come il fondatore dell'informatica per la sua dimostrazione dell'indecidibilità del Entscheidungsproblem (problema della decisione) di Hilbert, l'autore sostiene che il contributo di Georg Cantor alla teoria degli insiemi sia stato il prerequisito fondamentale e spesso sottovalutato per tali risultati.

Il problema centrale identificato è la mancanza di una classificazione strutturata per i problemi indeducibili (non risolvibili dalle Macchine di Turing). Mentre la teoria della complessità classica (P, NP, NP-completo) classifica i problemi risolvibili ma intrattabili, non esiste una gerarchia formale e completa per i problemi che sono intrinsecamente non risolvibili da una Macchina di Turing (TM). Inoltre, il paper critica l'assunzione che la dimostrazione dell'indeducibilità di un problema debba segnare la fine di ogni tentativo di risoluzione, proponendo invece approcci basati su distribuzioni probabilistiche e modelli di calcolo "super-Turing".

2. Metodologia

L'autore utilizza un approccio che combina:

Rivalutazione Storica e Logica: Analisi delle prove originali di Turing (1936) e dei lavori di Cantor (teoria degli insiemi, ipotenuse, ipotenuse) per dimostrare che la prova di Turing è una diretta applicazione della diagonalizzazione di Cantor.
Dimostrazioni Matematiche: Fornisce una nuova prova più breve dell'indeducibilità del Entscheidungsproblem basata esclusivamente sulla cardinalità degli insiemi (numeri reali vs interi) e sull'argomento diagonale di Cantor, senza ricorrere a complessi meccanismi di auto-riferimento come nella prova originale di Turing.
Definizione di Nuovi Modelli: Estende il concetto di "Macchina Oracle" (o-macchina) di Turing a una classe generale di modelli di calcolo Super-Turing (o ipercomputazionali).
Classificazione Teorica: Propone una nuova tassonomia per i problemi indecidibili, ispirata alla definizione di NP-completo di Cook/Levin, ma applicata all'ambito della non-risolubilità.
Analisi Probabilistica: Introduce il concetto di "misura di indecidibilità" basata sulla distribuzione di probabilità dei dati di input, distinguendo tra istanze decidibili e non decidibili all'interno di un problema.

3. Contributi Chiave

A. Ruolo Fondamentale di Cantor

L'autore dimostra che senza i risultati di Cantor (in particolare la differenza tra infinito numerabile e non numerabile, e l'argomento diagonale), la prova di Turing non sarebbe stata possibile. Turing ha semplicemente mappato le macchine di Turing agli interi (numerabili) e i linguaggi/problemi ai numeri reali (non numerabili). Di conseguenza, Cantor è proposto come il "nonno implicito" dimenticato dell'informatica.

B. Nuova Misura di Indecidibilità

Viene proposta una metrica quantitativa per l'indeducibilità: il grado di insolvibilità di un problema è definito dalla percentuale di istanze di input che sono indecidibili rispetto a quelle decidibili, basandosi sulla distribuzione di probabilità degli input. Questo permette di trattare problemi che sono "parzialmente" decidibili o dove la maggior parte delle istanze è risolvibile.

C. Estensione ai Modelli Super-Turing

Il paper estende le macchine Oracle di Turing a una classe completa di modelli Ipercomputazionali (Super-Turing), che includono automi cellulari, reti neurali, macchine interattive e modelli basati su tempo infinito o risorse infinite.

D. Introduzione di Tre Nuove Classi di Complessità

L'autore definisce formalmente tre nuove classi di complessità per i problemi indecidibili delle Macchine di Turing, ispirate alla gerarchia di Cantor e Turing:

U-complete (Universal Complete):
- Definisce problemi semi-decidibili (Ricorsivamente Enumerabili ma non Ricorsivi - REnonREC).
- Esempi: Il linguaggio della Macchina di Turing Universale ( $L_u$ ), il Problema di Corrispondenza di Post (PCP), il problema del "Busy Beaver".
- Caratteristica: Le parole nel linguaggio possono essere accettate in un numero finito di passi, ma le parole fuori dal linguaggio non possono essere rifiutate in tempo finito.
- Risultato: Si dimostra che per questa classe, i linguaggi ricorsivi non sono uguali ai linguaggi ricorsivamente enumerabili ma non ricorsivi.
D-complete (Diagonalization Complete):
- Definisce problemi che non sono nemmeno Ricorsivamente Enumerabili (non-RE).
- Esempi: Il linguaggio di diagonalizzazione ( $L_d$ ), il complemento del linguaggio universale.
- Caratteristica: Nessun TM può accettare o rifiutare le parole in un numero finito di passi; la decisione richiede l'impossibilità di enumerazione.
H-complete (Hypercomputation Complete):
- Definisce problemi "iper-indecidibili" che non possono essere risolti nemmeno con un numero infinito di passi da una TM standard, ma richiedono modelli di calcolo ipercomputazionali.
- Esempi: Linguaggi di iper-diagonalizzazione ( $L_{hd}$ ).
- Caratteristica: Richiedono risorse infinite (tempo, memoria o oracoli di ordine superiore) per essere risolti.

E. Risposta alla Domanda "P vs NP" per i Problemi Indecidibili

Mentre la domanda $P \stackrel{?}{=} NP$ rimane aperta per i problemi intrattabili, l'autore risponde negativamente alla domanda equivalente per la classe U-complete: la classe dei linguaggi ricorsivi ($REC$) non è uguale alla classe dei linguaggi ricorsivamente enumerabili ma non ricorsivi ( $RE \setminus REC$ ). Questo conferma che esistono problemi indecidibili che non possono essere ridotti a problemi decidibili.

4. Risultati Principali

Dimostrazione Semplificata: È stata fornita una prova più breve e diretta dell'indeducibilità del Entscheidungsproblem basata sulla cardinalità di Cantor.
Gerarchia Infinita: È stata ipotizzata e supportata la presenza di una gerarchia infinita di classi di complessità per i problemi indecidibili, basata sulla gerarchia degli infiniti di Cantor (numeri ordinali e cardinali), superando la semplice distinzione binaria tra "decidibile" e "indecidibile".
Corollario di Cardinalità: È stato confermato che il numero di problemi indecidibili (cardinalità dei numeri reali, $\aleph_1$ o superiore) è strettamente maggiore del numero di problemi decidibili (cardinalità dei numeri naturali, $\aleph_0$ ).
Ridefinizione dei Limiti: Il paper suggerisce che l'informatica tradizionale si concentra eccessivamente sui problemi decidibili e polinomiali, trascurando la vasta maggioranza dei problemi che sono indecidibili ma potenzialmente gestibili tramite approcci probabilistici, approssimativi o ipercomputazionali.

5. Significato e Implicazioni

Questo lavoro ha un significato profondo per la teoria dell'informatica e la filosofia della computazione:

Riconoscimento Storico: Ribalta la narrazione storica ponendo Georg Cantor come figura centrale, al pari di Turing, nella fondazione dell'informatica.
Nuova Prospettiva sulla Indecidibilità: Sposta il focus dalla "impossibilità assoluta" di risolvere un problema alla "misura" della sua indecidibilità. Questo apre la strada a tecniche di risoluzione approssimata, probabilistica o basata su input specifici per problemi teoricamente indecidibili.
Sviluppo di Nuovi Modelli: Legittima e formalizza la ricerca sui modelli Super-Turing (ipercomputazionali), suggerendo che l'evoluzione dell'informatica (AI, calcolo quantistico, sistemi adattivi) richiederà necessariamente di superare i limiti della Macchina di Turing classica.
Struttura Teorica: Fornisce il primo framework esplicito per classificare i problemi indecidibili in classi di complessità (U, D, H), offrendo un terreno di ricerca per futuri studi sulla gerarchia degli infiniti computazionali.

In sintesi, il paper non solo onora il contributo di Cantor, ma propone un'evoluzione necessaria della teoria della computabilità, passando da una visione binaria (risolvibile/non risolvibile) a una visione sfumata e gerarchica basata su probabilità, cardinalità e modelli di calcolo avanzati.