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/fullComputational complexity of probabilistic Turing machines (J Gill, 1977)
http://epubs.siam.org/doi/abs/10.1137/0206049First Draft of a Report on the Edvac (J. Von Neumann, 1945)
https://www.wiley.com/legacy/wileychi/wang_archi/supp/appendix_a.pdfSolvable 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
Being A SteemStem Member
Ho circa un milione di domande. Quindi grazie per il post. Ne faccio 2 perché se no mi mandi nel casino 😂😂😂. Sono 2 curiosità. Per il resto aspetto gli altri post
Forse sto anticipando altri tuoi post futuri. Ma ho visto che Microsoft sta progettando un software per i CQ con l'obbiettivo di diventare uno standard anche in quel settore... la capacità computazionale diventerebbe incredibile
Ok mi fermo qui 😂👍
Ciao @etn0, grazie a te per aver commentato :) Il post che ho scritto parla più di informatica teorica che di vere tecnologie dietro i computer, per questo non ho portato avanti esempi più concreti (cosa che potrei approfondire in un prossimo post sull'architettura degli elaboratori). I computer quantistici sono affascinanti, ma siamo ancora agli albori di questo nuovo campo, che comunque costituirà il nostro futuro dati i limiti tecnologici di miniaturizzazione dei transistor.
Per quanto riguarda il tuo primo quesito: sì, anche i computer quantistici possono essere ridotti ad una macchina di Turing :) sarà infinitamente più veloce ma non potrà risolvere problemi che una MdT non può risolvere.
Almeno fino a quando non si riuscirà a simulare perfettamente l'intelletto umano... ma stiamo sforando dalla scienza alla fantascienza ;)
ho letto il tuo articolo ma nelle parti tecniche mi sono un po' perso.
Guardando però la foto dell'ENIAC mi è tornata alla mente la frase del presidente dell'IBM T. Watson Jr. che disse nel 1943:
"Penso che ci sia richiesta mondiale per circa cinque computer" :D
E qui entra in gioco la splendida Legge di Moore, che forse meriterebbe un post a parte. Sarebbe divertente tornare indietro nel tempo con un vecchio portatile e dimostrare agli scienziati che quello scatolotto è 3000 volte più veloce del loro ENIAC :D
Esatto un bel post sulla legge di Moore
Post scritto, lo trovi sul mio blog ;)
Complimenti per il post, messo nei link della cartella "da leggere con calma perché merita"
Un saluto, nicola
Grazie, penso sia sempre interessante conoscere il passato degli oggetti di uso comune... soprattutto considerato che i computer oggigiorno gestiscono gran parte delle nostre vite ;)
Bella introduzione.👏 Nozione non richiesta: Studiando queste cose mi è capitato di conoscere l'origine della parola computer, un tempo chi faceva i conti a mano era uno 'human computer' un calcolatore umano, poi abbiamo deciso di tenere solo il secondo termine per i nostri amici non umani! 😜
Questa mi mancava O_o me la rivendo con i miei amici informatici! Grazie ;)