Siamo consapevoli di usarne una ogni giorno?
Ogni computer con cui abbiamo a che fare quotidianamente è sostanzialmente una macchina di Turing
I CAPTCHA
Chi non è perseguitato dai CAPTCHA quando deve connettersi a qualche sito internet vagamente sensibile?
E chi non ricorda Deckard-Harrison Ford in Blade Runner fare quegli strani interrogatori per individuare gli androidi?
Bene, CAPTCHA sta per “Completely Autometed public Turing test to tell Computers and Humans Apart, cioè test di Turing per distinguere I computer dagli umani.
E anche gli interrogatori condotti da Deckard con quelle domande apparentemente astruse hanno lo stesso scopo di capire se l’interrogato è un umano o una macchina
IL TEST DI TURING
In entrambi i casi si tratta di versioni specifiche del famoso test di Turing inventato nel 1950 ed esposto in uno dei saggi più citati della storia dell’information technology, Computing Machinery and Intelligence, comparso sulla rivista Mind.
La tesi di fondo sostenuta in quell’articolo è che una macchina può dirsi pensante solo se un osservatore ponendole delle domande non riesce a distinguerla da un umano.
Il test è tutt’ora valido, nel senso che nessuna macchina lo ha superato -anche se le domande sono semplici- per via del paradosso di Moravec, secondo il quale le macchine sanno fare cose per noi difficili relativamente bene, mentre non riescono a fare cose facilissime (sempre per noi).
Ad esempio e semplificando, se un CAPTCHA chiede di identificare delle lettere scritte male, il compito è semplice (relativamente) per noi mentre è molto complicato per un programma.
ALAN MATHISON TURING (1912-1954) E L’INFORMATICA MODERNA
Quando scrive questo articolo che sta alla base dell’intelligenza artificiale, in realtà Turing è già un matematico, logico e crittografo famoso.
Infatti è del 1936 il suo studio On Computable Numbers, with an Application to the Entscheidungsproblem.
In questo paper Turing getta le basi dell’informatica moderna inventando le macchine di Turing allo scopo di fornire una risposta a uno dei problemi posto dal grande matematico Hilbert.
David Hilbert sosteneva che la matematica fosse un sistema formale, cioè un sistema algoritmico basato su degli assiomi logici autoevidenti dai quali si possono dedurre in modo automatico e senza ricorrere a fantomatiche entità come l’intuizione, tutti i teoremi e gli enunciati veri all’interno di quel sistema. Un simile sistema formale doveva avere tre caratteristiche. Innanzitutto doveva essere coerente, cioè non generare contraddizioni tra i suoi enunciati. Quindi essere completo, cioè permettere di derivare tutti gli enunciati veri a partire dagli assiomi. E infine essere decidibile, cioè avere delle procedure tali da permettere di decidere della verità di ogni enunciato.
Nel 1930 Kurt Goedel con i suoi due teoremi di incompletezza aveva già fatto a pezzi l’idea che un sistema formale di questo tipo sia completo e coerente, nel senso che se è coerente non è completo e viceversa se è completo non è coerente.
LE MACCHINE DI TURING
Turing si occupa di confutare anche la decidibilità.
Per far questo inventa la macchina di Turing, il vero prototipo dei computer moderni e il modello della computabilità.
Le macchine di Turing consistono di un nastro dove sono scritti degli 0 e degli 1, e di una “testina” che può muoversi lungo il nastro e leggere, scrivere o cancellare i simboli che trova secondo le istruzioni che la “testina” contiene (il suo stato interno).
Ogni macchina di Turing è programmata per risolvere un compito (tipo moltiplicare o sommare e così via), ma si possono simulare varie macchine di Turing con una sola macchina inputandogli le istruzioni delle altre macchine sotto forma di programmi (di 0 di 1, in ultima analisi).
È il concetto alla base dei computer programmabili o general purpose, di cui quindi Turing è il precursore e l’inventore a livello teorico: ogni computer con cui abbiamo a che fare quotidianamente è sostanzialmente una macchina di Turing.
IL TEMA DELLA DECIDIBILITA’
È importante sottolineare come la macchina di Turing sia un modello teorico della computabilità ancora valido al giorno d’oggi, anzi del più potente modello di computabilità, in grado di computare qualsiasi problema.
Qualsiasi? Non proprio.
E qui torniamo al tema della decidibilità proposto da Hilbert.
Turing procede come segue.
Poniamo che esista una macchina di Turing (quindi una procedura formale di computabilità, un programma) in grado di decidere della verità di ogni enunciato matematico, cioè di dire se esiste un programma che arriva a decidere se un problema è risolvibile in un numero finito di step o il programma gira all’infinito (per esempio in grado di dire se la congettura di Goldbach, secondo la quale ogni numero pari superiore a 2 è la somma di due numeri primi, sia vera).
Chiamiamo questo programma Hal.
Ora immaginiamo un altro programma che chiamiamo C1P8, che si limita a fare esattamente il contrario di quello che fa Hal.
Se imputiamo un programma in Hal, Hal sa dirci se quel programma si ferma perché raggiunge un risultato o gira in eterno.
Ma ora immaginiamo di inputare C1P8 in Hal. Se C1P8 gira in eterno Hal ci dirà che C1P8 gira in eterno e quindi C1P8 si fermerà, mentre se se C1P8 si ferma Hal ci dirà che C1P8 si ferma e quindi C1P8 girerà in eterno: insomma se C1P8 gira in eterno allora si ferma e viceversa se si ferma allora gira in eterno.
Con ciò viene confutata la possibilità di avere un sistema logico formale che contenga una procedura automatica per dimostrare tutti gli enunciati veri del sistema stesso, senza incorrere in contraddizioni come quella di Hal e C1P8.
Il terzo principio di Hilbert, la computabilità di tutti gli enunciati, cade, così come erano caduti il principio di completezza e quello di coerenza per mano di Goedel.
Da notare come al cuore delle prove di Goedel e di Turing ci sia sempre l’impossibilità di un sistema di parlare di sè stesso senza incorrere in paradossi insormontabili.
Risultato?
Nella matematica in quanto sistema formale esistono enunciati che sono indecidibili seguendo le regole del sistema stesso, ed esistono problemi che nessun computer può risolvere.
RINGRAZIAMO PER IL CONTRIBUTO PAOLO RICCARDO FELICIOLI