L’informatica teorica
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
Negli anni Trenta del Novecento i logici riescono a dare uno statuto matematico alla nozione di calcolo. Nasce la teoria della calcolabiltà, sviluppata inzialmente per l’esigenza di precisare la nozione di deduzione formale. In questo decennio tre approcci indipendenti e quasi simultanei alla calcolabilità sono equivalenti: le funzioni ricorsive, λ-definibili, e Turing-calcolabili caratterizzano infatti la stessa classe di funzioni calcolabili. Ciascuno di questi tre approcci, però, apporta un contributo differente alla comprensione della nozione di funzione calcolabile e quindi si rende responsabile degli sviluppi successivi dell’informatica teorica.
All’origine dell’informatica
L’informatica teorica può essere definita come quella disciplina che studia fenomeni computazionali e che si occupa in generale dell’analisi di algoritmi fino a includere la struttura logica dei linguaggi di programmazione. Sebbene la nozione di calcolo o di algoritmo abbia alle proprie spalle più di due millenni di storia – basti pensare all’algoritmo euclideo per determinare il minimo comune divisore – modelli astratti e generali di calcolo non sono stati elaborati prima degli anni Trenta del Novecento. È una profonda ironia storica che, negli anni in cui il programma formalista di David Hilbert si rivela del tutto inadeguato, sia proprio da un’idea formalista come la meccanicità della deduzione che cominci a prendere forma una nuova disciplina scientifica, l’informatica, che è il più profondo e originale lascito intellettuale della logica novecentesca. Gli anni Trenta sono cruciali per chiarire la nozione di funzione calcolabile e di procedura finita, e, in generale, per gettare le basi della teoria matematica della calcolabilità, molto prima dell’avvento dei calcolatori. Non solo i linguaggi di programmazione, che non sono altro che linguaggi che definiscono funzioni, ma anche la programmazione logica può essere vista, a giusto titolo, come l’evoluzione diretta dei contributi teorici dei logici che lavorano in quegli anni.
La nascita della teoria della calcolabilità
Il meccanismo di ricorsione come mezzo per definire funzioni numeriche era già noto a Richard Dedekind e a Giuseppe Peano, per i quali i numeri naturali sono costruiti dal numero zero a cui è applicata la funzione successore (Nx = x+1). Negli anni Venti Thoralf Skolem sviluppa la base dell’aritmetica ricorsiva primitiva che comprende la classe di tutte le funzioni usuali dell’aritmetica. Alla fine degli anni Venti questa classe sembrava sufficientemente potente da definire tutte le funzioni calcolabili, ma nel 1928 il logico tedesco Wilhelm Ackerman esibisce una funzione, oggi chiamata funzione di Ackerman, intuitivamente calcolabile ma non ricorsiva primitiva poiché “cresce più in fretta” di ogni altra funzione ricorsiva primitiva. Solo nel 1934, raccogliendo un suggerimento di Jacques Herbrand, Kurt Gödel arriva a definire la nozione generale di funzione ricorsiva. Del resto risultati sulle funzioni ricorsive erano stati già sviluppati da Gödel nella sua fondamentale memoria del 1931.
Informalmente, l’idea che porta a definire la classe delle funzioni ricorsive consiste nell’introdurre alcune funzioni molto semplici e nel costruire funzioni assai più complesse applicando alcuni operatori a funzioni la cui appartenenza alla classe è già stata stabilita. Tecnicamente, dunque, le funzioni ricorsive sono gli elementi del più piccolo insieme di funzioni aritmetiche che contiene le funzioni base (funzione zero, funzione successore, funzione proiezione) e che è chiuso rispetto agli operatori di composizione, ricorsione e minimalizzazione. Nel 1938 Stephen C. Kleene dà una definizione precisa della classe delle funzioni parziali ricorsive, che probabilmente rappresenta l’ambito della teoria della ricorsività in cui sono stati ottenuti i risultati più interessanti. Negli stessi anni Trenta, il logico statunitense Alonzo Church introduce un sistema estremamente economico per definire gli algoritmi, il λ-calcolo, destinato a rivelarsi uno straordinario laboratorio di sperimentazione sui fenomeni computazionali. Il λ-calcolo esprime la classe delle funzioni calcolabili, cioè funzioni per le quali esistono algoritmi che le calcolano. Questo significa che le funzioni sono viste dal punto di vista di regole, anziché di grafici (insiemi di coppie ordinate), che ne congelano il comportamento computazionale. Contrariamente a quanto avviene nella teoria assiomatica degli insiemi di Zermelo-Fraenkel (per l’assioma di fondazione), nel λ-calcolo una funzione può essere applicata a se stessa, cioè è assente una predeterminata distinzione tra funzioni e argomenti. Moses Schönfinkel, proponendo un “calcolo algebrico senza variabili” è stato il primo a notare, nella prima metà degli anni Venti, che funzioni con un numero arbitrario (finito) di argomenti si lasciano ridurre a quelle con un solo argomento, se permettiamo che, come argomenti e valori delle funzioni, figurino ancora funzioni.
L’insieme dei λ-termini è il più piccolo insieme tale che:
– una variabile è un termine
– se u è un λ-termine e x una variabile, λx.u è un λ-termine (astrazione)
– se u e v sono λ-termini, (u)v è un λ-termine (applicazione)
Per esempio, la funzione matematica f(x)= x² è rappresentabile nel λ-calcolo come λx.x². L’unica regola di calcolo (β-riduzione) è la seguente:
(λx.u)v → u[v/x]
dove u[v/x] è il λ-termine u entro il quale ciascuna occorrenza della variabile x è stata sostituita da v. La β-riduzione è confluente: se t si riduce a v e a t, allora esiste un termine w tale che sia u che v sono riducibili a w. La confluenza, che ha essenzialmente una natura geometrica, è una proprietà fondamentale di un calcolo inteso come processo di riduzione; perché costituisce una sorta di dichiarazione di indipendenza: il risultato del calcolo è indipendente dal cammino di riduzione seguito.
Nel 1936 Kleene dimostra l’equivalenza tra la nozione di funzione ricorsiva e la nozione di funzione λ-definibile, cioè una funzione espressa dal λ-calcolo (dove un intero n è codificato come “iteratore di funzione”: n; λ fx. fn x).
Nel stesso anno, Church può annunciare la tesi, per così dire “semimatematica”, che porta il suo nome (TC), secondo cui ogni funzione effettivamente calcolabile è ricorsiva.
TC è senz’altro un’ipotesi di lavoro molto ragionevole, ben motivata dal fatto che altre differenti formulazioni della classe delle funzioni calcolabili descrivono classi di funzioni che sono coestensive a quella delle funzioni ricorsive. Tuttavia TC non è sufficientemente rigorosa da poter aspirare a diventare un teorema. Il motivo è che al suo interno unicamente la nozione di ricorsività rimanda a una definizione precisa, laddove la nozione di calcolabilità rimane in una nube intuitiva e informale, che rimanda a una nozione “fisica” di calcolo meccanico o automatico. Almeno in linea di principio, però, TC, estremamente in generale, può essere smentita da un controesempio: l’esibizione di una funzione intuitivamente e sicuramente calcolabile ma nello stesso tempo non ricorsiva. TC ha comunque almeno due notevoli conseguenze pratiche che meritano di essere segnalate: la prima è che nessun informatico scriverà mai un programma per calcolare una funzione che si è dimostrata non ricorsiva; la seconda è che nel corso di una dimostrazione, TC permette di qualificare un funzione visibilmente calcolabile come ricorsiva, evitando di dimostrarlo.
Da quando, alla fine degli anni Cinquanta, John McCarthy ha ideato il primo linguaggio di programmazione funzionale, il LISP, incorporando le idee del λ-calcolo, quest’ultimo ha acquisito un peso crescente presso la comunità informatica: oggi, infatti, è ampiamente accettato come la base logica della programmazione funzionale, soprattutto a seguito della scoperta di Stephen D. Scott nel 1970 di modelli del λ-calcolo. Più in generale, recenti sviluppi dell’informatica teorica e della logica hanno mostrato che il λ-calcolo fa da ponte tra la teoria della calcolabilità e la teoria della dimostrazione. Una prima osservazione di Haskell B. Curry nel 1958 aveva messo in evidenza un’identità di struttura tra i termini del λ-calcolo tipato – cioè tale per cui è stato definito un sistema di regole in base alle quali è possibile attribuire un tipo a espressioni, comandi e altri costrutti del linguaggio – e le dimostrazioni della deduzione naturale intuizionista. Più tardi l’esplicitazione di questo parallelismo è stata fatta da W. A. Howard nel 1969 (ma il lavoro fu pubblicato solo nel 1980) ed è alla base del rapporto tra la programmazione e la teoria della dimostrazione:
dimostrazioni = λ-termine = programma
proposizione = tipo = specificazione
Le dimostrazioni logiche sono dunque programmi la cui correttezza è assicurata dalla logica.
La macchina di Turing
Dare uno statuto matematico alla nozione di calcolo non significa ancora elaborarne modelli convincenti: né le funzioni λ-definibili né le funzioni ricorsive costituiscono infatti modelli intrinsecamente convincenti di calcolabilità effettiva. Nel 1936 in On computable numbers with an application to the Entscheidungsproblem (Sui numeri computabili con un’applicazione all’Entscheidungsproblem) il matematico inglese Alan Mathison Turing concepisce un modello di calcolo in termini di una macchina astratta che simula il comportamento di un essere umano che sta eseguendo un calcolo di tipo algoritmico. Turing può così introdurre un terza nozione di calcolabilità, equivalente a quella di ricorsività e di λ-definibilità, ma calcolabile da una macchina astratta di un certo tipo.
Una macchina di Turing (MT) consiste in un insieme finito di stati e in un nastro monodimensionale finito, ma potenzialmente illimitato in entrambe le direzioni, suddiviso in celle, ciascuna delle quali è vuota oppure ospita un simbolo di un alfabeto finito; una testina può leggere, scrivere e muoversi verso destra o sinistra lungo il nastro oppure stare ferma. Turing ci offre una spiegazione epistemologica del perché gli stati interni della macchina (che corrispondono a stati mentali umani) sono in un numero finito: “se ammettessimo un’infinità di stati mentali, alcuni di essi sarebbero arbitrariamente prossimi e quindi confusi”. Allo stesso modo, l’alfabeto è finito perché se così non fosse, potrebbero esserci simboli così simili da poter esser confusi. Il calcolo avviene per passi successivi e discreti (spostamento a destra o sinistra, sostituzione di un simbolo, cancellazione, lettura/scrittura, cambiamento di stato, fermata), regolati da una serie di istruzioni non contraddittorie ovvero un programma. Ne consegue che dopo un numero finito di passi, il nastro non potrà che contenere un numero finito di simboli, possibilmente inframmezzati da celle vuote. Possiamo prendere la MT come modello canonico di calcolatore perché ogni algoritmo che può essere implementato su un computer può essere modellato da qualche MT. Le MT manipolano dunque espressioni su un nastro che funge da medium per gli input e per gli l’output e, contemporaneamente, da memoria di lavoro nel corso della computazione. L’arbitrarietà dei simboli permette alle MT di lavorare su numeri o loro rappresentazioni simboliche opportune. La possibilità di associare numeri a MT, permette di applicare MT a MT: in particolare si può costruire una MT che avendo come input due elementi, il primo dei quali è il numero di un’altra MT, simula l’applicazione di quest’ultima al secondo elemento. La MT con queste caratteristiche si chiama macchina di Turing universale ed è così in grado di simulare il comportamento di qualsiasi altra TM.
Naturalmente esistono problemi che non sono risolubili mediante un algoritmo, cioè esistono limiti di calcolo che non possono essere superati. In particolare, nell’articolo del 1936 Turing dimostra che il problema della fermata è indecidibile: non esiste alcun algoritmo che, data una generica MT e dato un generico input per essa, consenta di stabilire se la macchina con quell’input termina il calcolo oppure no. Il problema della fermata è dunque l’esempio più celebre di funzione non calcolabile. Si può definire la funzione
h = [f|per tutti i programmi p, se p termina allora f(p)= 0 altrimenti f(p)= 1]
ma non esistono regole di calcolo che danno sistematicamente il valore di h(p).
Il decimo problema di Hilbert
Il decimo problema presentato da David Hilbert al congresso internazionale di Parigi del 1900 concerneva gli algoritmi: data una qualsiasi equazione diofantea (in una o più variabili) a coefficenti interi, esiste un algoritmo per determinare se l’equazione è risolubile nel dominio degli interi? Hilbert in realtà non usava la parola algoritmo, ma parlava, analogamente, di “un procedimento” con il quale decidere la questione “mediante un numero finito di operazioni”. La teoria della calcolabilità ha permesso di inserire il decimo problema in una rigorosa cornice concettuale: nel 1960, Martin Davis, Hilary Putnam e Julia Robinson mostrano come è possibile impostare il problema della fermata in termini di equazioni diofantee e nel 1970 Jurij V. Matijasevic risponde negativamente alla questione hilbertiana: non è possibile trovare un algoritmo per determinare se l’equazione diofantea abbia soluzioni.
La complessità computazionale
Se la teoria della calcolabilità trascura deliberatamente l’analisi delle risorse che sono necessarie a un calcolo, la teoria della complessità computazionale si occupa invece degli algoritmi dal punto di vista delle risorse necessarie per il loro funzionamento. È infatti evidente che esiste una radicale differenza tra la risolubilità “in teoria” di un problema e la sua risolubilità “in pratica”: intuitivamente, la complessità di un problema è determinata dall’efficienza del migliore algoritmo che lo risolve. L’origine informale della teoria della complessità può essere fatta risalire a una lettera di Gödel del 20 marzo 1956 a John von Neumann, nella quale si chiedeva se un problema di dimostrabilità nella logica del primo ordine è risolvibile in tempo lineare o quadratico. L’origine ufficiale della teoria è nel lavoro del 1965 di Juris Hartmanis e Richard Stearns.
P indica la classe di tutti i problemi che possono essere risolti in tempo polinomiale e include tutti i problemi che possono essere risolti efficientemente dai computer. NP è la classe di tutti i problemi che possono essere risolti in tempo polinomiale non deterministico. Probabilmente, il più importante problema in informatica teorica è la questione se P = NP (è chiara l’inclusione). Un importante passo teorico per stabilire se è stato fornito negli anni Settanta del secolo scorso dal lavoro indipendente di Stephen Cook e di Leonid Levin: essi hanno scoperto l’esistenza di certi problemi in NP, cosiddetti NP-completi, la cui complessità individuale è connessa a quella dell’intera classe: un problema di classe NP è NP-completo se a esso è riducibile in tempo polinomiale ogni altro problema in NP. Se dunque un problema è NP-completo e di classe P, allora P = NP. Il primo problema che è stato dimostrato essere NP-completo è quella della soddisfacibilità di una formula della logica proposizionale in forma normale congiuntiva (con esattamente disgiunzioni ternarie). Nel 1972 Richard Karp ha mostrato la rilevanza computazionale della nozione di NP-completezza, dimostrando che otto importanti problemi combinatori appartengono a questa classe. Il repertorio dei problemi NP-completi è dunque assortito, perché comprende problemi logici, di teoria dei grafi ma anche di teoria dei numeri.