backup del Post

Google e Turing

Io ho una teoria. La percezione di Google da parte della gente è migliore di quella di Microsoft per un’unica ragione: i doodle, i disegnini – ma non solo – che ogni poco compaiono nel motore di ricerca al posto dell’usuale scritta “Google”. Soprattutto da quando ogni tanto sono stati aggiunti quelli dinamici – a me così al volo viene in mente quello per Pac-Man, il ricordo di John Lennon e quello di Stanislaw Lem – sono in molti a pensare “gente che perde tempo a preparare cose come queste deve essere fondamentalmente buona”. Ah, il marketing…

Beh, oggi ricorre il centesimo anniversario della nascita di Alan Matheson Turing (ne avevo parlato ieri sul mio blog, ma anche qui sul Post potete trovare un articolo su di lui) e i googlisti hanno pensato di inserire una (finta) macchina di Turing in suo ricordo! Quando oggi si apre la home page del motore di ricerca, si vede un nastro che si muove su e giù, mentre si scrivono e cancellano numeri 0 e 1 per comporre i successivi numeri binari. Ma naturalmente la parte più divertente inizia quando si clicca sul triangolino “play” e ci vengono presentati i quizzini da risolvere… Se vi siete persi e vi interessa solo la soluzione, potete guardare per esempio questo video, oppure leggete qui; se invece siete più interessati alla logica dietro le macchine di Turing, continuate pure a leggere.

Prima di tutto una notizia che farà saltare molti sulla sedia: la macchina di Turing non è un computer. Questo per varie ragioni: innanzitutto perché quando venne definita i computer non esistevano ancora, ed è stato un caso che l’architettura definitiva dei calcolatori fosse definita a partire da essa; e soprattutto perché vi voglio vedere, a trovare un computer con disponibilità di memoria infinita. Turing aveva creato la sua macchina per scopi assolutamente teorici, vale a dire cercare un modo in cui formalizzare lo studio del problema della terminazione: è sempre possibile sempre possibile, dato un insieme di istruzioni formali (un algoritmo, diremmo oggi) e un dato input finito, stabilire se l’elaborazione delle istruzioni arriverà a un termine oppure si continuerà a lavorare all’infinito? La risposta è no, e la macchina di Turing è per l’appunto un modello (non un computer!) che permette di simulare un qualunque tipo di algoritmo.

La definizione di macchina di Turing è una cosa molto sfuggente, per l’ottima ragione che ci sono vari tipi di macchina tutti equivalenti tra di loro; quello che conta è che ci sia un nastro illimitato diviso in caselle, una testina che possa leggere, scrivere e cancellare il contenuto di una casella oltre che spostarsi a sinistra e a destra, un insieme finito di simboli che possono essere scritti sulle caselle (diciamo 0,1, e lo spazio ” “) e un insieme finito di stati, vale a dire di istruzioni che dicono cosa la testina farà quando si trova in una casella, a seconda di cosa ci sia scritto sulla casella stessa. Uno stato è lo stato finale, che termina la computazione. Tutto qua. La memoria? La puoi avere nel nastro (tanto è infinito, spazio per salvare cose ce n’è…); i salti condizionati corrispondono a stati diversi sullo stessa casella, e così via.

Gli amici di Google hanno però un po’ barato: tra gli stati che vedete disegnati nelle due righe sotto il nastro potete notare quelli standard (spostarsi a sinistra e a destra), la scrittura di 0 e 1, gli “if” (quelli col quadratino), ma anche un GOTO che farà mettere le mani nei capelli ai puristi ma è comunque esprimibile in termini di macchina di Turing. Che aggiungere? Beh, nonostante il nastro infinito la macchina di Turing è davvero minimale, ed è quello che la fa apprezzare a un matematico, e forse un po’ meno a un informatico. Se siete riusciti a risolvere senza aiuto sia i primi sei problemi che i successivi sei a cui potete accedere cliccando in alto a sinistra sul doodle statico dopo aver finito il primo round, avete sicuramente una mente analitica!