Loading
Loading
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.
5sezionica. 20min di lettura3competenzeLivelloStandard 2 · Approfondimento 3Verificato · 06/2026
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).
Lesetiefe: Approfondimento
Schriftgröße: Standard
I modelli di calcolo equivalenti e la tesi di Church-Turing
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.
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.
Ogni passo (la divisione e il confronto del resto con zero) è univocamente definito: dato lo stesso n si ottiene sempre lo stesso esito.
La procedura funziona per qualsiasi naturale n ≥ 2, non per un singolo valore particolare.
Ogni operazione (divisione intera, confronto) è elementare e meccanicamente eseguibile.
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
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))
Struttura di una macchina di Turing: nastro, testina e unità di controllo
Automa a stati finiti che accetta le stringhe binarie con un numero pari di 1
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.
L'automa parte in q0 (zero « 1 » letti: numero pari).
Da q0, il simbolo « 1 » commuta lo stato: q0 → q1 (un « 1 » letto, dispari).
Da q1, il simbolo « 0 » lascia invariato lo stato: q1 → q1.
Da q1, « 1 » commuta: q1 → q0 (due « 1 » letti, pari).
Da q0, « 1 » commuta: q0 → q1 (tre « 1 » letti, dispari).
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
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))
La contraddizione del problema della terminazione (diagonalizzazione su D(D))
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 ».
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.
Problema DECIDIBILE.
È esattamente il problema della terminazione: Turing ha dimostrato che nessun algoritmo generale può deciderlo per ogni coppia (P, d).
Problema INDECIDIBILE.
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.
Problema DECIDIBILE.
Risultato: (a) decidibile · (b) indecidibile (è l'halting problem) · (c) decidibile.
Errori frequenti
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))
Le classi di complessità: P contenuto in NP e i problemi NP-completi
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.
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
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.
n^2 = 5^2 = 25 operazioni.
2^n = 2^5 = 32 operazioni. Per n piccolo i due valori sono confrontabili.
n^2 = 20^2 = 400 operazioni: una crescita modesta.
2^n = 2^20 = 1.048.576 operazioni: oltre un milione, contro le 400 di A.
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
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))
Mappa dei problemi: non calcolabili, calcolabili intrattabili, calcolabili trattabili
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.
Decidere per ogni programma se termina è il problema della terminazione, dimostrato indecidibile.
Nessun programma può garantirlo in generale: gli strumenti di verifica si limitano a casi particolari o ad analisi approssimate, mai a una garanzia universale.
È una variante del problema del commesso viaggiatore, NP-completo: calcolabile (le soluzioni sono finite) ma con costo esponenziale nei metodi esatti.
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
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
Ministero dell'Istruzione e del Merito (MIM)