INDAGINE SUI LIMITI DELLA CALCOLABILITÀ– INTERVISTA AL PROF. ALFREDO GARRO

La matematica cambia, la statistica cambia, ma nessuno se ne accorge. La maggior parte delle persone evidentemente pensa che la matematica e la statistica siano una specie di credenza che non può mai cambiare per coloro che ci credono (mentre non esiste per coloro che non ci credono). È invece noto a tutti che la matematica e la statistica rientrano nelle discipline scientifiche e, come tali, cambiano, evolvono e si modificano anche in seguito all’elaborazione di nuovi strumenti di indagine.

Ho scritto su questo argomento più volte, ma in modo più completo nel libro: “Non è colpa della statistica”, pubblicato da C1V Edizioni il 7 marzo 2023. Il linguaggio matematico utilizzato in un certo contesto può condizionarci al punto da impedirci di osservare in modo completo l’oggetto di studio. E, insomma, potremmo finire in un vicolo cieco, a meno che ci rendiamo conto di quanto sia importante cambiare linguaggio / metodo / strumento matematico, al fine di migliorare letteralmente le nostre capacità di calcolo. In questo periodo di discute molto di calcolo automatico, soprattutto di che tipo di “intelligenza” abbiano gli algoritmi che ormai, soprattutto tramite i computer e gli smartphone, popolano la nostra vita, al punto da essere diventati quasi delle “estensioni” delle nostre capacità cognitive.

A questo punto una domanda del genere: “Cosa è calcolabile?” diventa di interesse generalizzato. È quindi il caso di leggere: “Osservabilità delle macchine di Turing. Un raffinamento della teoria del calcolo”, un lavoro di Yaroslav D. Sergeyev e Alfredo Garro (del Dipartimento di Elettronica, Informatica e Sistemistica dell’Università della Calabria). Possiamo considerare una macchina di Turing come un dispositivo astratto di calcolo, da utilizzare per indagare i limiti della calcolabilità, considerando però un determinato linguaggio matematico (sia quello “tradizionale” che uno nuovo trattato nel lavoro sopra citato). Ciò in quanto “questa situazione è esattamente la stessa che si verifica nelle scienze naturali: prima di cominciare a studiare un oggetto fisico, lo scienziato sceglie uno strumento e la sua accuratezza per lo studio” scrivono Sergeyev e Garro, aggiungendo poi: “dove è ben noto che lo strumento influenza i risultati delle osservazioni”.

Entriamo quindi nel merito della questione ponendo alcune domande direttamente al Prof. Alfredo Garro.

- Che cos’è una macchina di Turing?

Nel 1936 in un articolo intitolato "On Computable Numbers, with an Application to the Entscheidungsproblem", Alan Turing affrontò il cosiddetto “Problema della Decisione” (Entscheidungsproblem appunto) posto da David Hilbert nel 1928 nell’ambito della sua opera di sistematizzazione dei fondamenti della matematica. Il problema consiste nel determinare se esiste una procedura “eseguibile meccanicamente” (oggi diremmo un algoritmo) per decidere se un dato enunciato matematico può essere dimostrato o meno. Nell’articolo Turing riesce a dimostrare che tale procedura non esiste proponendo ed avvalendosi di un modello di calcolo astratto, noto oggi, appunto, come “Macchina di Turing”. 

La macchina di Turing è costituita da un nastro infinito, diviso in celle, su cui possono essere letti e scritti simboli di un alfabeto finito. La macchina ha un'unità di controllo che può leggere un simbolo dal nastro e, in base al simbolo letto, può cambiare lo stato di elaborazione della macchina, scrivere un nuovo simbolo sul nastro e spostare il nastro a sinistra o a destra. La macchina di Turing non è l’unico modello di calcolo astratto presente in letteratura; tuttavia, la sua elegante definizione ed il suo “potere computazionale” l’hanno resa lo strumento di elezione per investigare i limiti della computabilità e fornire le basi per la creazione di linguaggi di programmazione e di altre tecnologie informatiche che utilizziamo quotidianamente. Quando parlo di “potere computazionale”, in particolare, mi riferisco, ad esempio, ai risultati prodotti dal matematico e logico americano Alonzo Church che nella sua famosa “tesi” sostiene che ogni funzione calcolabile può essere calcolata da una macchina di Turing; ossia, con un lessico più moderno, che ogni algoritmo eseguibile può essere eseguito da una macchina di Turing e che, quindi, le macchine di Turing rappresentano un modello universale per il calcolo automatico. Ciò significa che ogni problema calcolabile può essere risolto da una macchina di Turing e che la macchina di Turing fornisce una definizione rigorosa e unificante del concetto di calcolabilità.

I lavori di Turing e Church completano, di fatto, l’opera iniziata da Kurt Gödel dimostrando che la calcolabilità ha dei limiti intrinseci e che non tutti i problemi possono essere risolti in modo algoritmico: proprio il “Problema della Decisione” di Hilbert da cui siamo partiti ne è un esempio. Ciò deriva direttamente dalla natura incompleta della logica matematica: in ogni sistema assiomatico sufficientemente complesso, esiste almeno una proposizione che non può essere dimostrata all'interno del sistema stesso. Questo significa, appunto, che non esiste un algoritmo generale per dimostrare tutte le proposizioni matematiche come probabilmente sognava Hilbert.

La macchina di Turing è, tuttavia, anch’essa un oggetto matematico che possiamo descrivere ed osservare, nelle computazioni che svolge, usando linguaggi matematici diversi. Il linguaggio matematico scelto modifica ciò che riusciamo ad osservare proprio come una lente di un microscopio con un potere di ingrandimento maggiore ci permette una maggiore accuratezza nelle risposte che forniamo analizzando con essa un particolare campione di materiale. Il linguaggio usato da Turing era essenzialmente quello di George Cantor ed usando quel linguaggio è possibile arrivare ad un dato livello di accuratezza. Quando si considerano macchine di Turing che eseguono un numero infinito di passi, ad esempio, esso non permettere di distinguere macchine di Turing che sono in grado di gestire un numero diverso di simboli, che operano su un numero diverso di nastri, oppure che operano in modo deterministico e non deterministico nella scelta della prossima operazione da eseguire durante una computazione. Nel nostro lavoro dimostriamo come, descrivendo ed analizzando le macchine di Turing con un linguaggio matematico diverso, sia possibile, invece, distinguere con maggiore accuratezza le computazioni eseguite da macchine di Turing che, osservate con il linguaggio matematico di Cantor/Turing, risultano essere del tutto indistinguibili soprattutto quando eseguono un numero infinito di passi o computano sequenze infinite di simboli.

- Quali sono le differenze fra una macchina di Turing immaginaria ed una fisica?

Una macchina di Turing immaginaria è un modello teorico astratto, mentre una macchina di Turing fisica è un dispositivo reale costruito con una specifica tecnologia che ha limiti fisici e può essere soggetto a problemi e malfunzionamenti tecnici. Le macchine di Turing immaginarie sono in grado di eseguire un numero infinito di passi di computazione, le macchine di Turing fisiche sono, invece, limitate dall’energia, dal tempo e dalla memoria disponibile e, quindi, possono eseguire solo un numero finito di passi di computazione.

Considerare macchine di Turing che eseguono un numero infinito di passi è, tuttavia, utile nella teoria della computazione per definire, ad esempio, la computabilità di una funzione o di un problema e le diverse classi di complessità computazionale. Nel nostro lavoro, in particolare, proprio considerando computazione infinite riusciamo, impiegando un nuovo linguaggio matematico, ad osservare con maggiore accuratezza i comportamenti di macchine di Turing che se descritti ed osservati con il linguaggio matematico tradizionale risulterebbero del tutto equivalenti.

- Che cos’è un algoritmo?

Un algoritmo è una sequenza finita di passi o istruzioni che descrivono come risolvere un determinato problema o compito. Ogni istruzione deve essere chiara, precisa, facilmente comprensibile ed eseguibile in un tempo finito. Un algoritmo deve essere in grado di acquisire e gestire dei dati in ingresso (input) e di produrre un risultato (output) corretto con una data accuratezza. Un algoritmo può essere descritto in molti modi, ad esempio: mediante un modello di calcolo astratto quale una macchina di Turing; attraverso pseudocodice, ossia combinando elementi del linguaggio naturale attraverso specifiche regole sintattiche; utilizzando un linguaggio di programmazione.

- Quali vantaggi si ottengono applicando un sistema numerale più preciso?

L'utilizzo di un sistema numerale più preciso può offrire diversi vantaggi, tra cui maggiore accuratezza nei calcoli, gestione degli errori di arrotondamento, migliore rappresentazione dei numeri reali e maggiore efficienza in molte procedure di calcolo. Nel nostro lavoro, ad esempio, impieghiamo, per la descrizione e l’osservazione delle computazioni eseguite da macchine di Turing, un nuovo sistema numerale, proposto alcuni anni fa dal prof. Sergeyev, che permette di rappresentare numeri infiniti ed infinitesimi con una accuratezza che consente di poter distinguere ed eseguire operazioni aritmetiche con grandezze finite ed infinitesime indistinguibili se descritte applicando un sistema numerale tradizionale. Nel caso specifico, l’applicazione del nuovo sistema numerale (basato sull’introduzione di un nuovo simbolo chiamato “Grossone”) ci ha permesso di caratterizzare meglio il comportamento di macchine di Turing con proprietà diverse che risultavano del tutto equivalenti se osservate impiegando il linguaggio matematico tradizionale di Cantor/Turing.

- Quali sono le conclusioni del suo lavoro?

Dall'inizio del secolo scorso, la natura fondamentale del concetto di computazione automatica ha attirato grande attenzione da parte di matematici e informatici. I primi studi avevano come contesto di riferimento il programma di David Hilbert e come linguaggio di riferimento quello introdotto da Georg Cantor. Tali studi portarono ad introdurre diversi modelli di calcolo astratto che, sorprendentemente, sono risultati essere equivalenti (ad esempio, qualsiasi cosa sia calcolabile nel λ-calcolo introdotto da Alonzo Church è calcolabile da una macchina di Turing). Questi risultati, e, come discusso in precedenza, soprattutto quelli ottenuti da Turing, Church e Gödel, hanno di fatto dimostrato che il programma di David Hilbert, basato sull'idea che tutta la Matematica potesse essere assiomatizzata, non può essere realizzato. Ciononostante, l'idea di trovare un insieme adeguato di assiomi per i diversi campi della matematica continua ad essere tra gli obiettivi più attraenti per i matematici contemporanei. Di solito, quando è necessario definire un concetto o un oggetto, i logici cercano di introdurre una serie di assiomi che descrivano l'oggetto nel modo più completo possibile. Tuttavia, non è chiaro come raggiungere questa assolutezza; infatti, quando descriviamo un oggetto matematico o un concetto siamo limitati dalla capacità espressiva del linguaggio che usiamo per fare questa descrizione. Un linguaggio più ricco ci permette di dire di più sull'oggetto e un linguaggio più debole - meno. Così, il continuo sviluppo dei linguaggi matematici (e non solo matematici) porta ad una continua necessità di trascrizione e specificazione dei sistemi assiomatici. In secondo luogo, non vi è alcuna garanzia che il sistema assiomatico scelto definisca "sufficientemente bene" il concetto richiesto ed è necessario un confronto continuo con la pratica per verificare la bontà dell'insieme accettato di assiomi. Tuttavia, non può esserci nuovamente alcuna garanzia che la nuova versione sarà l'ultima e la definitiva. Infine, una terza limitazione, già menzionata in precedenza, è rappresentata nei due famosi teoremi di incompletezza di Gödel.

Partendo da queste considerazioni, nel nostro lavoro, le macchine di Turing dotate di nastro singolo (Single-tape) e multiplo (Multi-tape) sono state descritte e osservate attraverso la lente di un nuovo linguaggio matematico. Questo nuovo linguaggio, a differenza di quello tradizionale, permette di distinguere tra infinite sequenze di diversa lunghezza consentendo una più accurata descrizione delle macchine di Turing a nastro singolo e multiplo. La possibilità di esprimere esplicitamente la lunghezza di una sequenza infinita dà la possibilità di stabilire risultati più accurati riguardo all'equivalenza fra macchine di Turing rispetto alle osservazioni che si possono fare utilizzando il linguaggio matematico tradizionale di Cantor/Turing.

Vale la pena notare che i risultati tradizionali e quelli presentati nel nostro lavoro non si contraddicono a vicenda. Entrambi i linguaggi matematici osservano e descrivono gli stessi oggetti – le macchine di Turing – ma con accuratezza diversa. Di conseguenza, sia i risultati tradizionali che quelli nuovi sono corretti rispetto ai linguaggi matematici utilizzati per esprimerli e corrispondono a diverse accuratezze dell'osservazione. Questo fatto è una delle manifestazioni della relatività dei risultati matematici formulati utilizzando diversi linguaggi matematici, allo stesso modo in cui l'uso di una lente più forte in un microscopio dà la possibilità di distinguere più oggetti all'interno di un oggetto che sembra essere unico se visto da una lente più debole. In particolare, il nuovo linguaggio matematico utilizzato nel nostro lavoro, denominato “Grossone”, ha permesso di dare la definizione di output completo di una macchina di Turing, di stabilire quando e come si può osservare l'output completo di una macchina e di fornire una relazione più accurata tra macchine di Turing a nastro singolo e multiplo, così come tra macchine di Turing deterministiche e non deterministiche.

I risultati che abbiamo ottenuto mostrano che esistono limitazioni nella simulazione di macchine di Turing non deterministiche da parte di macchine deterministiche. Queste limitazioni possono essere ora osservate grazie alla possibilità, data dall'introduzione del nuovo linguaggio matematico, di osservare gli stati finali dei processi sequenziali di computazione sia nei casi di processi finiti sia nei casi di processi infiniti. I teoremi che abbiamo dimostrato e i loro corollari mostrano che le limitazioni scoperte e le relazioni tra macchine di Turing deterministiche e non deterministiche hanno forti legami con le nostre capacità matematiche di descrivere processi di calcolo automatico e di costruire modelli per tali descrizioni. Tale relatività nell’osservazione dei modelli di calcolo astratto, legata al linguaggio impiegato per la loro descrizione e all’accuratezza con cui tale linguaggio è in grado di distinguere le computazioni da essi eseguite, finite o infinite che siano, dovrebbe portare a ripensare non solo la formulazione, ma anche a meglio caratterizzare i limiti delle soluzioni fornite ad importanti problemi aperti di informatica teorica e teoria della complessità.

Riferimenti

    1. Y. Sergeyev, A. Garro. Observability of Turing Machines: a Refinement of the Theory of Computation. Informatica, 21(3):425-454, 2010, ISSN 0868-4952, IOS Press, Amsterdam, The Netherlands.

    2. Y. Sergeyev, A. Garro. Single-tape and Multi-tape Turing Machines through the lens of the Grossone methodology. The Journal of Supercomputing, 65(2):645-663, 2013, ISSN 0920-8542, Springer-Verlag Berlin Heidelberg, Germany.

    3. Y. Sergeev, A. Garro. The Grossone Methodology Perspective on Turing Machines. In Automata, Universality, Computation. Cap. 7, pp. 139-169, 2015, ISBN 978-3-319-09038-2, Springer-Verlag Berlin Heidelberg, Germany.

Prof. Dr.-Ing. Alfredo Garro - Associate Professor of Computer Engineering - University of Calabria - Department of Informatics, Modeling, Electronics and Systems Engineering (DIMES)

intervistato da Walter Caputo - Divulgatore in Scienze Statistiche - Autore di "Non è colpa della Statistica" - C1V Edizioni, Roma, 2023