19 set 2025·8 min
Alan Turing e i limiti della computazione spiegati
Scopri le idee chiave di Alan Turing—algoritmi, indecidibilità e decifrazione—e come hanno plasmato l'informatica moderna, la sicurezza e le basi dell'IA.
Scopri le idee chiave di Alan Turing—algoritmi, indecidibilità e decifrazione—e come hanno plasmato l'informatica moderna, la sicurezza e le basi dell'IA.
La maggior parte di quello che fai con un telefono o un laptop—cercare sul web, inviare messaggi, sbloccare account, chiedere aiuto a un assistente—si basa su domande che Alan Turing ha contribuito a chiarire: Cos'è il calcolo? Cosa può fare un computer in principio? E dove sono i limiti?
Turing è importante oggi perché non si è limitato a inventare tecniche intelligenti; ha definito le regole del gioco. L'ingegneria del software moderna, la sicurezza informatica e la ricerca sull'IA ereditano tutte quelle regole, che la gente lo menzioni o no.
Primo: calcolo. Il modello semplice di Turing (la “macchina di Turing”) ci dà un modo chiaro per parlare di programmi, dati e algoritmi. È il motivo per cui possiamo confrontare dispositivi molto diversi—portatili, server, smartphone—come varianti della stessa idea di base: una macchina generale che esegue istruzioni.
Secondo: sicurezza. Durante la Seconda Guerra Mondiale Turing trasformò la decifrazione in una disciplina sistematica e orientata all'ingegneria. Quello stesso approccio è presente in crittografia e sicurezza moderna: il successo dipende dal capire cosa gli aggressori possono calcolare e quanto gli costa.
Terzo: intelligenza artificiale. Turing pose una domanda pratica che ancora plasma i dibattiti sull'IA: Come riconosceremmo un comportamento intelligente dall'esterno? Il “Test di Turing” resta un punto di riferimento, anche se la gente discute i suoi limiti.
Questa guida mantiene la matematica leggera e l'intuizione al centro. Il tema principale è semplice: i computer sono incredibilmente potenti, ma non sono magici. Alcuni problemi sono impossibili da risolvere con qualsiasi programma, e molti altri lo sono solo a costi tali da renderli inutilizzabili nella pratica. Capire quei confini ti aiuta a valutare meglio le affermazioni tecnologiche e a scegliere gli strumenti giusti.
Alan Turing (1912–1954) viene spesso presentato attraverso racconti drammatici, ma il modo più utile per capirlo è attraverso ciò che ha costruito e dimostrato. Era un matematico che ha trattato le domande su “cosa può essere calcolato” come problemi precisi, e poi ha seguito le risposte fino alle macchine reali.
Il suo articolo del 1936, On Computable Numbers, fece due cose durature: descrisse un modello astratto di calcolo (oggi chiamato macchina di Turing) e lo usò per mostrare che alcune domande sui programmi non possono essere risolte in generale. Non era fantascienza; era un argomento accurato sui limiti della logica e del calcolo.
Durante la Seconda Guerra Mondiale Turing lavorò a Bletchley Park sulla crittanalisi—trovare modi per decifrare messaggi cifrati. Le narrazioni popolari a volte suggeriscono che abbia “rotto l'Enigma da solo” o “inventato il computer” in una notte. La realtà è più interessante: fu un contributore chiave in un grande sforzo, progettando metodi e aiutando a definire strumenti elettromeccanici che trasformarono l'intuizione matematica in lavoro operativo e ripetibile.
La forza di Turing stava nel passare dalle dimostrazioni alla pratica. Poteva ragionare su una macchina idealizzata sulla carta, poi aiutare a progettare procedure e vincoli hardware che rendevano un sistema reale più veloce e affidabile. Questa miscela—pensiero formale più implementazione pratica—è un modello per l'informatica moderna.
Le idee di Turing riecheggiano in molte aree: le basi dell'informatica moderna (calcolabilità e decidibilità), il pensiero iniziale sulla sicurezza (crittanalisi sistematica) e i successivi dibattiti sull'intelligenza artificiale. Anche quando si discute con lui, spesso si usa il quadro che ha aiutato a definire.
Un algoritmo è semplicemente una serie chiara di passi per ottenere un risultato. Non è necessariamente “da matematica” o anche legato al computer—è solo un metodo che puoi seguire in modo affidabile.
Pensa a una ricetta base per fare il tè:
Questa è un'algoritmo: passi non ambigui, in ordine, con un risultato prevedibile.
Le macchine early erano spesso a scopo singolo: progettate per fare un lavoro preciso, come tessere, calcolare tavole o cifrare/decifrare messaggi con un sistema specifico. Se volevi fare qualcosa di diverso, di solito serviva un'altra macchina o una riconfigurazione importante.
Un computer general-purpose è diverso. È progettato per seguire molti algoritmi diversi, a seconda delle istruzioni che gli dai. L'hardware rimane lo stesso; ciò che cambia è il programma.
Il software è, in fondo, un modo di scrivere algoritmi così che una macchina li esegua con precisione. Invece di “aspettare 3–5 minuti”, un programma potrebbe dire “aspetta 240 secondi”. Invece di “se vuoi zucchero”, potrebbe dire “se l'utente ha selezionato zucchero, aggiungi un cucchiaino.”
Questo spostamento—trattare le istruzioni come qualcosa che la macchina può memorizzare, leggere ed eseguire—ha preparato il terreno per il calcolo moderno: un dispositivo, innumerevoli compiti, tutti guidati da algoritmi.
Vedi l'idea general-purpose in strumenti di “vibe-coding”: invece di scrivere manualmente ogni passo, descrivi l'obiettivo e il sistema traduce quella specifica in software eseguibile.
Per esempio, Koder.ai ti permette di costruire applicazioni web, backend e mobile tramite un'interfaccia chat—poi esportare il codice sorgente, distribuire e ospitare. In fondo si ritorna all'inquadramento di Turing: il sistema genera programmi (algoritmi + dati + controllo) che devono comunque funzionare entro vincoli reali come tempo, memoria, sicurezza e correttezza.
Una macchina di Turing è meglio intesa come esperimento mentale: una “macchina immaginaria” volutamente semplice progettata per catturare cosa significa calcolare qualcosa passo dopo passo. Turing non voleva necessariamente costruire questo dispositivo; voleva definire il calcolo in modo abbastanza preciso da poter dimostrare cose su di esso.
Immagina una striscia di carta infinita (il nastro) divisa in celle. Ogni cella può contenere un simbolo—come vuoto, 0 o 1. Una testina di lettura è sopra una cella alla volta.
Aggiungi una piccola scheda di istruzioni che dice alla testina cosa fare. La macchina è sempre in uno di un numero finito di stati (pensa a “modalità”, come cerca il prossimo numero o finito).
Per ogni combinazione (stato corrente + simbolo sulla cella) c'è una regola che dice:
Questo è tutto—eppure, con le regole giuste, la macchina può eseguire qualsiasi computazione che riconosceremmo come algoritmo.
La macchina di Turing dà una definizione nitida di calcolo: un insieme finito di regole meccaniche che agiscono su uno spazio di memoria. È un modello matematico, non un progetto hardware.
Poiché il modello è così minimale, è potente per le dimostrazioni: se qualcosa non può essere calcolato neanche da questa macchina idealizzata, non può esserlo neppure dai computer ordinari.
I programmi moderni non assomigliano a un nastro e una testina, ma la mappatura è semplice: la memoria contiene dati, il flusso di controllo cambia stato, e le istruzioni trasformano simboli. Anche le “stored procedure” nei database rientrano nello stesso schema: regole fisse che leggono dati, li aggiornano e procedono per passi—calcolo come processo ripetibile e guidato da regole.
Alcune domande sui programmi sembrano avere risposte meccaniche e pulite. Turing mostrò che per una classe importante di domande quella speranza è impossibile—non perché non siamo abbastanza intelligenti, ma perché la risposta non può esistere come metodo generale.
Un problema è decidibile se esiste una procedura (un algoritmo) che termina sempre e risponde correttamente SÌ/NO per ogni input.
Un problema è indecidibile se nessun algoritmo può farlo per tutti i casi. Potresti risolvere molte istanze, ma non costruire un singolo metodo che sia sempre giusto e che termini sempre.
Il problema dell'arresto chiede:
Dato un programma qualsiasi e il suo input, possiamo sempre determinare se il programma si fermerà (arresta) o continuerà a funzionare per sempre?
Turing dimostrò che la risposta è no. Non esiste un controllore universale che, per qualsiasi programma e qualsiasi input, predica correttamente l'arresto.
Una volta accettato che “predire la terminazione per tutti i programmi” è impossibile, molti strumenti di analisi perfetta diventano irrealizzabili.
Un “rivelatore universale di bug” significherebbe: dagli qualsiasi programma e dire se contiene un certo tipo di bug. Ma molte proprietà di bug si possono ricodificare come “il programma raggiunge mai un certo stato?”—che può codificare il problema dell'arresto.
Quindi gli strumenti reali devono scendere a compromessi: possono essere incompleti (mancare alcuni bug), dare falsi avvisi o funzionare solo per tipi ristretti di programmi.
Prendi la proprietà: “Questo programma non entra mai in un loop infinito.” Se uno strumento potesse verificarlo perfettamente per tutti i programmi, risolverebbe anche il problema dell'arresto. Poiché quello è indecidibile, non esiste una verifica perfetta in generale.
È per questo che linters, type checker e analizzatori statici sono utili—ma non sono miracoli.
Una lezione chiave dopo Turing è che “computabile” non significa “utile”. Alcuni compiti sono possibili in principio—esiste un programma che si fermerà—ma ancora irrealistici perché il programma richiederebbe troppo tempo o troppa memoria.
Immagina un programma che risolve un rompicapo provando tutte le combinazioni. Funzionerà prima o poi, ma se il numero di combinazioni cresce più velocemente del miglioramento dei computer, “prima o poi” può essere più lungo dell'età dell'universo.
Questo è il lato pratico dei limiti del calcolo: non se esiste una soluzione, ma se quella soluzione rientra nei vincoli reali.
Ogni programma consuma risorse:
Una differenza che sembra piccola sulla carta può essere enorme nella realtà. Un metodo che raddoppia il lavoro quando l'input raddoppia può restare gestibile; uno che lo quadraplica (o peggio) diventa rapidamente inutilizzabile.
Gli informatici raggruppano i problemi in base a come crescono le risorse richieste. Senza matematica pesante, l'idea è semplice:
Questi raggruppamenti sono spesso discussi come classi di complessità—etichette che separano problemi che ci aspettiamo di risolvere efficacemente da quelli che no.
In crittografia, la difficoltà è spesso una caratteristica. Molti sistemi di sicurezza si basano su compiti facili da eseguire in un verso (chiudere) ma estremamente costosi da invertire senza una chiave (aprire).
Quindi, mentre i limiti della computazione restringono ciò che possiamo fare rapidamente, aiutano anche a spiegare perché la sicurezza moderna può funzionare—anche contro avversari con macchine potenti.
La crittoanalisi è la pratica di analizzare messaggi cifrati per recuperarne il significato senza conoscere la chiave. Durante la Seconda Guerra Mondiale questo lavoro era cruciale: le comunicazioni cifrate portavano piani e ordini su scala tale che la decifrazione manuale era troppo lenta.
Se non puoi leggere i messaggi in tempo, non puoi agire—quindi velocità e ripetibilità divennero importanti quanto l'ingegno.
I buoni cifrari cercano di far sembrare i messaggi rumore casuale. La crittoanalisi cerca i modi in cui la realtà trapela: pattern linguistici, formati ripetuti, header prevedibili o abitudini umane nell'uso dei sistemi. Invece di considerare ogni messaggio come un enigma isolato, i decifratori lo trattavano come un problema di dati.
Un approccio pratico combina tre ingredienti:
Qui emerge il pensiero da informatica precoce: definire il problema con precisione, ridurlo a passi e costruire sistemi che possano eseguire quei passi più velocemente di una persona.
La sicurezza moderna inizia ancora con la stessa mentalità: assumere un avversario intelligente, persistente e con vincoli. I difensori formulano assunzioni (segretezza, gestione delle chiavi, comportamento degli utenti, integrità del dispositivo) e gli attaccanti cercano il più debole.
È anche un mondo di compromessi. Crittografia più forte può complicare l'uso, più monitoraggio può sollevare problemi di privacy, rilevazione più veloce può aumentare i falsi allarmi.
L'epoca di Turing ricorda una lezione duratura: la sicurezza non è solo “migliori algoritmi”, ma sistemi, incentivi e come le persone li usano davvero.
Turing lavorò in un'epoca in cui i messaggi erano questione di vita o di morte—e quella pressione si mappa bene sugli obiettivi di sicurezza odierni.
La sicurezza di solito si riduce a poche idee semplici:
L'era di Turing ha mostrato che raramente ottieni questi aspetti “gratis”. Bisogna progettarli e testarli sotto pressione.
La crittografia moderna si fonda sulla durezza matematica: problemi facili in un verso ma molto difficili da invertire senza il segreto (ad esempio fattorizzare numeri grandi). Questa è la “serratura matematica”.
Ma la chiave è spesso il punto debole reale. La gestione delle chiavi significa generarle in modo sicuro, conservarle in modo che non possano essere copiate, ruotarle quando serve e revocarle rapidamente se compromesse.
Algoritmi brillanti possono essere resi inutili da una chiave trapelata, una password riutilizzata o un server non aggiornato.
Gli attaccanti si adattano. La sicurezza raramente è perfezione—è riduzione del rischio: rendere gli attacchi costosi, rilevabili e limitati nei danni.
Oggi gli aggressori automatizzano operazioni che richiedevano squadre specializzate: indovinare password, phishing, scannerizzare milioni di sistemi. Alla scala di Internet, piccoli errori diventano grandi incidenti—spazi di storage mal configurati, credenziali copiate o un dipendente che clicca il link sbagliato.
La lezione duratura è pratica: abbina buona matematica a operazioni disciplinate e assumiti sempre che il sistema sarà attaccato continuamente.
Quando si parla di cosa “può” fare un computer, di solito si intende qualcosa di più preciso che “qualsiasi cosa tu possa immaginare”. La tesi di Church–Turing è la regola pratica che tracci quel confine: un compito è calcolabile se esiste una procedura passo‑per‑passo (un algoritmo) che termina con la risposta corretta e che quella procedura potrebbe essere eseguita da una macchina di Turing.
Nonostante il nome, non è qualcosa che si può provare nel senso matematico abituale—perché collega un modello formale (macchina di Turing) a un'idea informale (“qualsiasi metodo efficace”). È però sostenuta da decenni di evidenza: ogni volta che si è proposto un nuovo modello ragionevole di calcolo (linguaggi, circuiti, automi cellulari, CPU moderne), si è scoperto che coincidono sugli stessi problemi calcolabili.
La tesi ci permette di confrontare computer e linguaggi molto diversi senza perderci nei dettagli. Se due sistemi sono “Turing-completi”, allora—dato abbastanza tempo e memoria—possono calcolare gli stessi tipi di funzioni.
Questo è il motivo per cui il tuo telefono, un portatile e un server cloud differiscono principalmente in velocità, costi e scala, non nei tipi fondamentali di problemi che possono risolvere.
Church–Turing non promette che ogni domanda abbia una soluzione algoritmica. Alcuni problemi sono non calcolabili (come il problema dell'arresto), cioè nessun programma può rispondere correttamente in tutti i casi.
E anche quando qualcosa è calcolabile, può essere così lento da risultare inutile nella pratica—una questione coperta dalla teoria della complessità.
Turing notò che la domanda “Le macchine possono pensare?” è sfuggente. “Pensare” può significare provare emozioni, comprendere, essere creativi, avere autocoscienza o semplicemente produrre buone risposte. Se non concordiamo su una definizione, non possiamo costruire un test chiaro.
Turing propose di sostituire la domanda vaga con una pratica: può una macchina comportarsi in modo intelligente in conversazione?
Nella versione classica, un giudice umano chatta (tipicamente via testo) con due partecipanti nascosti: un umano e una macchina. Il giudice può fare qualsiasi domanda e poi deve decidere chi è chi. Se il giudice non riesce a distinguere in modo affidabile, si dice che la macchina ha superato il test.
È meno una prova di intelligenza interna e più un obiettivo misurabile: performance indistinguibile in una specifica interazione.
Il Test di Turing si concentra sul comportamento esterno in un contesto limitato. È un vantaggio (è osservabile), ma anche un limite:
Gli chatbot di oggi possono sembrare sorprendentemente umani in scambi brevi, il che rende l'idea di Turing nuovamente pertinente. Ma mette anche in luce i limiti della valutazione: i benchmark possono essere “brogliati” con stile e familiarità con i formati di test, e un sistema che chatta bene può comunque fallire su accuratezza fattuale, ragionamento a lungo termine o coerenza.
La lezione duratura non è che la conversazione sia la misura definitiva dell'intelligenza, ma che servono test attenti e trasparenti e onestà su ciò che ogni test misura davvero.
I sistemi di IA sembrano aperti a molti usi, ma comunque eseguono programmi—e quindi ereditano gli stessi confini che Turing ha chiarito. Questi limiti sono importanti per decidere cosa è realisticamente raggiungibile, cosa sarà costoso e cosa è impossibile in principio.
Molti compiti di IA sono calcolabili ma costosi: addestrare un modello, cercare una soluzione o ottimizzare un piano può richiedere enormi quantità di tempo ed energia. Più dati e hardware più veloce aiutano—talvolta in modo drammatico.
Altri obiettivi scontrano barriere più profonde. Alcune domande non possono essere risposte da una procedura generale per tutti i casi (nello spirito dell'indecidibilità). Per esempio, “dimostra che questo sistema arbitrario non fallirà mai” non è solo difficile; per classi ampie di sistemi non può essere completamente automatizzato senza eccezioni e assunzioni.
Anche quando un problema è calcolabile, può essere intrattabile: il tempo richiesto cresce così rapidamente che “aggiungere più dati” smette di funzionare. Questo appare in pianificazione a lungo termine, verifiche esaustive e certi tipi di ragionamento nel caso peggiore.
L'IA può approssimare o indovinare, ma le garanzie diventano costose.
Poiché le garanzie perfette sono limitate, la valutazione diventa gestione dell'incertezza: misurare tassi di errore, stress-testare scenari rari e tracciare i modi in cui il sistema fallisce nel tempo. I bug più difficili spesso vivono nei casi limite che non compaiono nei benchmark tipici.
Anche la sicurezza è modellata da questi limiti. Non puoi filtrare tutto il comportamento dannoso solo con regole, né verificare completamente ogni interazione. Prompt injection, avvelenamento dei dati e uso improprio ricordano che le difese devono essere stratificate: monitoraggio, controllo degli accessi, red‑teaming e progettazione accurata del sistema—not una singola prova perfetta.
Il lavoro di Turing viene spesso insegnato come storia, ma è più utile come insieme di “regole della strada” per pensare chiaramente a cosa i computer possono (e non possono) fare.
1) Calcolabilità (cosa è possibile in assoluto). La macchina di Turing dà un modo chiaro per parlare di quali problemi possono essere risolti da qualsiasi procedura passo‑per‑passo. Il problema dell'arresto è il risultato principale qui: alcune domande sui programmi non sono risolvibili in generale.
2) Complessità (cosa è possibile con tempo e risorse reali). Molti compiti sono calcolabili ma diventano inutilizzabili quando gli input crescono—perché tempo, memoria o energia esplodono. Questo è il motivo per cui “funziona su un esempio piccolo” può comunque significare “non funzionerà nel mondo reale”.
3) Sicurezza (come i limiti possono proteggerci). La crittografia moderna si basa su limiti pratici: non che rompere un sistema sia impossibile, ma che sia troppo costoso o lungo per essere fatto su scala. Il lavoro di Turing sulla decifrazione ci ricorda che gli attaccanti usano matematica, ingegneria e scorciatoie operative—not solo forza bruta.
Quando affronti un problema computazionale, fatti tre domande in ordine:
Se vuoi approfondire, i prossimi argomenti utili sono:
Il progresso nel calcolo è reale—hardware più veloce, algoritmi migliori, strumenti di sicurezza più forti. I limiti sono reali anch'essi, e capirli è un vantaggio pratico: ti aiuta a scegliere lo strumento giusto, fissare aspettative realistiche ed evitare di farti ingannare da promesse che ignorano la matematica.
Una macchina di Turing è un modello astratto e minimale di calcolo: un nastro (memoria), una testina di lettura/scrittura e un insieme finito di regole (stati). È importante perché offre un modo preciso per discutere cosa può fare “un programma” in principio—indipendentemente dall'hardware o dal linguaggio usato.
La tesi di Church–Turing afferma che qualsiasi metodo effettivo, passo dopo passo, di calcolo può essere simulato da una macchina di Turing. Non è un teorema formale dimostrabile in senso matematico perché collega un'idea informale («metodo effettivo») a un modello formale; è però supportata da decenni di evidenza: tutti i modelli ragionevoli proposti si sono rivelati equivalenti rispetto ai problemi calcolabili.
“Calcolabile” significa che esiste un algoritmo che produce la risposta corretta (prima o poi). “Efficientemente calcolabile” significa che lo fa con tempo e memoria pratici quando l'input cresce. Molti problemi sono calcolabili ma diventano inutilizzabili perché richiedono risorse che esplodono con la dimensione dei dati.
Il problema dell'arresto chiede se esista un algoritmo universale che, dato un programma qualsiasi e il suo input, possa sempre decidere se quel programma si fermerà o continuerà a girare per sempre. Turing dimostrò che una tale procedura universale non può esistere. Concretamente, è la ragione per cui non possiamo avere un metodo infallibile che predice la terminazione per ogni programma.
Perché molte proprietà di bug possono essere ricodificate come “il programma raggiunge mai questo stato?”, che può incorporare il problema dell'arresto. Quindi uno strumento universale che cattura ogni bug richiederebbe la soluzione del problema dell'arresto, che è impossibile. Gli strumenti reali quindi fanno compromessi:
Per questo l'analisi statica è preziosa ma non magica.
La complessità riguarda come le risorse richieste crescono con la dimensione dell'input—principalmente tempo e spazio. Un piccolo cambiamento nel tasso di crescita può fare la differenza: raddoppiare il lavoro rispetto a quadruplicarlo è una differenza enorme a grande scala. Questo spiega perché una soluzione che sembra OK su un esempio piccolo può fallire nel mondo reale.
La crittografia moderna si basa spesso su problemi facili da risolvere se si possiede la chiave ma estremamente costosi da risolvere senza di essa. Questo “divario di costo” è in genere un'assunzione di complessità: un attaccante potrebbe calcolare la soluzione in linea di principio, ma non entro un tempo o un budget realistico. Quindi i limiti diventano parte del progetto di sicurezza, non solo un ostacolo.
Il lavoro di decifrazione della II Guerra Mondiale ha modellato un approccio ancora valido: combinare struttura, statistica e automazione.
Oggi si applica la stessa mentalità, ma su scala Internet.
Il Test di Turing valuta se una macchina può produrre un comportamento conversazionale simile a quello umano in un ambiente definito. È utile come benchmark comportamentale osservabile, ma non misura direttamente comprensione, coscienza o veridicità. Può premiare la persuasività e lo stile più che l'accuratezza.
I sistemi di IA ereditano limiti di calcolabilità e di complessità: non si possono ottenere garanzie universali e perfette su ogni comportamento, e alcuni obiettivi di verifica sono indecidibili per classi molto ampie di sistemi. Per questo la pratica si concentra sulla gestione del rischio: test, monitoraggio, difese stratificate, red‑teaming e assunzioni chiare su cosa il sistema può e non può fare.