La vera Macchina di Turing

In molti, oserei dire pure troppi, sono convinti che il computerone narrato nel film the imitation game, col quale fu sconfitto il «cripto-marchingegno» Enigma, fosse la (famosa) Macchina di Turing. Ma va’ là…!!!

Chiamiamolo, come nel film, Christopher, per via dell’amico d’infanzia di Turing. O più realisticamente Victory o ancor meglio Bomba, come il computer polacco al quale era ispirato. Ma NON chiamiamola Macchina di Turing… per favore!

E non ti ci mettere pure tu, Zia Wiki!!! Nella voce inglese della zia, relativa al film - ancor di più dopo la traduzione in italiano, ma non per colpa di quest’ultima! - aleggia, anzi serpeggia, finanche lì un BEL po’ di confusione: per qualche millisecondo temevo di aver sbagliato pagina e stavo riattaccando.

Chiariamoci: che quella nel film fosse una macchina e che l’avesse creata Turing è fuor di dubbio, ci mancherebbe! Il problema è che a mio modestissimo avviso la dicitura (la maglia?) «Macchina di Turing» andrebbe ritirata e mai, mai, mai, avvicinata a qualcosa di diverso: anche quando c’è di mezzo lo stesso Alan (sempre sia lodato!).

Saranno pure sottigliezze, ma per me sono sacrosante. Fine sfogo!

Detto questo, LA Macchina di Turing, per brevità MdT, ideata dallo stesso negli anni trenta, tanto per cominciare non è fisicamente realizzabile - quindi non sarebbe mai e poi mai potuta apparire implementata e funzionante in un film storico - per un piccolo dettaglio: la sua memoria infinita. È proprio questo, assieme alla sua semplice logica di funzionamento deterministica, a renderla capace di calcolare… qualsiasi funzione calcolabile e pertanto, schiacciando un po’ l’acceleratore del ragionamento, si assume che la MdT possa essere riconosciuta come il computer più potente NON esistente, nel mondo reale, ma sulla carta sì e come!

Per intenderci, se vedete in giro (anche a casa di zia) immagini di prototipi pseudo-funzionanti della MdT - ne ho visto pure una, ossignùr, realizzata a colpi di nonpiùmattoncini Lego!!! - sappiate che è un fake. Ovvero al massimo una versione infinitamente sottodimensionata. Problema peraltro irrisolvibile.

Nel mentre­ ­che faccio pace con la zia, consentitemi questa breve autocitazione da MC n. 59 (gennaio 1987, fattoriale), presa dall’articolo Algoritmi e Macchine di Turing in Appunti di Informatica: «Giusto per chiarire subito una cosa, vogliamo aggiungere che anche un VIC-20 con memoria infinita sarebbe equipotente alla MdT: di questa se ne parla con tanta ammirazione proprio per la sua semplicità e per il fatto di essere stata ideata e studiata negli anni trenta»…

Nella sua infinita semplicità è composta essenzialmente da tre parti: un nastro magnetico, una testina R/W e una parte di controllo, come visibile nello schema a lato. Il nastro è la memoria di sistema, che come dicevamo ha lunghezza infinita (meglio sarebbe dire illimitata). Nello stato iniziale, per intenderci al momento del RUN, alcune celle sono già scritte (corrispondono ai dati di ingresso da elaborare), ma naturalmente possono essere ri-scritte strada facendo, così come se ne possono utilizzare altre - quante vogliamo! - per i dati intermedi e per scrivere, al termine, il risultato finale del calcolo.

Il secondo componente della MdT, la testina di lettura/scrittura, come dice il ragionamento stesso (cit.), legge e scrive le celle del nastro magnetico che, proprio come fosse un (antico) registratore, scorre nei due versi davanti a questa. La parte di controllo, che include il codice del programma da elaborare (sotto forma di tabella degli stati finiti) serve per elaborare quanto è inciso sul nastro dando ordini sia alla testina che al meccanismo di scorrimento del nastro. Robe del tipo: nello stato q1, se leggi A scrivi B, passa allo stato q2 e sposta a destra o a sinistra il nastro di una posizione, ecc.

Nonostante l’incredibile semplicità di tutto l’ambaradàn, a tutt'oggi non sono riusciti ancora a trovare un formalismo in grado di calcolare più cose della MdT: equipotenti sì, più potenti no.

Dove per potenza, va da sé, non si intende la banale velocità di calcolo…

AdP