Turing, Von Neumann e l'informatica moderna

Introduzione

In passato abbiamo parlato dell'Intelligenza Artificiale sotto vari aspetti: come funzionano le reti neurali, gli algoritmi genetici e l'ant colony optimization ed alcuni modelli per l'analisi semantica dei testi, facendoci un'idea di come i computer si siano evoluti durante gli ultimi anni.

Eppure c'è un aspetto che abbiamo sottovalutato in questo breve percorso nell'intelligenza artificiale. Un aspetto senza il quale tutti gli articoli precedenti cadono come un castello di carte.

Cos'è un computer? Com'è nato? Come fa a funzionare?

Effettivamente abbiamo dato per scontato che il computer possa decidere quando attivare un neurone oppure no, quando e come decidere se la parola "Gatto" e "Animale" siano in relazione tra di loro... ma come fa ad eseguire questi calcoli e questi confronti?

Affrontiamo questo discorso partendo dagli albori dell'era computazionale.

Un po' di storia

Era il lontano 1936 quando un giovane ricercatore di matematica all'Università di Cambridge pubblicò l'articolo "On computable Numbers, with an application to the Entscheidungsproblem", un articolo nel quale veniva descritta in termini rigorosi, per la prima volta nella storia, la teoria dietro tutti i calcolatori moderni. Il suo nome era Alan Turing.

_{Un prototipo della Macchina di Turing - CC0 Image, click for source}

La teoria dietro quell'articolo fu applicata dallo stesso Turing qualche anno dopo, nel 1942. Erano gli anni della Seconda Guerra Mondiale, ed il giovane Turing (all'epoca appena trentenne) era già a capo di un team di matematici al soldo del governo britannico. Il loro scopo era quello di "Decrittare" i messaggi nazisti che utilizzavano un complicatissimo codice chiamato "Enigma".

Turing utilizzò le sovvenzioni del governo per costruire fisicamente la sua Macchina di Turing: nonostante le spese ingenti ed il tempo impiegato, nacque Colossus, una macchina capace di decifrare velocemente le comunicazioni naziste e che fu (molto probabilmente) la chiave di volta per la vittoria degli Alleati durante la grande guerra.

Il nome Colossus non era un'esagerazione: la prima macchina programmabile costruita dall'umanità utilizzava, al posto dei relè, delle valvole termoioniche (ben 1500) ed occupava un'intera stanza. Funzionava ad una velocità di lettura pari a 5000 caratteri al secondo, per un clock della CPU stimato a circa 5,8 MHz... uno sproposito per l'epoca.

Ma cosa rendeva questa nuova macchina così innovativa?

La macchina di Turing

La macchina di Turing (d'ora in poi abbreviata come MdT) è il primo calcolatore programmabile teorizzato dall'uomo.
Informalmente, è costituita da un nastro diviso in celle (possiamo immaginarlo di carta comune) di lunghezza infinita. Su questo nastro si muove una testina di lettura/scrittura. Tale testina può eseguire i seguenti compiti:

• Leggere un carattere scritto sul nastro in una particolare cella.
• Scrivere un carattere sul nastro in una particolare cella.
• Muoversi a destra o a sinistra sul nastro.

Sul nastro è possibile leggere o scrivere simboli provenienti da una alfabeto ben determinato e finito. Quando la MdT deve leggere un carattere, quando deve scriverlo o dove deve muoversi è deciso da un insieme di istruzioni finite che basano le proprie valutazioni sullo stato attuale della macchina e sul carattere letto.

_{Funzionamento di una MdT - CC0 Image, click for source}

Esistono varie versioni della macchina di Turing, diverse nella forma ma identiche nella capacità computazionale. Quella più famosa in ambito accademico è la MdT a un nastro e istruzioni a cinque campi. Cercando di essere un po' più formali, questa MdT è caratterizzata dalla seguente forma:

Dove:

S: l'insieme (finito) degli stati che la MdT può assumere
s0: Lo stato iniziale della macchina.
F: l'insieme degli stati finali della MdT
ß: Il carattere "Blank"
δ: l'insieme (finito) delle istruzioni che caratterizza la MdT

A loro volta le istruzioni sono composte dalla seguente quintupla:

Dove:

s: lo stato attuale della macchina
a: il carattere letto dalla MdT nella cella corrente
t: lo stato nella quale la macchina "salterà" dati gli input di cui sopra
b: il carattere che la MdT andrà a scrivere nella cella corrente
m: è il movimento che farà la testina: sinistra (-1), destra (+1) o immobile (0).

Finiti i formalismi proviamo a fare un esempio pratico tanto per entrare nell'ottica: la mia MdT ha due stati (s0 e s1). Lo stato iniziale della macchina è s0 e quello finale è s1.
Il set di istruzioni è molto semplice: se sono allo stato zero, e il carattere letto sul nastro è la lettera "A", allora scrivi nella cella "X" e passa allo stato s1. Se il carattere è "B", allora non scrivere nulla, resta nello stato s0 e muovi la testina verso destra.

Formalmente:

δ(s0, A) = {s1, X, 0}
δ(s0, B) = {s0, blank, +1}

In questa maniera, dando in pasto alla macchina una stringa composta di A e B, segnerà con una X l'occorrenza della prima A.
Ovvero:

input: "BBBBABBA"
output: "BBBBXBBA"

Questo perché ad ogni "B" la macchina sposta la testina verso destra e cicla sullo stato s0; alla prima "A" sovrascrive la cella con una "X" e passa allo stato finale s1, ponendo fine alla computazione.
E' ovviamente un esempio molto semplice ma serve a far capire il funzionamento.

All'inizio ci siamo domandati cosa rende questa macchina così innovativa: beh, questo funzionamento così basilare permette l'elaborazione di qualunque calcolo, dimostrazione, algoritmo mai inventato dalla mente umana dall'inizio della storia ad oggi.

Sì, esatto: quando scrivete il vostro post su Steemit e lo inserite nella blockchain, quando accendete una smart TV, quando giocate alla Playstation, dietro c'è una macchina di Turing che sta placidamente eseguendo le sue elaborazioni.

Edvac e l'architettura Von Neumann

Ogni elaboratore presente sulla faccia della terra può essere ricondotto ad una macchina di Turing: la cosiddetta Tesi di Church-Turing. Tale principio è così potente nell'ambito dell'informatica moderna che le teorie e le tesi riguardanti la computabilità e la complessità di calcolo si basano sulle performance di un'ipotetica macchina di Turing (Turing-equivalente).

Quindi la MdT costituisce il non plus ultra degli elaboratori moderni. Logicamente, una MdT costruita con un nastro di carta e valvole termoioniche non avrà mai le stesse performance di un computer moderno, ma è affascinante apprendere che, con la necessaria dose di pazienza, avrebbero potuto ottenere gli stessi risultati del desktop con il quale navighiamo su internet.

In realtà Turing era un matematico teorico, poco incline alla realizzazione "fisica" delle sue teorie. Fu costretto a mantenere il segreto militare riguardante Colossus (le informazioni sull'operazione di decodifica britannico furono rese pubbliche solo nel 1974, quando Turing ed i suoi colleghi erano morti da tempo) e le sue proposte tecnologiche furono scartate per i costi troppo elevati.

_{L'ENIAC occupava una superficie di circa 45mq di pura potenza di calcolo - CC0 Image, click for source}

Forse per questo il vero fondatore dell'informatica moderna è in realtà John Von Neumann, matematico, fisico e primo vero informatico della storia. Nel 1946 un gruppo di scienziati creò il progetto ENIAC (Electronic Numerical Integrator and Computer), un elaboratore enorme e pesante diverse tonnellate creato per il calcolo dei percorsi missilistici d'artiglieria. Si trattava di una macchina senza precedenti, ma con un grande problema: la "riprogrammazione" poteva richiedere settimane di modifica manuale ai 1200 calcolatori che ne facevano parte, rendendo impraticabile un utilizzo "general purpose", nonostante fosse concepito proprio a questo scopo.

Nel 1949 John Von Neumann in collaborazione con lo stesso team di ENIAC costruì EDVAC (Electronic Discrete Variable Automatic Calculator), uno tra i primi calcolatori basati sulla architettura Von Neumann.

Essenzialmente, per la prima volta la memoria degli elaboratori è stata condivisa sia per immagazzinare i dati, sia per memorizzare i programmi stessi che la macchina avrebbe dovuto eseguire. Divideva inoltre i componenti dell'elaboratore in una CPU (divisa in un controller ed una ALU per le operazioni aritmetiche), una periferica di input ed una di output, collegate da un BUS che faceva da "raccordo" tra i vari componenti.

Vi ricorda qualcosa?
I moderni computer si basano tutti esattamente su questo tipo di architettura, nonostante siano passati più di 60 anni.

L'EDVAC fu il precursore dei nostri personal computer, il bisnonno dell'informatica moderna.

Complessità computazionale

A conclusione di questo articolo, vorrei sfiorare un argomento molto ostico (che potremmo affrontare "ad alto livello" in seguito), ovvero quello della complessità computazionale.

_{La "Chomsky Hierarchy", gerarchia delle classi di complessità - CC0 Image, click for source}

Gli algoritmi che possono essere eseguiti da una macchina sono classificati in diversi gradi di "complessità": partendo dal più basso (tipo 3, linguaggi regolari) per arrivare al più alto (tipo 0, insiemi ricorsivamente enumerabili). Le macchine di Turing possono elaborare linguaggi di tipo 0, ma esistono problemi "non computabili" che riescono a far bloccare persino una macchina di Turing.

Uno di questi problemi è quello di creare un algoritmo che riesca a decidere se una macchina di Turing possa giungere ad uno stato finale oppure no. Quindi, quando diciamo che una MdT riesce a calcolare tutto il computabile, rendiamoci conto che questo è solo un insieme (anche abbastanza piccolo) di tutte le cose che riusciamo a fare noi esseri umani e che le macchine non sono in grado di elaborare.

Almeno per ora..!

---

Fonti e Approfondimenti:

• On Computable Numbers, with an Application to the Entscheidungsproblem (A. M. Turing, 1937)
  http://onlinelibrary.wiley.com/doi/10.1112/plms/s2-42.1.230/full

• Computational complexity of probabilistic Turing machines (J Gill, 1977)
  http://epubs.siam.org/doi/abs/10.1137/0206049

• First Draft of a Report on the Edvac (J. Von Neumann, 1945)
  https://www.wiley.com/legacy/wileychi/wang_archi/supp/appendix_a.pdf

• Solvable and unsolvable problems (A. M. Turing, 1954)
  http://www.ens.fr/IMG/file/internationale/2009/Sciences/Sujets_commentaire_SIS09_en.pdf

NOTA: tutte le foto presenti sono liberamente utilizzabili con licenza Creative Commons