L'informatica teorica rappresenta il fondamento matematico su cui poggia l'intera disciplina informatica moderna. Prima dell'avvento dei calcolatori elettronici, matematici e logici del ventesimo secolo si interrogavano sulla natura stessa del calcolo e sui limiti intrinseci di ciò che può essere computato mediante procedure algoritmiche.
Il problema centrale che animava il dibattito matematico degli anni Trenta riguardava la decidibilità: è possibile determinare meccanicamente se una proposizione matematica sia vera o falsa? Questo interrogativo, noto come Entscheidungsproblem (problema della decisione), formulato da David Hilbert nel 1928, costituiva uno dei pilastri del programma di Hilbert per la fondazione della matematica.
Alan Turing, matematico britannico, affrontò questo problema nel suo celebre articolo del 1936 "On Computable Numbers, with an Application to the Entscheidungsproblem", introducendo un modello astratto di calcolo che oggi conosciamo come Macchina di Turing. Parallelamente, Alonzo Church sviluppava il lambda calcolo, dimostrando l'equivalenza dei due approcci attraverso quella che oggi chiamiamo Tesi di Church-Turing.
Una Macchina di Turing (MdT) è un modello matematico di calcolo costituito da:
Definizione formale: Una Macchina di Turing deterministica è una settupla M = (Q, Σ, Γ, δ, q₀, B, F) dove:
Il nastro della Macchina di Turing è concettualmente infinito in entrambe le direzioni (o, equivalentemente, infinito a destra con estensione dinamica), suddiviso in celle contenenti ciascuna un simbolo dell'alfabeto Γ. La testina di lettura/scrittura può:
La funzione di transizione δ rappresenta il "programma" della macchina. Dato lo stato corrente e il simbolo letto, δ determina:
Formalmente: δ(q, a) = (p, b, D) significa che, trovandosi nello stato q e leggendo il simbolo a, la macchina transisce allo stato p, scrive il simbolo b e muove la testina nella direzione D.
Una configurazione (o descrizione istantanea) della macchina descrive completamente il suo stato in un dato momento e può essere rappresentata come (q, w₁aw₂), dove:
Una computazione è una sequenza di configurazioni C₀ ⊢ C₁ ⊢ C₂ ⊢ ... ⊢ Cₙ, dove C₀ è la configurazione iniziale e ogni Cᵢ₊₁ è ottenuta da Cᵢ mediante l'applicazione della funzione di transizione.
La macchina accetta un input se, partendo dalla configurazione iniziale con quell'input sul nastro, raggiunge uno stato finale. La macchina rigetta se termina in uno stato non finale o se entra in un ciclo infinito.
Una MdT a k nastri possiede k nastri indipendenti, ciascuno con la propria testina. La funzione di transizione diventa:
δ: Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ
Teorema di equivalenza: Ogni Macchina di Turing a k nastri può essere simulata da una Macchina di Turing standard a un nastro con al più un rallentamento quadratico.
Dimostrazione (sketch): Si codificano i k nastri su un unico nastro usando un alfabeto espanso che include marcatori per le posizioni delle k testine. Ogni passo della macchina multinastro viene simulato mediante una scansione completa del nastro della macchina singolo-nastro.
Una Macchina di Turing non deterministica (NDTM) ha una funzione di transizione che restituisce un insieme di possibili transizioni:
δ: Q × Γ → P(Q × Γ × {L, R, S})
La macchina accetta se esiste almeno un percorso computazionale che porta a uno stato finale.
Teorema: Ogni linguaggio riconosciuto da una NDTM è riconosciuto anche da una DTM.
Questo risultato è fondamentale ma nasconde una complessità cruciale: la simulazione può richiedere tempo esponenziale, portando alla famosa questione P vs NP.
Una Macchina di Turing Universale (UTM) è una MdT che può simulare qualsiasi altra MdT dato:
Formalmente, dato un sistema di codifica ⟨M⟩ per le macchine di Turing:
U(⟨M⟩, w) simula M(w)
L'esistenza di una UTM dimostra che esiste una macchina "programmabile" capace di eseguire qualsiasi algoritmo, prefigurando concettualmente il computer general-purpose.
Un linguaggio formale L su un alfabeto Σ è un sottoinsieme (eventualmente infinito) di Σ*, l'insieme di tutte le stringhe finite costruibili con simboli di Σ.
Gerarchia di Chomsky: I linguaggi formali si classificano in quattro categorie:
Tipo 0 - Linguaggi Ricorsivamente Enumerabili (RE): Riconosciuti dalle Macchine di Turing. Le produzioni grammaticali hanno forma α → β con α, β ∈ (V ∪ Σ)* e α contiene almeno un simbolo non terminale.
Tipo 1 - Linguaggi Context-Sensitive (CS): Riconosciuti da automi linearly bounded. Le produzioni hanno forma αAβ → αγβ con |γ| ≥ 1 (produzioni non contrattive).
Tipo 2 - Linguaggi Context-Free (CF): Riconosciuti da automi a pila. Le produzioni hanno forma A → γ con A simbolo non terminale.
Tipo 3 - Linguaggi Regolari: Riconosciuti da automi a stati finiti. Le produzioni hanno forma A → aB o A → a.
Vale l'inclusione stretta: REG ⊂ CF ⊂ CS ⊂ RE.
Un linguaggio L è Turing-riconoscibile (o ricorsivamente enumerabile) se esiste una MdT M tale che:
Un linguaggio L è Turing-decidibile (o ricorsivo) se esiste una MdT M che termina sempre e:
La distinzione è cruciale: i linguaggi decidibili costituiscono un sottoinsieme proprio dei linguaggi riconoscibili.
Una funzione f: Σ* → Σ* è Turing-calcolabile se esiste una MdT M tale che, per ogni input w:
Tesi di Church-Turing: Ogni funzione calcolabile mediante una procedura algoritmica intuitiva è calcolabile da una Macchina di Turing.
Questa non è un teorema matematico ma una tesi filosofica che identifica la nozione intuitiva di "calcolabilità" con la calcolabilità formale delle MdT. L'evidenza a supporto include:
Teorema dell'Arresto (Halting Problem): Il problema di determinare se una MdT M si ferma su un input w è indecidibile.
Dimostrazione per diagonalizzazione:
Supponiamo per assurdo che esista una MdT H che decide il problema dell'arresto:
H(⟨M⟩, w) = { accetta se M si ferma su w rigetta se M non si ferma su w }
Costruiamo una macchina D che, dato ⟨M⟩:
Consideriamo D(⟨D⟩):
Entrambi i casi portano a contraddizione, dunque H non può esistere. ∎
Una riduzione da un problema A a un problema B è un algoritmo che trasforma istanze di A in istanze di B preservando la risposta. Se A è riducibile a B e B è decidibile, allora anche A è decidibile.
Esempi di problemi indecidibili dimostrati per riduzione dall'Halting Problem:
Definizione: Una MdT M opera in tempo f(n) se, per ogni input di lunghezza n, M termina entro f(n) passi.
DTIME(f(n)): Classe dei linguaggi decidibili da una DTM in tempo O(f(n))
NTIME(f(n)): Classe dei linguaggi decidibili da una NDTM in tempo O(f(n))
Classe P: Insieme dei problemi decidibili in tempo polinomiale P = ⋃ₖ DTIME(nᵏ)
Classe NP: Insieme dei problemi decidibili da una NDTM in tempo polinomiale NP = ⋃ₖ NTIME(nᵏ)
Equivalentemente, NP è la classe dei problemi per cui una soluzione può essere verificata in tempo polinomiale.
Domanda aperta: P = NP?
Sappiamo che P ⊆ NP, ma non sappiamo se l'inclusione è stretta. Questo è considerato il più importante problema aperto in informatica teorica, con un premio di un milione di dollari del Clay Mathematics Institute.
Significato pratico: Se P = NP, problemi che oggi richiedono tempo esponenziale (come fattorizzazione, ottimizzazione combinatoria, scheduling) potrebbero essere risolti efficientemente. L'impatto su crittografia, intelligenza artificiale, logistica e molti altri campi sarebbe rivoluzionario.
Un problema L è NP-completo se:
Teorema di Cook-Levin (1971): Il problema SAT (soddisfacibilità booleana) è NP-completo.
Questo teorema è fondamentale perché fornisce il primo problema NP-completo, permettendo di dimostrare la NP-completezza di altri problemi mediante riduzione da SAT.
Esempi di problemi NP-completi:
SPACE(f(n)): Linguaggi decidibili usando O(f(n)) celle di nastro
NSPACE(f(n)): Linguaggi decidibili da NDTM usando O(f(n)) celle
Classe L: SPACE(log n) - problemi decidibili in spazio logaritmico
Classe PSPACE: ⋃ₖ SPACE(nᵏ) - problemi decidibili in spazio polinomiale
Teorema di Savitch: NSPACE(f(n)) ⊆ SPACE(f²(n)) per f(n) ≥ log n
Questo implica che PSPACE = NPSPACE, un risultato notevole che contrasta con l'incertezza su P vs NP.
Le relazioni note tra le principali classi sono:
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
Sappiamo che P ≠ EXPTIME (per il teorema della gerarchia temporale), ma non sappiamo quali altre inclusioni siano strette.
Un DFA è una quintupla M = (Q, Σ, δ, q₀, F) dove:
Teorema: Un linguaggio è regolare se e solo se è riconosciuto da un DFA.
Un NFA differisce da un DFA per la funzione di transizione:
δ: Q × (Σ ∪ {ε}) → P(Q)
Gli NFA possono avere transizioni ε (senza consumare input) e transizioni multiple dallo stesso stato con lo stesso simbolo.
Teorema di equivalenza DFA-NFA: Per ogni NFA esiste un DFA equivalente (costruzione per sottoinsiemi).
Le espressioni regolari forniscono una notazione algebrica per i linguaggi regolari:
Teorema di Kleene: Un linguaggio è regolare se e solo se può essere descritto da un'espressione regolare.
Lemma di Pumping: Se L è un linguaggio regolare, esiste una costante p (lunghezza di pumping) tale che ogni stringa w ∈ L con |w| ≥ p può essere suddivisa in w = xyz soddisfacendo:
Applicazione: Dimostrare che L = {aⁿbⁿ | n ≥ 0} non è regolare.
Supponiamo per assurdo che L sia regolare con lunghezza di pumping p. Consideriamo w = aᵖbᵖ ∈ L. Per il pumping lemma, w = xyz con y = aᵏ (k > 0) e |xy| ≤ p. Allora xy²z = aᵖ⁺ᵏbᵖ ∉ L, contraddizione. ∎
Un PDA è una settupla M = (Q, Σ, Γ, δ, q₀, Z₀, F) dove:
Teorema: Un linguaggio è context-free se e solo se è accettato da un PDA.
Una CFG è una quadrupla G = (V, Σ, R, S) dove:
Forma Normale di Chomsky: Ogni CFG può essere convertita in forma normale di Chomsky dove tutte le produzioni hanno forma:
Lemma di Pumping (CF): Se L è context-free, esiste p tale che ogni w ∈ L con |w| ≥ p può essere scritta come w = uvxyz con:
Applicazione: L = {aⁿbⁿcⁿ | n ≥ 0} non è context-free (dimostrazione simile al caso regolare).
Il lambda calcolo, sviluppato da Church, è un sistema formale basato su:
Regola β: (λx.M)N →β M[N/x] (sostituzione di x con N in M)
Teorema di Church-Rosser: Se un termine ha una forma normale, la β-riduzione la raggiunge indipendentemente dall'ordine delle riduzioni.
Le funzioni ricorsive sono definite a partire da:
Teorema: Una funzione è Turing-calcolabile se e solo se è ricorsiva.
Le macchine a registri (o RAM machines) hanno:
Teorema: Le macchine a registri sono equivalenti alle MdT in termini di potenza computazionale.
Un sistema formale consiste in:
Primo Teorema di Incompletezza di Gödel (1931): In ogni sistema formale consistente e sufficientemente espressivo (capace di rappresentare l'aritmetica), esistono proposizioni vere ma non dimostrabili nel sistema.
Secondo Teorema di Incompletezza: Un sistema formale consistente non può dimostrare la propria consistenza.
Questi risultati hanno profonde implicazioni per i limiti della formalizzazione matematica e sono intimamente connessi alla teoria della computabilità.
Esiste una profonda corrispondenza tra:
Questa corrispondenza unifica logica, teoria dei tipi e computazione, costituendo la base della teoria dei tipi costruttivi e dei proof assistants moderni.
La teoria della complessità parametrizzata studia problemi NP-hard chiedendo: possiamo risolverli efficientemente quando un parametro k è piccolo?
Un problema è fixed-parameter tractable (FPT) se risolvibile in tempo f(k)·nᶜ dove f è una funzione qualsiasi di k e c è una costante.
Esempio: Vertex Cover è FPT nel parametro k (dimensione del cover).
La complessità descrittiva collega classi di complessità e logica:
Teorema di Fagin: NP è esattamente la classe dei linguaggi descrivibili in logica del secondo ordine esistenziale.
Teorema: P coincide con i linguaggi descrivibili in logica del primo ordine con punto fisso meno generale.
Le macchine di Turing quantistiche operano su sovrapposizioni di stati, utilizzando:
Classe BQP (Bounded-error Quantum Polynomial time): problemi risolvibili da computer quantistici in tempo polinomiale con probabilità di errore limitata.
Sappiamo: P ⊆ BQP ⊆ PSPACE, ma non sappiamo se BQP = P o BQP = NP.
Il calcolo con DNA sfrutta:
Adleman (1994) risolse un'istanza del Hamiltonian Path Problem con DNA, dimostrando la fattibilità del bio-computing.
L'informatica teorica fornisce i fondamenti matematici per comprendere cosa può essere computato e con quale efficienza. I risultati principali che abbiamo esplorato includono:
Le domande aperte più significative rimangono P vs NP, i limiti del calcolo quantistico rispetto al calcolo classico, e le connessioni profonde tra logica, computabilità e complessità.
La Macchina di Turing, concepita come strumento per affrontare questioni fondazionali della matematica, si è rivelata il modello teorico che meglio cattura l'essenza della computazione, influenzando profondamente lo sviluppo dell'informatica pratica e rimanendo ancora oggi il riferimento centrale per l'analisi degli algoritmi e lo studio dei limiti computazionali.