Appunti · InformaticaIT · Maturità

Principi teorici della computazione

La teoria della computazione studia che cosa può essere calcolato automaticamente, con quali modelli astratti di calcolo (automi a stati finiti, macchina di Turing) e a quale costo, fissando i limiti invalicabili dell'elaboratore. Si tratta di un approfondimento culturale che inquadra algoritmi e programmazione entro la loro cornice teorica. « Approfondimento — fuori dall'Esame di Stato »: l'argomento non costituisce un obiettivo direttamente valutato nella seconda prova, ma offre la chiave di lettura concettuale dell'intera disciplina.

5 sezioni~26 min di lettura3 competenzeLivello Standard 2 · Approfondimento 3Verificato · 07/2026

T·141414 / 14

Profilo d’esame

Approfondimento — fuori dall'Esame di Stato: cogliere i fondamenti teorici dell'informatica e i limiti di ciò che è calcolabileDistinguere tra problemi risolubili in modo efficiente e problemi computazionalmente difficiliInquadrare gli algoritmi e la programmazione entro la cornice teorica della computazione

Operatori:spiegadescriviclassificadistinguianalizzagiustificaillustraconfronta

livello base

È sufficiente padroneggiare a livello intuitivo le idee-chiave: la nozione di calcolabilità, la macchina di Turing come modello universale, l'esistenza di problemi indecidibili e la distinzione tra problemi trattabili e intrattabili.

livello avanzato

Nell'indirizzo Scienze Applicate si curano gli automi a stati finiti come riconoscitori di linguaggi, la diagonalizzazione che prova l'indecidibilità della terminazione e la struttura logica della questione P vs NP (verifica polinomiale, riduzioni, NP-completezza).

Profondità

Testo

Contenuti · 5 sezioni

Principi teorici della computazione

Calcolabilità e modelli astratti di calcolo#

StandardOSA-informatica-fondamenti-teoria-computazioneConcetto di calcolabilitàModelli astratti di calcolo

I modelli di calcolo equivalenti e la tesi di Church-Turing

Fig. 1Tesi di Church-Turing: «calcolabile» = computabile da una macchina di Turing. I tre modelli di calcolo (macchina di Turing, lambda-calcolo, funzioni ricorsive) sono equivalenti.

La teoria della computazione nasce da una domanda sorprendentemente semplice e profonda: esiste un metodo meccanico, una procedura puramente formale e priva di intuizione, che permetta di risolvere un dato problema? Prima ancora di chiedersi quanto sia veloce un algoritmo, ci si chiede se l'algoritmo esista affatto. Una funzione si dice « calcolabile » (o computabile) quando esiste un procedimento finito e ben definito che, a partire dai dati di ingresso, produce sempre il risultato corretto in un numero finito di passi.

Per dare risposta rigorosa a questa domanda occorre fissare che cosa significhi « procedimento meccanico ». Negli anni Trenta del Novecento diversi studiosi proposero modelli formali di calcolo apparentemente molto diversi: la macchina di Turing di Alan Turing (1936), il lambda-calcolo di Alonzo Church e le funzioni ricorsive di Gödel e Kleene. Il fatto notevole è che tutti questi modelli si rivelarono equivalenti: ciò che è calcolabile in uno è calcolabile in tutti gli altri.

Questa equivalenza è riassunta dalla « tesi di Church-Turing »: ogni funzione che sia intuitivamente calcolabile mediante un procedimento meccanico è calcolabile da una macchina di Turing. Non è un teorema dimostrabile — perché lega una nozione intuitiva (« calcolabile in modo meccanico ») a una nozione formale (« calcolabile da una macchina di Turing ») — ma è una congettura universalmente accettata, mai smentita in quasi un secolo, che fissa il confine della calcolabilità.

Un modello di calcolo è un'astrazione: ignora i dettagli fisici di un computer reale (transistor, linguaggio, memoria limitata) per isolare l'essenza del calcolo. Studiare i modelli astratti consente di dimostrare proprietà valide per QUALSIASI calcolatore, presente o futuro, indipendentemente dalla tecnologia: i limiti che scopriremo non dipendono dalla potenza della macchina, ma dalla logica stessa del calcolo.

Esempio svolto

Riconoscere se una procedura è un algoritmo (e quindi calcolabile)

Si consideri la procedura: « per stabilire se un numero naturale n è primo, prova a dividerlo per ogni intero d con 2 ≤ d ≤ n−1; se nessuna divisione è esatta, n è primo ». Si stabilisca, motivando, se questa procedura definisce un algoritmo e quindi una funzione calcolabile.

Finitezza
Per ogni n l'insieme dei divisori da provare è finito (da 2 a n−1), quindi il numero di passi è finito: la procedura termina sempre.
Determinismo
Ogni passo (la divisione e il confronto del resto con zero) è univocamente definito: dato lo stesso n si ottiene sempre lo stesso esito.
Generalità
La procedura funziona per qualsiasi naturale n ≥ 2, non per un singolo valore particolare.
Eseguibilità
Ogni operazione (divisione intera, confronto) è elementare e meccanicamente eseguibile.
Conclusione
Soddisfatte le quattro proprietà, la procedura è un algoritmo; di conseguenza la funzione « n è primo? » è calcolabile (e, come tutte le funzioni totali ben definite, computabile da una macchina di Turing).

Risultato: La procedura è un algoritmo: la primalità è una proprietà decidibile e quindi calcolabile.

Errori frequenti

Confondere « calcolabile » con « calcolabile velocemente »: la calcolabilità riguarda l'esistenza di un procedimento finito, non la sua efficienza. Un problema può essere calcolabile ma richiedere tempi proibitivi.
Ritenere la tesi di Church-Turing un teorema dimostrato: è una congettura (largamente accettata), perché collega una nozione intuitiva a una formale.

Approfondimento

Un argomento sorprendente mostra che i problemi non calcolabili non solo esistono, ma sono la stragrande maggioranza. Ogni programma è, in ultima analisi, una stringa finita di simboli: dunque i programmi possibili sono un'infinità «numerabile» (si possono mettere in fila e contare, come i numeri naturali). Le funzioni dai numeri naturali ai numeri naturali, invece, sono un'infinità «non numerabile», strettamente più grande, come dimostrò Georg Cantor con l'argomento diagonale. Poiché i programmi sono numerabili e le funzioni no, non può esistere un programma per ogni funzione: la maggior parte delle funzioni è, per pura ragione di cardinalità, non calcolabile — il problema della terminazione ne sarà un esempio concreto e «naturale». Questo chiarisce anche il valore della tesi di Church-Turing: fissando un unico confine per tutti i modelli equivalenti (macchina di Turing, lambda-calcolo, funzioni ricorsive e, per estensione, ogni linguaggio di programmazione reale), essa rende la calcolabilità una proprietà robusta, indipendente dal formalismo scelto. Un linguaggio si dice Turing-completo quando può simulare una macchina di Turing, e quasi tutti i linguaggi di uso comune lo sono: ciò significa che condividono esattamente lo stesso potere di calcolo — e gli stessi limiti invalicabili. La potenza di un linguaggio, al di là della comodità sintattica, non va dunque oltre quella di questo semplicissimo modello astratto degli anni Trenta.

Ripasso attivo

Spiega che cosa significa che una funzione è « calcolabile » e illustra il contenuto della tesi di Church-Turing, chiarendo perché essa non è un teorema ma una congettura. Indica almeno due modelli di calcolo che si sono rivelati equivalenti.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Automi a stati finiti e macchina di Turing#

ApprofondimentoOSA-informatica-fondamenti-teoria-computazioneAutomi a stati finiti e macchina di Turing (cenni)

Struttura di una macchina di Turing: nastro, testina e unità di controllo

Fig. 2La testina (sulla cella 3) legge/scrive un simbolo; l’unità di controllo applica la funzione di transizione δ(stato, letto) = (scrivi, muovi L/R, nuovo stato). Il nastro è una memoria infinita.

L'automa a stati finiti è il più semplice modello astratto di calcolo: una macchina dotata di un numero finito di « stati » che legge una sequenza di simboli in ingresso, un simbolo alla volta, e per ciascuno transita da uno stato all'altro secondo una funzione di transizione fissata. Non possiede memoria oltre allo stato corrente: la sua « conoscenza » del passato è interamente riassunta dallo stato in cui si trova.

Un automa a stati finiti è formalmente una quintupla composta dall'insieme finito degli stati, dall'alfabeto di ingresso, dalla funzione di transizione, dallo stato iniziale e dall'insieme degli stati di accettazione (stati finali). L'automa « accetta » una stringa se, partendo dallo stato iniziale e consumando tutti i simboli, termina in uno stato finale; l'insieme delle stringhe accettate è il linguaggio riconosciuto dall'automa (i linguaggi regolari). Gli automi modellano ascensori, distributori automatici, semafori, analizzatori lessicali.

Il limite degli automi a stati finiti è proprio l'assenza di memoria illimitata: non possono, ad esempio, riconoscere che il numero di parentesi aperte uguagli quello delle chiuse per una sequenza arbitrariamente lunga, perché ciò richiederebbe di « contare » senza limite. Per superare questo limite serve un modello più potente, dotato di memoria illimitata: la macchina di Turing.

La macchina di Turing è il modello universale di calcolo. È costituita da un nastro infinito diviso in celle (la memoria), una testina che legge e scrive un simbolo nella cella corrente e può spostarsi di una cella a sinistra o a destra, un insieme finito di stati e una funzione di transizione che, in base allo stato corrente e al simbolo letto, decide quale simbolo scrivere, in quale direzione muoversi e in quale nuovo stato passare. Nonostante l'estrema semplicità, una macchina di Turing può calcolare tutto ciò che è calcolabile: la « macchina di Turing universale » è in grado di simulare qualsiasi altra macchina di Turing, ed è l'antenato teorico del computer programmabile.

Automa a stati finiti che accetta le stringhe binarie con un numero pari di 1

Fig. 3q₀ (pari) è lo stato accettante; leggere 1 commuta fra i due stati, leggere 0 lascia lo stato invariato. L’automa accetta le stringhe binarie con un numero pari di 1.

Esempio svolto

Far funzionare un automa a stati finiti su una stringa

Dato l'automa a due stati che riconosce le stringhe binarie con un numero PARI di simboli « 1 » (stato iniziale e finale q0 = numero pari di 1 letti finora; q1 = numero dispari; leggere « 1 » commuta lo stato, leggere « 0 » lo lascia invariato), si determini, traccia per traccia, se la stringa « 1011 » viene accettata.

Stato iniziale
L'automa parte in q0 (zero « 1 » letti: numero pari).
Legge 1
Da q0, il simbolo « 1 » commuta lo stato: q0 → q1 (un « 1 » letto, dispari).
Legge 0
Da q1, il simbolo « 0 » lascia invariato lo stato: q1 → q1.
Legge 1
Da q1, « 1 » commuta: q1 → q0 (due « 1 » letti, pari).
Legge 1
Da q0, « 1 » commuta: q0 → q1 (tre « 1 » letti, dispari).
Esito
Consumata tutta la stringa, l'automa è in q1, che NON è stato finale: la stringa non è accettata. Coerentemente, « 1011 » contiene tre « 1 » (numero dispari).

Risultato: La stringa « 1011 » termina in q1 e quindi NON è accettata: contiene un numero dispari di « 1 ».

Errori frequenti

Pensare che il nastro « infinito » significhi una memoria fisicamente illimitata e realizzabile: è un'idealizzazione matematica che serve a non porre limiti artificiosi al calcolo, non un componente costruibile.
Confondere il numero finito di stati con un limite della macchina di Turing: gli stati sono finiti, ma la memoria (il nastro) è illimitata — è proprio questo a renderla universale, a differenza dell'automa a stati finiti.

Approfondimento

Fra l'automa a stati finiti e la macchina di Turing esiste tutta una gerarchia di modelli di potenza crescente, la gerarchia di Chomsky, che lega ogni classe di macchine a una classe di grammatiche e di linguaggi. Alla base ci sono gli automi a stati finiti, che riconoscono i linguaggi regolari (descritti dalle espressioni regolari): perfetti per l'analisi lessicale, il primo stadio di un compilatore che spezza il testo in token. Aggiungendo all'automa una pila (una memoria LIFO) si ottiene l'automa a pila (pushdown automaton), che riconosce i linguaggi liberi dal contesto (context-free): è proprio la pila a permettergli di «contare» le parentesi aperte e chiuse, compito impossibile per l'automa a stati finiti, ed è il modello dell'analisi sintattica (il parser) che verifica la struttura grammaticale di un programma. Salendo ancora si incontrano gli automi limitati linearmente e i linguaggi dipendenti dal contesto, e infine, al vertice, la macchina di Turing, che riconosce i linguaggi ricorsivamente enumerabili, i più generali. Questa scala non è un'astrazione fine a sé stessa: spiega perché la sintassi dei linguaggi di programmazione si descriva con grammatiche libere dal contesto (in notazione BNF) e perché un compilatore sia organizzato in stadi di potenza crescente, dal lessicale al sintattico al semantico. Ogni gradino aggiunge memoria, e con la memoria potere di calcolo — la stessa lezione, portata al suo estremo teorico, che distingueva l'array dalla pila e la pila dalla macchina universale.

Ripasso attivo

Descrivi la struttura di una macchina di Turing elencandone i componenti e spiegando il ruolo della funzione di transizione. Indica quindi una differenza essenziale rispetto a un automa a stati finiti, con un esempio di compito che l'automa NON può svolgere.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Problemi decidibili e indecidibili#

ApprofondimentoOSA-informatica-fondamenti-teoria-computazioneProblemi decidibili e indecidibili; cenni al problema della terminazione (halting problem)

La contraddizione del problema della terminazione (diagonalizzazione su D(D))

Fig. 4Per diagonalizzazione su D(D): si ipotizza un decisore H della terminazione e si costruisce D che inverte la previsione di H; entrambe le previsioni portano a contraddizione, quindi H non può esistere.

Un problema decisionale è una domanda a cui si risponde « sì » o « no » (ad esempio: « questo numero è primo? »). Un problema si dice « decidibile » quando esiste un algoritmo che, per OGNI dato di ingresso, fornisce la risposta corretta e termina sempre in un numero finito di passi. Si dice « indecidibile » quando un tale algoritmo non esiste — e qui non si tratta di una difficoltà tecnica momentanea, ma di un'impossibilità dimostrata e definitiva.

Il risultato più celebre della teoria è il « problema della terminazione » (halting problem), dimostrato indecidibile da Turing nel 1936. La domanda è: esiste un programma H che, ricevuto in ingresso un qualsiasi programma P e un qualsiasi dato d, sia in grado di stabilire con certezza se l'esecuzione di P su d terminerà oppure proseguirà all'infinito? La risposta di Turing è netta: un simile programma universale non può esistere.

La dimostrazione procede per assurdo con un argomento di « autoreferenza » (diagonalizzazione). Si supponga che H esista; si costruisca allora un programma furbo D che, ricevuto in ingresso un programma P, interroga H sul comportamento di P applicato a se stesso: se H prevede che P(P) termini, allora D entra deliberatamente in un ciclo infinito; se H prevede che P(P) non termini, allora D termina subito. Si esegua infine D su se stesso, cioè D(D): qualunque previsione faccia H si genera una contraddizione (se H dice « termina », D non termina; se H dice « non termina », D termina). Dunque H non può esistere.

L'esistenza di problemi indecidibili ha una portata che oltrepassa la curiosità teorica: dimostra che vi sono compiti ben definiti che nessun computer — per quanto potente — potrà mai svolgere in modo generale. Molte questioni pratiche dell'informatica sono riconducibili al problema della terminazione (per esempio decidere automaticamente, per OGNI programma, se contiene un certo difetto): di conseguenza certi strumenti di verifica del software non possono essere perfetti in tutti i casi, ma solo corretti su casi particolari o approssimati.

Esempio svolto

Classificare un problema come decidibile o indecidibile

Si classifichino, motivando, i seguenti problemi come decidibili o indecidibili: (a) « dato un intero n, stabilire se è pari »; (b) « dato un programma P e un dato d, stabilire se P(d) termina »; (c) « data una lista finita di interi, stabilire se è ordinata in modo crescente ».

Analisi (a)
Esiste un algoritmo che termina sempre: basta esaminare l'ultima cifra (o calcolare n mod 2). Risposta sì/no in un numero finito di passi per ogni n.
Classificazione (a)
Problema DECIDIBILE.
Analisi (b)
È esattamente il problema della terminazione: Turing ha dimostrato che nessun algoritmo generale può deciderlo per ogni coppia (P, d).
Classificazione (b)
Problema INDECIDIBILE.
Analisi (c)
La lista è finita: si scorrono gli elementi confrontando ciascuno col successivo; al primo confronto in cui l'ordine è violato si risponde « no », altrimenti « sì ». L'algoritmo termina sempre.
Classificazione (c)
Problema DECIDIBILE.

Risultato: (a) decidibile · (b) indecidibile (è l'halting problem) · (c) decidibile.

Errori frequenti

Pensare che « indecidibile » significhi « molto difficile » o « non ancora risolto »: significa che è DIMOSTRATO che nessun algoritmo generale può esistere, mai.
Credere che il problema della terminazione sia irrisolvibile per singoli programmi particolari: per molti programmi specifici la terminazione è ovvia. È inesistente l'algoritmo UNIVERSALE che decida la terminazione per QUALSIASI coppia programma-dato.

Approfondimento

La dimostrazione dell'indecidibilità della terminazione non è un caso isolato: è la sorgente da cui, con la tecnica della riduzione, si dimostra indecidibile una miriade di altri problemi. Ridurre un problema A a un problema B significa mostrare che, se sapessimo risolvere B, sapremmo risolvere anche A; se A è già noto indecidibile, allora anche B deve esserlo, altrimenti risolveremmo A. Con questo metodo si dimostra, per esempio, che è indecidibile stabilire se un programma stamperà mai un dato output, o se due programmi calcolano la stessa funzione. Un risultato di portata generale è il teorema di Rice: qualunque proprietà «semantica» non banale del comportamento di un programma — cioè che riguardi che cosa il programma calcola, non come è scritto — è indecidibile. Ecco perché gli strumenti di analisi automatica del software possono controllare proprietà sintattiche, ma non decidere in generale proprietà di comportamento. Va infine distinta l'indecidibilità dalla semi-decidibilità: il problema della terminazione è «semi-decidibile» (o riconoscibile), perché esiste una procedura che, se il programma termina, prima o poi se ne accorge — basta eseguirlo e aspettare — ma se non termina, la procedura non lo scopre mai, restando in attesa all'infinito. Decidibile significa avere sempre una risposta certa, sì o no; semi-decidibile significa avere la certezza solo per i «sì»: un confine sottile, ma cruciale nella teoria.

Ripasso attivo

Enuncia il problema della terminazione (halting problem) e spiega, illustrando l'idea della dimostrazione per assurdo basata sull'autoreferenza, perché non può esistere un programma in grado di decidere la terminazione di ogni programma su ogni dato.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Complessità computazionale: problemi trattabili e intrattabili (P e NP)#

ApprofondimentoOSA-informatica-fondamenti-teoria-computazioneNozione intuitiva di complessità computazionale: problemi trattabili e intrattabili; classi P e NP (cenni)

Le classi di complessità: P contenuto in NP e i problemi NP-completi

Fig. 5P ⊆ NP: ogni problema risolubile in tempo polinomiale è anche verificabile in tempo polinomiale. I problemi NP-completi sono i più difficili di NP. È aperto se P = NP.

Stabilito che cosa è calcolabile, la teoria della complessità si chiede a quale COSTO. Il costo si misura contando come cresce il numero di operazioni elementari al crescere della dimensione n dell'ingresso, descritto con la notazione asintotica O-grande. Un algoritmo è « efficiente » quando il suo costo cresce in modo polinomiale (per esempio O(n), O(n log n), O(n^2)); è « inefficiente » quando cresce in modo esponenziale (per esempio O(2^n)), perché in tal caso anche ingressi di dimensione moderata richiedono tempi astronomici.

La classe P (« tempo polinomiale ») raccoglie i problemi decisionali per i quali esiste un algoritmo che li RISOLVE in tempo polinomiale: sono i problemi considerati « trattabili », praticamente affrontabili. L'ordinamento di una lista, la ricerca in un insieme, la verifica di primalità appartengono a P.

La classe NP raccoglie i problemi per i quali una soluzione proposta può essere VERIFICATA in tempo polinomiale, anche se TROVARE la soluzione potrebbe richiedere molto più tempo. L'esempio classico è il problema dello zaino o il problema del commesso viaggiatore in forma decisionale: data una soluzione candidata, controllarne la validità è rapido; trovarla da zero, con i metodi noti, può richiedere tempo esponenziale. Ogni problema di P è anche in NP (se so risolverlo in fretta, so anche verificarlo in fretta), quindi P è contenuto in NP.

La domanda « P = NP? » — se cioè ogni problema verificabile rapidamente sia anche risolubile rapidamente — è il più importante problema aperto dell'informatica teorica (uno dei « problemi del millennio »). Gli esperti ritengono che P sia diverso da NP, ma una dimostrazione non esiste. All'interno di NP vi sono i problemi « NP-completi », i più difficili della classe: se anche solo uno di essi ammettesse un algoritmo polinomiale, allora P sarebbe uguale a NP e tutti i problemi di NP diverrebbero trattabili. È questa cornice a giustificare, in pratica, l'uso di metodi approssimati o euristici per i problemi intrattabili.

T(n) = O\big(g(n)\big)

Notazione O-grande

Il costo T(n) di un algoritmo è O(g(n)) se, per n sufficientemente grande, cresce al più come g(n) a meno di una costante: misura l'ordine di crescita, non i dettagli implementativi.

\mathrm{P} \subseteq \mathrm{NP}

Relazione tra le classi

Ogni problema risolubile in tempo polinomiale (P) è anche verificabile in tempo polinomiale (NP). Se valga anche l'inclusione opposta (P = NP) è il grande problema aperto.

Crescita del costo: tempo polinomiale n² contro tempo esponenziale 2^n

Esempio svolto

Confrontare la trattabilità di due algoritmi tramite il numero di operazioni

Due algoritmi risolvono lo stesso problema: A esegue circa n^2 operazioni, B circa 2^n operazioni, dove n è la dimensione dell'ingresso. Si calcoli il numero di operazioni di ciascuno per n = 5 e n = 20 e si stabilisca quale algoritmo è trattabile.

Algoritmo A, n=5
n^2 = 5^2 = 25 operazioni.
Algoritmo B, n=5
2^n = 2^5 = 32 operazioni. Per n piccolo i due valori sono confrontabili.
Algoritmo A, n=20
n^2 = 20^2 = 400 operazioni: una crescita modesta.
Algoritmo B, n=20
2^n = 2^20 = 1.048.576 operazioni: oltre un milione, contro le 400 di A.
Confronto
La crescita esponenziale di B esplode: già a n=20 supera quella polinomiale di A di oltre 2600 volte, e il divario cresce senza limite. Il polinomiale resta affrontabile, l'esponenziale diventa proibitivo.

Risultato: L'algoritmo A (O(n^2), polinomiale) è trattabile; l'algoritmo B (O(2^n), esponenziale) è intrattabile per n grande: a n=20 richiede 1.048.576 operazioni contro 400.

Errori frequenti

Confondere « problema in NP » con « problema impossibile »: NP non significa indecidibile; significa che una soluzione è verificabile in tempo polinomiale. I problemi NP sono tutti calcolabili.
Dare per dimostrato che P sia diverso da NP: è una congettura largamente ritenuta vera ma NON dimostrata; è un problema aperto.

Approfondimento

Il cuore della teoria della complessità è la nozione di NP-completezza, e il suo motore è di nuovo la riduzione. Un problema è NP-completo quando appartiene a NP e, in più, ogni altro problema di NP gli si può ridurre in tempo polinomiale: esso è quindi «almeno difficile quanto» qualunque problema della classe. Il teorema di Cook-Levin (1971) dimostrò che il problema della soddisfacibilità booleana (SAT — esiste un'assegnazione di verità che rende vera una formula logica?) è NP-completo, il primo della storia; da allora, per riduzione a partire da SAT, si è dimostrato NP-completo un elenco vastissimo di problemi pratici: il commesso viaggiatore, la colorazione di grafi, lo zaino, la pianificazione. La conseguenza è pesante: se anche uno solo di essi avesse un algoritmo polinomiale, l'avrebbero tutti (P = NP); poiché si congettura di no, di fronte a un problema NP-completo non si cerca la soluzione esatta, ma ci si accontenta di algoritmi di approssimazione (che garantiscono una soluzione vicina all'ottimo), di euristiche (che funzionano bene in pratica senza garanzie) o di metodi probabilistici. Per rendere concreta la differenza fra polinomiale ed esponenziale: un algoritmo «O(n²)» su un ingresso «n = 50» esegue circa 2500 operazioni, mentre uno «O(2ⁿ)» ne esegue circa «10¹⁵» — la distanza fra un istante e millenni di calcolo. È questa voragine, che nessun hardware può colmare, a separare il trattabile dall'intrattabile.

Ripasso attivo

Spiega la differenza tra la classe P e la classe NP usando la distinzione tra « risolvere » e « verificare » una soluzione, e illustra il significato della domanda aperta « P = NP? ». Chiarisci infine perché un algoritmo di costo O(2^n) è considerato intrattabile rispetto a uno di costo O(n^2).

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

I limiti teorici del calcolo automatico e le loro implicazioni#

StandardOSA-informatica-fondamenti-teoria-computazioneLimiti teorici del calcolo automatico e loro implicazioni

Mappa dei problemi: non calcolabili, calcolabili intrattabili, calcolabili trattabili

Fig. 7I problemi trattabili (classe P) hanno costo polinomiale; fra calcolabili e trattabili stanno gli intrattabili (costo esponenziale); fuori dai calcolabili, i problemi indecidibili (es. halting problem).

La teoria della computazione consegna una mappa dei confini del calcolo articolata su due assi distinti. Il primo asse è quello della calcolabilità: separa ciò che può essere calcolato da ciò che è indecidibile, cioè i problemi che nessun algoritmo potrà mai risolvere in generale. Il secondo asse è quello della complessità: tra i problemi calcolabili, separa quelli trattabili (efficienti, polinomiali) da quelli intrattabili (esponenziali con i metodi noti).

Questi limiti sono di natura LOGICA, non tecnologica. Nessun avanzamento dell'hardware, nessuna nuova generazione di processori potrà mai risolvere il problema della terminazione in generale, perché l'impossibilità è dimostrata a partire dalla pura logica del calcolo. Allo stesso modo, finché P resta diverso da NP (come si congettura), per i problemi NP-completi non esisterà un metodo risolutivo universalmente efficiente, comunque potente sia la macchina.

Le implicazioni pratiche sono concrete e quotidiane. L'indecidibilità della terminazione spiega perché gli strumenti di verifica del software non possono garantire l'assenza di tutti i difetti per ogni programma: possono solo lavorare su casi particolari o dare risposte approssimate. La presenza di problemi intrattabili spiega perché, di fronte a un problema NP-completo, l'informatica si affida a soluzioni APPROSSIMATE, euristiche o probabilistiche, rinunciando alla soluzione esatta in cambio di tempi accettabili.

Vi è infine un risvolto positivo e fondante: la stessa difficoltà di certi problemi è una risorsa. La crittografia moderna, su cui poggia la sicurezza di Internet, si fonda proprio sulla presunta intrattabilità di alcuni problemi (come la fattorizzazione di numeri molto grandi): è « facile » verificare una chiave ma « difficile » scoprirla. In questa cornice teorica gli algoritmi e la programmazione studiati nel corso trovano il loro senso più profondo: sapere che cosa si può calcolare, e a quale costo, è la base culturale dell'informatica.

Esempio svolto

Inquadrare un problema reale nella mappa dei limiti del calcolo

Per ciascuna delle seguenti situazioni, indica quale limite teorico è coinvolto (indecidibilità oppure intrattabilità) e quale conseguenza pratica ne deriva: (a) un'azienda vuole un programma che, dato QUALSIASI software, garantisca che non andrà mai in loop infinito; (b) un corriere vuole il percorso più breve che tocchi 50 città una sola volta.

Analisi (a)
Decidere per ogni programma se termina è il problema della terminazione, dimostrato indecidibile.
Conseguenza (a)
Nessun programma può garantirlo in generale: gli strumenti di verifica si limitano a casi particolari o ad analisi approssimate, mai a una garanzia universale.
Analisi (b)
È una variante del problema del commesso viaggiatore, NP-completo: calcolabile (le soluzioni sono finite) ma con costo esponenziale nei metodi esatti.
Conseguenza (b)
Per 50 città l'enumerazione esatta è proibitiva; si ricorre ad algoritmi approssimati o euristici che trovano un buon percorso (non necessariamente l'ottimo) in tempi accettabili.

Risultato: (a) limite di indecidibilità → verifica solo parziale/approssimata; (b) limite di intrattabilità (NP-completezza) → si usano metodi approssimati ed euristici.

Errori frequenti

Confondere i due limiti: l'indecidibilità riguarda l'ESISTENZA stessa di un algoritmo; l'intrattabilità riguarda il COSTO di un algoritmo che esiste. Sono assi diversi.
Credere che computer più potenti possano superare questi limiti: l'impossibilità è logica e indipendente dalla tecnologia.

Approfondimento

Un'ultima domanda chiude il quadro: modelli di calcolo radicalmente nuovi possono superare questi limiti? Il candidato più discusso è il computer quantistico, che sfrutta i principi della meccanica quantistica (sovrapposizione, entanglement) per esplorare in parallelo molte possibilità. Conviene essere precisi su ciò che può e non può fare. Non supera i limiti di calcolabilità: un computer quantistico non può risolvere il problema della terminazione, perché è comunque simulabile da una macchina di Turing e calcola quindi le stesse funzioni, solo potenzialmente più in fretta. Sul piano della complessità offre invece accelerazioni notevoli per problemi specifici — l'algoritmo di Shor fattorizza numeri grandi in tempo polinomiale, minacciando la crittografia a chiave pubblica attuale e spingendo verso una crittografia «post-quantistica» — ma non si ritiene che possa risolvere in tempo polinomiale i problemi NP-completi in generale. I limiti di fondo, dunque, restano. Vi è infine un legame profondo con la logica: il teorema di incompletezza di Gödel (1931), gemello dei risultati di Turing, dimostra che in ogni sistema formale abbastanza potente esistono affermazioni vere ma indimostrabili al suo interno — calcolo e dimostrazione condividono lo stesso confine invalicabile. Conoscere questa mappa — che cosa si può calcolare, a quale costo, e che cosa resta per sempre fuori portata — è il traguardo culturale a cui l'intero corso di informatica conduce: non solo saper programmare, ma sapere che cosa la programmazione può e non può fare.

Ripasso attivo

Distingui tra i limiti di calcolabilità (problemi indecidibili) e i limiti di complessità (problemi intrattabili), spiegando perché entrambi sono limiti logici e non tecnologici. Illustra poi una conseguenza pratica per ciascuno dei due tipi di limite.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Riferimenti e fonti

Fonti

Ministero dell'Istruzione e del Merito (MIM)

Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento

Principi teorici della computazione

5 sezioni~26 min di lettura3 competenzeLivello Standard 2 · Approfondimento 3Verificato · 07/2026

Principi teorici della computazione

Punti chiave

Riconoscere se una procedura è un algoritmo (e quindi calcolabile)

Punti chiave

Far funzionare un automa a stati finiti su una stringa

Punti chiave

Classificare un problema come decidibile o indecidibile

Punti chiave

Confrontare la trattabilità di due algoritmi tramite il numero di operazioni

Punti chiave

Inquadrare un problema reale nella mappa dei limiti del calcolo

Fonti

Principi teorici della computazione

Punti chiave

Riconoscere se una procedura è un algoritmo (e quindi calcolabile)

Punti chiave

Far funzionare un automa a stati finiti su una stringa

Punti chiave

Classificare un problema come decidibile o indecidibile

Punti chiave

Confrontare la trattabilità di due algoritmi tramite il numero di operazioni

Punti chiave

Inquadrare un problema reale nella mappa dei limiti del calcolo

Fonti