Pokémon, calcolabilità e complessità

Delle tre parole del titolo di questo post, probabilmente vi è nota solo la prima. I Pokémon sono un gruppo di mostriciattoli nati sul Gameboy. E' un marchio sorprendentemente prolifico (ha venduto più di 275 milioni di unità, lo batte solo Super Mario), che ha dato vita a cartoni, giocattoli, magliette, e ben venti lungometraggi.

Pokémon, sebbene abbia dato origine a tutte queste entità, rimane un videogioco, ovvero un programma per computer, ovvero, a dirla tutta, una funzione matematica. 
Tutti hanno bene in testa (davvero?) il concetto matematico di funzione, ovvero un sottoinsieme di tutte le coppie ordinate tra due insiemi A e B, tale che ogni elemento di A appare in una coppia una e una sola volta. Più facile pensare a una funzione come a una macchinetta che prende elementi dell'insieme A e associa un solo elemento di B, che poi può essere lo stesso elemento che la funzione associa ad un altro (se questo non avviene, la funzione è iniettiva; se poi ottieniamo tutti gli elementi di B associando ogni elemento di A, la funzione è suriettiva. Ma qui stiamo divagando.)
I programmi sono funzioni in quanto prendono in input elementi di un insieme, che possono essere i tasti del joystick, numeri naturali, immagini, frasi, e chi più ne ha più ne metta. Se si pensa che i programmi che usiamo tutti i giorni o che abbiamo utilizzato (Facebook, Google, Pokémon, ... sono tutti programmi) sono funzioni matematiche, ecco che ci viene in mente almeno un motivo (ma potremmo trovarne tanti) per cui la matematica è studiata a scuola, o almeno un motivo per cui la matematica è davvero utile.
Non tutte però le funzioni che posso scrivere sono in verità programmi. Guardiamo tre esempi di funzione:

f(x) = x
f(x) = pigreco
f(x,y) = 1 se la funzione x termina su input y, 0 altrimenti

La prima funzione è la più semplice che esiste: è la funzione identità. Essa prende in input un elemento, e, semplicemente, non fa nulla: lo restituisce così com'è.

La seconda è altrettanto semplice: restituisce pigreco, un numero irrazionale, ottenibile dividendo una qualsiasi circonferenza per il suo diametro. 

La terza prende in input due elementi, e risponde a una domanda: la funzione x (dunque x non è un numero, è una funzione!) termina su input y? Ovvero, se ho un programma x e do ad esso in pasto il dato (ora sì: è un numero) y, questo programma crasha, si pianta, o succede qualcosa? Detta in questi termini, forse la terza è la funzione più interessante di tutte.

Questi argomenti a cui ci stiamo avvicinando pian piano fanno parte di una branca dell'informatica teorica, e della matematica, denominata calcolabilità. Questa branca tenta di rispondere a una domanda: "Cosa precisamente posso calcolare con un computer?". Non parliamo del computer più potente del mondo, né dei computer che appariranno tra qualche secolo, né in verità di un computer particolare. Parliamo di ogni computer: anche quello con cui state leggendo queste righe (che sia uno smartphone, un tablet, una tv, una lavastoviglie... qualsiasi cosa abbia CPU, RAM e forse un po' di memoria secondaria, ovvero un hard disk, è un computer. Se poi avete una lavastoviglie per leggere un post su un blog, fatemi sapere il modello che mi piacerebbe valutare l'acquisto).
Quindi la calcolabilità, presa una funzione, può rispondere a una domanda: è calcolabile? Ovvero, posso scrivere un programma che calcola questa funzione?
Cosa vuol dire questo? Semplicemente, un programma che per ogni input della funzione, restituisce esattamente ciò che la funzione matematicamente calcola. Facciamo un esempio (chi ha capito può saltarlo): la funzione identità restituisce 1 se l'input è 1, 2 se l'input è 2, 3 se l'input è 3, ecc. se il mio programma per ogni input su cui è definita la funzione (ovvero i numeri naturali) risponde quello che deve rispondere, ovvero quello stesso numero dato in input, questa funzione calcola esattamente l'identità. (Forse a qualcuno sarà sorto un dubbio: ma se i numeri sono infiniti... come faccio a provare che il mio programma calcola l'identità? Per ora, auguri.)
Ora posso porvi una domanda che ho in testa da un po': quale delle tre funzioni date prima sono programmi? Ovvero, possono essere calcolate? Ovvero, ed ora in poi userò questo termine, sonocalcolabili? Si accettano scommesse.
Al di là dei dettagli tecnici, come: quale linguaggio di programmazione uso per mostrare che l'identità è calcolabile? Come faccio a mostrarlo? Mando al foto del monitor a qualcuno? Ma i numeri sono infiniti...
Al di là di tutti questi dettagli, una persona ci viene incontro, e il suo nome è Alan Turing.

Alan Turing è stato uno scienziato geniale, vissuto durante la prima metà del XX secolo, che diede contributi enormi all'informatica, ancora prima che il computer fosse inventato. Anzi, si dice che i computer veri, quelli che gli ingegneri e altri matematici come Von Neumann costruirono (cerca ENIAC su Google), a Turing stavano un po' antipatici. Alan Turing era un duro e puro, e arrivò a parlare di calcolabilità prima che la gente scoprisse cosa volesse dire calcolare automaticamente. Turing è famoso per aver decrittato, assieme a un equipe di matematici, il codice Enigma che i nazisti utilizzavano per le loro comunicazioni durante la seconda guerra mondiale, facendosi aiutare da una macchina denominata Colossus, che costruì per l'occasione (vedi il film The Imitation Game che dà una versione un po' romanzata della storia - basti pensare che la macchina nel film si chiama Christopher...).

Tornando al problema delle funzioni calcolabili, Turing arrivò a pensare a macchine che calcolano in risposta a un problema che David Hilbert, un altro matematico, formulò durante la prima metà del XX secolo per discutere i fondamenti della matematica (che in quegli anni attraversò una profonda crisi - vedi il libro interessante Il calcolatore universale di Martin Davis che ne parla ampiamente): è possibile scrivere un algoritmo che data una formula logica dica se essa è vera? Questo problema è chiamato in tedesco entscheidungsproblem, ovvero problema di decisione. Turing inventò per l'occasione una macchina per mostrare che tale algoritmo non poteva essere scritto.
Per algoritmo qui si intende una procedura eseguibile del tutto meccanicamente, poiché non esistendo i computer è difficile pensare che Hilbert avesse pensato a un programma per computer che eseguito rispondesse sì se la formula fosse stata vera e no altrimenti. Ma gli algoritmi furono inventati molto prima dei computer: uno dei più antichi fu quello di Euclide per calcolare il massimo comune divisore (stiamo parlando del 300 a.C.!).
Turing inventò dunque una macchina, che oggi porta il suo nome, che sorprendentemente fa tutto quello che un computer può fare: essa è la Macchina di Turing (di seguito anche MdT), ed è veramente molto semplice. Contiene:

·         un nastro infinito a quadretti su cui si può leggere e scrivere un quadretto alla volta; 

·         una testina che può leggere e scrivere sul quadretto;

·         un piccolo display su cui è scritto in che stato è la macchina;

·         un piccolo cervello che capisce cosa c'è scritto sul quadretto letto, e può scrivere un nuovo simbolo e cambiare eventualmente stato sul display

Una tesi chiamata di Church-Turing dice che una funzione è calcolabile solo se è calcolabile tramite una MdT. Questo è veramente sorprendente.

In pratica stiamo dicendo che un qualsiasi programma per computer (sì: Google, Facebook,Pokémon...) può essere scritto per la macchina di Turing, ovvero potrei controllare i post su Facebook, cercare su Google e giocare a Pokémon anche con una MdT!

La MdT è così importante che oggi per provare diverse questioni nell'informatica teorica si fa ancora ricorso ad essa. Grazie alla tesi di Church-Turing, comunque, per mostrare che una funzione è calcolabile basta esibire un algoritmo che la calcola, scritta in un linguaggio più o meno umano. 

Così, posso mostrare un algoritmo per calcolare l'identità (return è usato per esprimere restituisci, ovvero esibisci in output):

id(x): return x

o che calcoli pigreco

pi(x): return pigreco

Certo è che pigreco è un numero irrazionale. Questo è un problema: il numero di cifre dopo la virgola è infinito, e qualsiasi computer non ha abbastanza spazio per contenerlo tutto. E' il solito problema dei numeri infiniti. 

Tuttavia, quel pigreco è un'approssimazione abbastanza adeguata del numero: a nessuno servirà mai avere tutte le cifre di pigreco in mano. Quindi la funzione pi è sì calcolabile, ma sempre tenendo conto che non avrò mai una risposta completa dalla funzione, bensì una risposta di cui mi devo accontentare.

Turing grazie alla MdT mostrò che la terza funzione di cui abbiamo parlato, quella che restituisce1 se la funzione x termina su input y, non è calcolabile. Infatti, se si potesse scrivere una funzione del genere, si andrebbe facilmente in contraddizione. Chi è interessato può vedere il libro Teoria della calcolabilità e complessità di Toffaroli et al. edito da McGraw-Hill.

Le MdT dunque offrono un modello di calcolo universalmente riconosciuto: i computer di oggi ne sono addirittura un approssimazione (infatti nessun computer può avere memoria infinita come la MdT). Vi sono altri modelli di calcolo, come il lambda-calcolo di Church (che dà il nome alla tesi vista prima) e le funzioni ricorsive di Kleene. Ma vi possono essere altri modelli di calcolo, o per così dire sistemi di calcolo.
Un modello di calcolo si dice turing-completo se fa tutto quello che la MdT può fare. Un sistema di calcolo può essere dato anche da un linguaggio di programmazione, che permette una certa espressività nel definire funzioni. Per esempio, un linguaggio che abbia il costrutto while è turing-completo, mentre non lo è uno che fornisca solo il for (come scrivo un ciclo infinito?). Cerca le definizioni su Google se sei interessato.

Una domanda a cui non risponde la calcolabilità è: "Quanto tempo impiego a calcolare una funzione?". Ovvero, quanto è complessa la mia funzione? A questo ci pensa la teoria dellacomplessità, la quale si occupa di analizzare le funzioni calcolabili dal punto di vista dell'utilizzo delle risorse (tempo, spazio e ultimamente anche energia).

Il tempo di esecuzione di una macchina dipenda da quante cose fa la macchina mentre calcola. Ad esempio, per calcolare l'identità la MdT praticamente non fa nulla. Sta nel suo stato, e basta. Quindi si può dire che la MdT calcola il suo output in un tempo costante, ovvero che non dipende dall'input.

Per la funzione pi la situazione è la stessa: infatti anche se devo scrivere pigreco, questo tempo non dipende dall'input, bensì da quante cifre di pigreco voglio scrivere. Il numero di operazioni è sempre costante, e dipende da tale numero.

Introduciamo una funzione un po' più complicata ma abbastanza celebre:

max(x,y) = il massimo tra x e y

per calcolare questa funzione (che è ovviamente calcolabile) devo fare un numero di passi che dipende dal massimo dei due numeri dati in input. Infatti una MdT dovrebbe verificare quale dei due è più grande, e quindi esaminarli entrambi! Si dice che una funzione del genere è lineare nei suoi input. infatti deve fare un numero di passi che dipende linearmente da essi.

Dipende linearmente vuol dire che la funzione che descrive quanti passi deve fare la MdT calcolando max non ha esponenti, ovvero è un polinomio in un numero n, che rappresenta lalunghezza (non il valore!!) dei numeri dati in input. 

Si possono avere polinomi più complicati? Certo che sì: possiamo avere polinomi con esponente 2, 3, 4, ... , e in generale qualsiasi esponente che sia un numero naturale.

Ad esempio, un algoritmo quadratico (ovvero la cui complessità è rappresentata da un polinomio di grado 2) anch'esso abbastanza celebre è l'ordinamento per inserimento, che ordina gli elementi di una lista di oggetti in un modo particolare (vedi insertion sort su Wikipedia).

La complessità divide i problemi che possono essere calcolati facilmente da un computer da altri che invece non possono esserlo (per ora...): la classe P è la classe dei problemi che possono essere risolti da una MdT in un tempo al più polinomiale.

Una tesi, questa volta di due signori che sono Cook e Karp (i padri di questa materia, praticamente hanno fatto tutto loro), dice che un computer può calcolare una funzione in maniera efficiente se essa appartiene a P, ovvero se essa ammette algoritmo di calcolo polinomiale. In P ci sono i problemi visti fin qui: l'identità, pigreco, max, insertion sort, ma anche Google e Facebook (certo che è da dimostrare ma intuitivamente questi ultimi due servizi sono molto "facili" da fruire, e forse il loro successo lo si deve anche a questo).
Una domanda che si può fare è: Pokémon appartiene a P? Ognuno può provare a rispondere, per ora.

Se ci sono problemi per così dire trattabili, ovvero che un computer può risolvere senza troppi problemi, ve ne sono anche di intrattabili, ovvero quelli che ammettono algoritmo di calcolo che non è polinomiale, ma almeno esponenziale. 

Esiste un'altra classe di problemi interessante, che è la classe NP, ovvero la classe dei problemi che ammettono una verifica polinomiale. Questo vuol dire che ci metto tanto a risolvere il problema, ma una volta risolto verificare che la soluzione è quella giusta è questione di un attimo!

La classe NP contiene i più celebri rompicapo: il Sudoku, alcuni problemi di enigmistica, ma anche la battaglia navale e Candy Crush.

Uno dei più importanti problemi aperti (= a cui nessuno ha dato ancora una risposta) dell'informatica è determinare se la classe P sia uguale o meno alla classe NP. Su due piedi uno direbbe di no.

Tuttavia, il problema che consiste nel chiedersi se un numero dato in input è primo o meno è stato in NP fino al 2002. Infatti, cosa fareste voi per verificare che un numero è primo, intuitivamente? 

"Semplicemente", prendete tutti i numeri prima del numero dato e provate a dividere il vostro numero per ognuno di questi. Se trovate un divisore, potete fermarvi, altrimenti no. Ecco quindi che fate n passi, dove n è il numero dato in input (non la sua lunghezza, però: il suo valore!), e in ogni passo fate una divisione, il cui tempo potremmo chiamarlo d. I passi in tutti sono n per d, man è il valore del numero dato in input, che dipende esponenzialmente dalla sua lunghezza. Ecco quindi che l'algoritmo è esponenziale! Per niente polinomiale, la funzione esponenziale cresce più di qualsiasi polinomio. Se provate a verificare se 123 è primo ci mettete già un po' di tempo. 

Tre ricercatori hanno scritto questo articolo in cui dimostrano che questo problema, chiamato PRIMES, è in P. Questo può alimentare i dubbi sulla questione P = NP. Uno scienziato ha detto poeticamente che se P fosse uguale NP verificare che una soluzione è quella giusta e trovare la soluzione sarebbe uguale: chiunque capisca la bellezza di una sinfonia sarebbe Mozart, chiunque comprenda una dimostrazione matematica sarebbe Gauss, chiunque ammiri una bella punizione dal limite dell'area sarebbe Del Piero. Guarda qui una discussione sull'argomento.

Esistono problemi poi che sono più difficili di tutti quelli che stanno in NP. Questi problemi in qualche modo rappresentano tutti i problemi in NP, e si chiamano problemi NP-completi. In pratica, se p è un problema NP-completo, preso un qualsiasi problema p2 in NP esso può essere trasformato in p, ovvero se risolvo p con i dati che ho fornito a p2, risolvo anche p2. Guarda quiuna lista di problemi NP-completi. 

Se qualcuno è arrivato a leggere fin qui, potrebbe benissimo chiedere: ma cosa c'entra Pokémon con tutto questo? Forse l'autore è impazzito?

A mia discolpa, voglio dirvi che Pokémon calza a pennello con tutti questi argomenti. Quindi forse il vero interesse arriva qui, ma la lunga premessa era necessaria. A questo punto possiamo enunciare due proposizioni:

Proposizione 1. Pokémon Giallo è turing completo

A sostegno di questa proposizione, vi è un bell'esperimento che puoi trovare qui, e che riassumerò spero agilmente. L'autore parla di com'è possibile scrivere un qualsiasi programma utilizzando Pokémon Giallo. L'ispirazione, racconta lui stesso, gli venne guardando questa speedrun su Youtube, in cui un giocatore riusciva a finire Pokémon Giallo in meno di due minuti, creando una warp door dalla casa del protagonista e saltando direttamente alla fine del gioco. Sostanzialmente, il giocatore prende in giro il gioco stesso, facendo in modo che lui stesso creda di essere finito. Si può fare facilmente lo stesso con i Pokémon della serie Game Boy Advance, come Rubino e Zaffiro, visto i molteplici software che sono a disposizione per modificare il gioco dal computer: è infatti possibile creare una porta come quella che ha creato l'autore della speedrun, saltando direttamente alla fine.
L'autore, Robert McIntyre, parla del gioco da un punto di vista piuttosto generale. Ogni gioco presenta delle regole, che il giocatore deve rispettare per risolverlo. Per la verità, un sistema automatico volto ad eseguire questo gioco non permette di modificare le regole dello stesso. Così, un gioco di scacchi per computer non permette di trasformare gli scacchi in dama, o in Tetris. Sorprendentemente, in Pokémon Giallo è diverso. Si mostra com'è possibile programmare il Gameboy attraverso Pokémon Giallo, semplicemente sfruttando un piccolo bug presente nel videogioco, che crea una specie di assurdo nella funzione (perché ricordate che di funzione si tratta;
quando si crea l'assurdo in informatica o in matematica, succedono sempre cose molto interessanti...)
Se si va oltre alla regole di tenere 20 strumenti nello zaino, si fa andare in contraddizione tutto quanto. I programmatori, evidentemente, questo non lo avevano previsto.
Così, chiunque può creare un programma parlando direttamente al Gameboy interagendo con la lista di oggetti. Un po' più approfonditamente, il Gameboy ha istruzioni lunghe 8 bit, che rappresentano essenzialmente comandi a basso livello (prendi questo dato e mettilo nel registro B, verifica che è stato premuto il tasto A, ...). Se qualcuno è sufficientemente esperto, può, acquisendo i giusti strumenti, trasformare Pokémon nel gioco che vuole. Questo poiché gli strumenti sono codificati tramite numeri a 8 bit, e possono essere interpretati come istruzioni.
I dettagli tecnici sono piuttosto difficili da comprendere. Questo video mostra com'è possibile scrivere una canzone MIDI e disegnare una figura utilizzando questa procedura.

Arrivati fin qui, si potrebbe dimostrare la proposizione 1 formalmente, partendo da un linguaggio turing completo come C, o un linguaggio giocattolo (tipo il linguaggio WHILE), e mostrando che i costrutti esprimibili in Pokémon sono equivalenti a quelli presenti in esso. 

Dunque, tirando le somme, Pokémon Giallo crea un ambiente di sviluppo in grado di descriverequalsiasi algoritmo: è possibile scrivere in questo modo qualsiasi programma vi venga in mente!

La seconda proposizione che enunciamo non riguarda l'alterazione delle regole del gioco di Pokémon, bensì una loro diretta conseguenza.

Proposizione 2. Pokémon è NP-completo

Ebbene sì: tutti quelli che hanno giocato a Pokémon ci hanno messo parecchio a finirlo, la prima volta. Tuttavia, una volta che si sa dove si deve andare e quali strumenti acquisire, il gioco diventa piuttosto banale. Si dimostra, questa volta formalmente, che Pokémon è NP-completo. La tecnica per fare questo, essenzialmente, è una tecnica di riduzione da un altro problema NP-completo. Infatti, se si riduce un problema NP-completo a un altro problema in NP, quest'ultimo diventa NP-completo.
Il primo problema importante che è stato dimostrato essere NP-completo è SAT, o problema della soddisfacibilità di formule booleane: data una formula booleana, ovvero scritta utilizzando connettivi logici quali AND, OR e NOT, trovare un'assegnazione delle variabili che rende vera la formula. Dimostrare che questo problema è NP-completo richiede molta fatica, ma qualcuno l'ha fatto.
Per dimostrare che Pokémon è NP-completo si riduce da SAT quest'ultimo, utilizzando unacostruzione che già è stata utilizzata per risolvere un altro gioco, che è PUSH, che consiste nel spostare scatole in punti precisi di una mappa. Anche questo gioco è NP-completo.
La dimostrazione è tutto tranne che banale. Sostanzialmente, si implementano dei gadget, come li chiamano gli autori, tali per cui ogni situazione del gioco è riducibile a questi ultimi. Guardatel'articolo originale se siete curiosi.
Come si vede dall'articolo, non solo Pokémon è NP-completo, ma anche Super Mario, Metroid, Zelda, Donkey Kong. Molti giochi famosi sono NP-completi.
Questa NP-completezza è legata alla questione P = NP. Infatti c'è un teorema che dice che se S è un problema NP-completo e S sta in P, allora P è uguale a NP. La dimostrazione è banale.
Tuttavia, suggerisce una tecnica per dimostrare che P è uguale a NP. Se si mostra una procedura veloce per finire Pokémon rispettando le sue regole (quindi niente warp room!), allora P è uguale a NP! Questo è alquanto sorprendente. Lo stesso vale per ogni problema NP-completo, quindi Super Mario, Metroid, Zelda, ...
Che dire? Per dimostrare P = NP (e portarsi a casa 1 milione di dollari!), magari si scoprirà che la strada giusta è studiare i videogiochi della Nintendo!

Molte delle cose scritte in questo post sono state prese dal libro di Toffalori et al. citato più su. Ho linkato agli articoli citati.