Shakespeare archiviato nel Dna 

di Martina Saporiti | Pubblicato il 24 Gennaio 2013 - http://www.galileonet.it/

Un tempo c’erano gli archivi con i loro scaffali pieni zeppi di faldoni contenenti documenti di ogni genere e sorta. Oggi c’è il Dna, una molecola così versatile da poter essere utilizzata persino per archiviare i miliardi di miliardi di dati digitali prodotti oggi nel mondo. Ricercatori dello European Bioinformatics Institute (Embl-Ebi), in Gran Bretagna, e ingegneri dell’Agilent Technologies , una compagnia di elettronica con base in California, hanno infatti lavorato assieme per mettere a punto una nuova tecnologia che permetterebbe di immagazzinare 100 milioni di ore di filmato in alta qualità in un piccolissimo frammento di Dna. Per capire come ci sono riusciti basta leggere lo studio pubblicato su Nature . 

Avete mai sentito parlare di zettabyte? È una delle unità di misura dell’informazione, una cifra stratosferica che corrisponde a mille miliardi di miliardi. Ebbene, oggi nel mondo esistono circa tre zettabyte di dati digitali, un numero destinato a crescere considerando l’enorme quantità di informazioni che vengono messe in circolo quotidianamente in ogni angolo della Terra. Ma come conservare questa gigantesca mole di dati? Gli hard disk sono costosi e ingombranti, mentre i nastri magnetici si rovinano in una decina d’anni, troppo poco per poter garantire un’archiviazione a lungo termine. Perché allora non usare il Dna? “E’ piccolo, compatto e non consuma energia per immagazzinare dati”, spiega Nick Goldman , il ricercatore della Embl-Ebi a capo dello studio. In più, si conserva per migliaia di anni. 

L’idea di utilizzare la regina delle molecole biologiche per archiviare dati non è nuova, e qualche successo in questa direzione era già stato raggiunto. Ma le vecchie tecniche impiegate per convertire le informazioni digitali in sequenze di nucleotidi (i mattoni del dna) erano suscettibili di errori e permettevano di immagazzinare solo piccole quantità di dati. La nuova tecnologia messa a punto dai ricercatori bypassa questi problemi. Ecco come funziona: l’informazione digitale espressa in bit viene prima convertita in trit, cioè l’unità di base di un sistema numerico che utilizza tre cifre (generalmente 0, 1 e 2) al posto di due (0 e 1); a ogni trit viene poi fatto corrispondere un nucleotide. In questo modo, è stato possibile assemblare lunghi filamenti di dna in cui, grazie alle molteplici combinazioni numeriche possibili con un codice a tre cifre, era quasi impossibile avere vicino due nucleotidi dello stesso tipo (la maggior fonte di errore in questo tipo di tecnologie). Il filamento è stato quindi spezzato in piccole porzioni (più facilmente manipolabili) a cui sono state legate sequenze indice che ne indicavano la posizione all’interno del filamento originale. 

Utilizzando questa tecnica, il gruppo di Goldman ha trasformato in dna varie tipologie di dati digitali per un toltale di oltre 700 kilobyte: un mp3 tratto dal celebre discorso di Martin Luther King I have a dream; una foto in jpg della Embl-Ebi; il pdf di un articolo di Watson e Crick (i due scienziati che scoprirono la struttura a doppia elica del dna); un file di testo dei sonetti di Shakespeare. Questa conversione ha generato più di 153mila frammenti di Dna piccoli come un granello di polvere. Dal sequenziamento di queste porzioni di materiale genetico, poi, è stato possibile risalire ai file originali con un’accuratezza del 100%. “Abbiamo creato un archivio capace di immagazzinare dati per 10mila anni, o forse più”, afferma Goldman. Ora i ricercatori sono al lavoro per perfezionare il processo con la speranza di poter presto disporre di molecole di Dna sintetico dalle stesse funzionalità di un hard disk.

La Stampa Tuttoscienze - Il computer che simula il cervello

Calcola, calcola dove finiremo? - 26 ottobre 2012, http://www.avvenire.it

L'uomo ha da sempre cercato di costruire macchine che gli fossero di ausilio nelle sue attività. Così come ha anche cercato di utilizzare la forza e le attitudini degli animali per i lavori più pesanti o difficili. Ha arato la terra sfruttando la forza di buoi per tirare l’aratro, ha inviato messaggi per mezzo di piccioni viaggiatori, ha utilizzato e utilizza cani per ricercare persone sepolte sotto le valanghe. Per lo svolgimento di attività più elaborate, come "far di conto" o prendere delle decisioni, l’uomo non ha potuto trovare nessun ausilio già pronto fuori di sé, nel mondo degli animali o nella realtà fisica. E allora ha sviluppato strumenti che lo potessero aiutare in queste attività.

Già molti secoli prima di Cristo l’uomo ha utilizzato l’abaco per sommare numeri. Poi, alla metà del 1600, il giovane Blaise Pascal ha costruito una macchina, la Pascalina, per sommare e sottrarre numeri. In tempi più recenti vari logici, matematici, fisici e ingegneri hanno lavorato, sia sul versante teorico e che su quello tecnologico, allo sviluppo di macchine (come computer, <+corsivo>decision support system<+tondo>, robot di vario genere) che potessero aiutare l’uomo nelle attività di calcolare, ragionare, prendere decisioni e, perfino, ideare teorie scientifiche.

Queste attività si possono classificare ponendole su tre livelli distinti. Il livello del «calcolare»: su questo livello c’è, per esempio, il fare le somme, le sottrazioni e le altre operazioni aritmetiche imparate a scuola. Il livello del «ragionare»: su questo livello c’è, per esempio, il dedurre proprietà nell’ambito di teorie formali e lo scegliere strategie vincenti nello svolgimento di giochi. Sono su questo livello la prova del teorema che la somma degli angoli interni di un triangolo è di 180 gradi e la scelta di strategie durante una partita di scacchi. Il livello del «pensare scientifico»: su questo livello c’è, per esempio, l’ideare nuove teorie matematiche o fisiche (come fece Einstein quando fissò gli assiomi della Teoria della Relatività) e l’indagare sui rapporti tra varie teorie e sui limiti dell’applicabilità delle teorie.

C’è anche un quarto livello dell’attività pensante. Su questo livello c’è il riflettere dell’uomo che si riconosce pensante e autocosciente, aderisce a una visione del mondo o a una verità di fede. Ma per ora non diremo nulla sulle attività a questo livello.

Per il primo livello, quello del «calcolare», esiste in genere un algoritmo (il software) che può essere eseguito da una macchina (l’hardware). Tale algoritmo termina sempre e dà il risultato desiderato, a patto che durante il calcolo non si verifichi alcun guasto. Questo è il livello a cui appartiene la macchina Pascalina: in essa la correttezza dei risultati delle operazioni viene assicurata dall’integrità degli ingranaggi. In effetti c’è una limitazione intrinseca al processo meccanico di calcolo dovuta alla «dimensione dei dati». Infatti, essendoci infiniti numeri, si ha che, scelto comunque un numero intero, esiste sempre un altro numero la cui rappresentazione necessita di una sequenza di cifre più lunga del numero scelto.

In altri termini, non è vero che le macchine di calcolo, anche le più potenti, sanno fare «tutte» le somme, e questo deriva dal semplice fatto che nelle macchine non si possono rappresentare «tutti» i numeri, essendo esse degli oggetti finiti, con un numero finito di stati. Questa limitazione si supera assumendo, e anche noi ora lo assumiamo, che esista una memoria infinita su cui si possa memorizzare un qualsiasi numero.

Al secondo livello, quello del «ragionare», l’algoritmo di deduzione (o di scelta delle strategie, nel caso dei giochi) può terminare o non terminare e questo dipende dalle caratteristiche della teoria formale (o del gioco) in esame.

In particolare, come messo in evidenza da Alan Turing con l’ideazione della Macchina Universale e la dimostrazione del Teorema della Fermata, ci sono teorie (e giochi) che sono «semidecidibili» e altre che non lo sono. La semidecidibilità assicura che se la proprietà da provare vale, allora l’algoritmo di deduzione termina, altrimenti, se la proprietà non vale, l’algoritmo può non terminare. Ciò significa che se passato un certo lasso di tempo la macchina non ha prodotto ancora alcun risultato, purtroppo non possiamo dedurre nulla circa la deducibilità o meno della proprietà da provare.

Le teorie semidecidibili individuano il limite della meccanizzabilità perché per ogni teoria semidecidibile non esiste nessuna Macchina di Turing (né qualsiasi altra macchina) che, data una proprietà, possa dedurre per la teoria in esame la validità o meno di quella proprietà.

Al terzo livello, quello del «pensare scientifico», la deduzione avviene in una teoria formale che, in generale, non è neppure semidecidibile. Ciò significa, per esempio, che la ideazione di una nuova teoria (matematica o fisica) a partire da vecchie teorie non è, in generale, meccanizzabile. Per tale ideazione si possono, sì, adottare tecniche basate sull’Intelligenza Artificiale, però poi, in generale, non si potrà determinare meccanicamente se la teoria ideata sia consistente o meno. Cioè, non sarà possibile determinare algoritmicamente se una falsità sia o no deducibile a partire dai suoi assiomi.

Ovviamente, se una falsità fosse deducibile, allora la teoria non sarebbe di alcun interesse. Non è meccanizzabile neppure la verifica del fatto che una data teoria sia o no adeguata a descrivere un insieme di fatti concettuali e/o di osservazioni sperimentali, se tale teoria è abbastanza complessa.

Si noti, infine, che quanto abbiamo affermato sulla decidibilità e sulla meccanizzabilità dell’attività pensante dell’uomo ha la validità di un teorema della matematica e non dipende, pertanto, dallo sviluppo tecnologico delle macchine di calcolo. Non dipende neppure dalle possibili assunzioni filosofiche circa la scienza e le macchine.

Alberto Pettorossi

Quegli algoritmi che decidono per noi

L’irriducibilità dell’uomo alla macchina - I limiti insuperabili della tecnica e dell’algoritmo, contro le fantasie trans umanistiche – di Giorgio Masiero, fisico e docente universitario, 17 luglio, 2012, http://www.uccronline.it/

Ogni 4 anni, al Congresso Internazionale dei Matematici, è assegnata la medaglia Fields ai giovani ricercatori qualificatisi per le scoperte più rilevanti. Il premio è soprattutto onorifico, a meno che la scoperta non rientri tra i “7 problemi del Millennio” del Clay Institute: allora ai 15.000 dollari canadesi della medaglia Fields si aggiunge il premio Clay di 1.000.000 di dollari USA. L’ultimo congresso si è svolto nel 2010 a Hyderabad ed ha assegnato solo medaglie Fields; nel precedente di Madrid invece, al russo Grigori Perelman era toccato anche il premio Clay per la dimostrazione della congettura di Poincaré, una questione che resisteva da un secolo agli assalti della ragione. La descrizione del problema e degli altri 6 ancora irrisolti si può trovare nel sito del Clay. A sorpresa Perelman non si mosse dalla sua San Pietroburgo per ritirare i premi, limitandosi a dire agli esterrefatti cronisti: “Ho risolto il problema, tanto mi basta”. Mostrava così la gioia perfetta di chi, col solo uso della mente, in anni di riflessioni dedicate a coniugare l’intuizione all’inferenza in vista d’un obiettivo, era riuscito a scalare difficoltà logiche inimmaginabili.

I moderni computer, implementati dei software adeguati, possono per la loro velocità di calcolo risolvere problemi complessi, che richiederebbero tempi astronomici al calcolo umano, ma hanno gravi limiti. Quali sono? Da che cosa traiamo indicazioni sui loro ambiti? L’unico giudice dei limiti dell’algoritmo e del processore è la ragione umana! Forse un giorno saranno dimostrati tutti i problemi del Clay; o forse no: per alcuni la dimostrazione potrebbe essere preclusa ad ogni tecnica. I due teoremi d’incompletezza di Gödel (1931) impattano proprio la capacità dell’algoritmo di dimostrare proposizioni matematiche e di costruire teorie scientifiche coerenti. Stando al primo teorema esistono in aritmetica, e quindi in tutta la matematica (di cui l’aritmetica costituisce il nucleo) e in tutte le scienze naturali (di cui la matematica è il linguaggio), enunciati veri che non si possono dimostrare per via algoritmica. Non è una questione di completezza degli assiomi, né di capacità di memoria, né di velocità elaborativa: semplicemente non esiste la procedura! Un esempio di questione matematica indecidibile fu trovato una cinquantina d’anni fa, con uno spettacolare teorema che procurò all’americano Paul Cohen la medaglia Fields nel 1966: è l’ipotesi del continuo di Cantor. Una delle prime domande su cui conto di avere risposta nell’altro mondo la riguarda: esistono infiniti intermedi tra i numeri naturali ed i reali?

La presenza di limiti all’algoritmo, tuttavia, ci è anche utile in questo mondo. Tornando alla lista Clay, leggiamo tra i 6 problemi irrisolti la sigla P vs NP. Essa sta ad indicare una questione cruciale in molti problemi d’ottimizzazione industriale, per es. nel process scheduling. Un problema è classificato tra quelli P (polinomiali) se è risolvibile in tempi ragionevoli da un calcolatore, magari dotato di velocità del processore e di capacità della RAM superiori a quelle odierne; rientra invece tra quelli NP (non polinomiali) se può essere risolto soltanto in modo bruto attraverso l’immissione ed il controllo di tutte le combinazioni e se richiede allo scopo un dispendio di risorse superiori all’età e all’energia dell’Universo. Non pensare, caro lettore, che i problemi NP riguardino chissà quali situazioni astratte: prova, se ci riesci, a calcolare il tragitto più corto per visitare in un unico giro 10 amici, abitanti in 10 località sparse della tua regione; o quello per la distribuzione giornaliera di un centinaio di pacchi di uno spedizioniere locale. Insomma un problema NP, anche se risolubile in teoria (da una “macchina di Turing”), non lo è in pratica: è oltre il limite fisico della tecnica…, a meno che con qualche scorciatoia matematica non sia traducibile in un problema di tipo P. La sfida posta dal Clay consiste proprio in ciò: i problemi NP sono sempre riducibili a problemi P?

Ricordate i numeri primi? Sono quelli divisibili solo per 1 e per se stessi: 2, 3, 5, 7, 11,… Anche se sembra ripetersi indefinitamente la stranezza di trovare ogni tanto due primi attaccati, detti “gemelli” (…, 107, 109, …, 599, 601, …, 821, 823, …), avanzando si diradano in media sempre più, ma sono infiniti (teorema di Euclide, III sec. a.C.): ciò significa che ne esistono di grandi quanto si vuole, anche da mille o un milione di cifre. La scomposizione poi è l’operazione che fattorizza un numero non primo (“composto”) nei suoi fattori primi, per es. 60 = 2 × 2 × 3 × 5. Se il numero composto non è troppo grande, la scomposizione è facile: se è pari si divide per 2, poi si prova per 3, poi per 5, ecc. Quando il numero è molto grande si ricorre ai calcolatori. Oggi, con sofisticati algoritmi che utilizzano recenti scoperte matematiche sulla distribuzione dei numeri primi (alcune, bellissime, hanno procurato nel 2006 una medaglia Fields all’australiano Terence Tao), un normale pc ci può dire in tempi ragionevoli se un dato numero di qualche centinaio di cifre è primo o no, e ci può anche trovare un nuovo primo di tali dimensioni. Non esiste tuttavia nessun software per nessun computer (sia pure il super-computer di Standard & Poor, o il K computer di Kobe da 8 milioni di miliardi di istruzioni al secondo, né quello 1.000 volte più veloce di cui si disporrà tra 10 anni) che sappia scomporre in tempi fisici il prodotto di due numeri primi di alcune centinaia di cifre.

Questa almeno è la situazione allo stato delle nostre conoscenze matematiche, dove la scomposizione resiste come problema NP. Sui tempi ultramondani della fattorizzazione di grossi numeri si fonda gran parte della crittografia per la sicurezza di internet (scambio dati riservati, transazioni bancarie, privacy, reti di trasporto, infrastrutture energetiche, comandi militari, ecc.). Così, quasi per una legge del contrappasso, quella finitudine dell’algoritmo che in apparenza ne denota negativamente i tratti applicativi, si trasforma nella capacità di dare sicurezza alle transazioni mondiali. Una tecnica onnipotente implicherebbe software capaci di fattorizzare tutti i numeri e di scardinare ogni crittografia; quindi sicurezza nulla ed impossibilità di transazioni riservate via internet; quindi, in definitiva, l’annullamento di ogni utilità del web, ridotto a veicolo di spam. Invece una tecnologia performante limitata consente una sicurezza che seppur finita resta performante: una sicurezza accettabile, pur se labile come ogni cosa di questo mondo, minacciata sempre da un hacker che trovi, forse domani, forse tra qualche anno, la via per districare il problema NP della scomposizione e tradurlo in uno di tipo P.

Morale. Giorni fa, prima di ritirare l’auto dal parcheggio a pagamento, sono passato alla cassa automatica e, trovatomi senza spiccioli, ho usato la mia carta di credito con chip e pin “ultrasicura, di ultima generazione” (secondo lo slogan della banca emittente): inseritala nello slot dedicato, ho digitato il pin sulla tastiera ed atteso la restituzione della carta. Tardando questa ad uscire, ho premuto il tasto “Annulla operazione” e l’ho estratta manualmente. Apparso comunque il messaggio di “Transazione eseguita”, me ne sono uscito tranquillamente dal parcheggio. A tarda serata però, un sms mi avvertiva che un acquisto di 1.659 € era appena stato eseguito in un negozio di confine con la mia card. Me l’avevano clonata! Realizzai allora che a rallentarne l’uscita dallo slot era stato uno skimmer fraudolentemente applicatovi per clonare il badge… e che la zingarella aggirantesi intorno alla cassa, apparentemente impegnata a richiedere un obolo ai passanti, era lì allo scopo di controllare il campo e di carpire dal moto delle dita il pin ai malcapitati. Le carte di credito usano sì teoremi che le rendono, allo stato delle nostre conoscenze matematiche, inattaccabili dai calcolatori, ma c’è una peculiarità della ragione umana che coniuga le più moderne tecnologie con le più ataviche doti d’intuizione e destrezza: quest’arte può battere sempre ogni impossibilità di cui è prigioniera la macchina. “Datemi una definizione d’intelligenza ed io vi dimostrerò che i calcolatori possono essere intelligenti”, preconizzava troppo ottimisticamente il britannico Alan Turing, del quale abbiamo festeggiato il 23 giugno scorso il centenario della nascita. Ebbene, non è l’intuizione una componente tra le più importanti, se non la prima, dell’intelligenza umana? e l’algoritmo non è alternativo all’intuizione, nella definizione fondante della computer science che tu, Alan, ne hai dato nel tuo memorabile scritto del 1936? Ricordi, lettore, il Dustin Hoffman di Rain man? Il personaggio mostra meglio di ogni disquisizione che l’autismo, anche quando fa prodigi nel calcolo, non coincide con l’intelligenza. A questa distinzione si deve se nessun adepto dell’Intelligenza Artificiale sa (anche vagamente solo immaginare come) scrivere un programma che dimostri per es. la proprietà commutativa della moltiplicazione, senza ricorrere al quinto assioma di Peano.

ANNIVERSARI/ Interrogate il PC: vi risponderà come una macchina di Turing - Angelo Montanari, lunedì 11 giugno 2012, http://www.ilsussidiario.net

Se discipline quali la matematica e la fisica possono vantare nutrite schiere di padri nobili, per una disciplina relativamente giovane qual è l'informatica, la celebrazione del centenario della nascita di Alan Turing rappresenta una novità assoluta. Non deve, perciò, sorprendere che, in questo 2012, quello che è unanimemente riconosciuto come il padre dell'informatica sia il protagonista di molteplici iniziative distribuite fra i vari continenti.

La conferenza ufficiale si terrà a Manchester a fine giugno, ospitata dall'università presso la quale Turing lavorò dal 1948 al 1954, anno della sua morte, e vedrà la partecipazione di numerosi vincitori del premio Turing (il premio Nobel per l'informatica a lui intitolato); accanto ad essa, interventi sull'influenza dei risultati di Turing su settori dell'informatica sono stati inseriti nel programma di moltissime conferenze internazionali di area informatica di quest'anno.

La vita di Turing è già di per sé un'avventura: l'infanzia in una famiglia che viveva a cavallo tra India e Inghilterra, gli studi al King's College di Cambridge e i primi lavori in settori tradizionali della matematica, come la teoria delle funzioni quasi periodiche, i lavori fondamentali da cui prenderà forma la scienza informatica, il successivo dottorato a Princeton, con lo studio dei gradi di insolubilità dei problemi, il coinvolgimento nel gruppo impegnato nella decodifica dei codici segreti utilizzati dall'esercito tedesco per le comunicazioni militari durante la seconda guerra mondiale, gli anni del dopoguerra presso l'Università di Manchester, le anticipazioni di temi che diventeranno oggetto di importanti ricerche in intelligenza artificiale, l'omosessualità e il suicidio a 42 anni. In questo articolo ci soffermeremo su alcuni dei suoi contributi scientifici più importanti.

La ricerca di un sistema formale (logico) in grado di catturare tutte le inferenze deduttive comunemente usate nella pratica matematica può essere fatta risalire agli studi di Frege nella seconda metà dell'ottocento. Il nucleo della logica di Frege è nella sostanza quella che viene oggi chiamata la logica del prim'ordine. Una cinquantina di anni dopo, in un lavoro scritto col suo allievo Ackermann, Hilbert solleva due questioni fondamentali relative a tale logica. La prima riguarda la completezza della logica del prim'ordine, ossia la sua capacità di derivare, mediante l'applicazione delle regole di sistema, tutte le formule valide; la seconda la possibilità di sviluppare una procedura in grado di stabilire la validità o meno di una qualsiasi formula della logica.

Questa seconda questione è nota come Entscheidungsproblem (problema della decisione). Nella sua tesi di dottorato, Gödel provò la completezza e la correttezza della logica del prim'ordine (teorema di completezza di Gödel), fornendo una risposta positiva alla prima delle due questioni. In virtù di tale risultato, l'Entscheidungsproblem può essere riformulato come il problema dell'esistenza di un procedimento di calcolo effettivo (un algoritmo) in grado di stabilire se, dati un certo insieme di premesse e una conclusione, la seconda sia o meno derivabile dalle prime.

Turing iniziò ad occuparsi del problema poco dopo la pubblicazione dei sorprendenti teoremi di incompletezza di Gödel. In essi, Gödel aveva dimostrato che all'interno di ogni sistema formale abbastanza potente da contenere l’aritmetica esistono proposizioni che il sistema non riesce a decidere, non riesce, cioè, a fornire una dimostrazione né di esse né della loro negazione. Inoltre, fra le proposizioni che tale sistema non riesce a dimostrare c'è anche quella che esprime la non-contraddittorietà (coerenza) del sistema.

Tali risultati rendevano improbabile l'esistenza di un algoritmo per Entscheidungsproblem. Turing concentrò, pertanto, il suo sforzo sulla ricerca di una dimostrazione di tale impossibilità e nel tentativo di fornire un modello adeguato del processo di calcolo arrivò a concepire quelle che da allora vengono chiamate le macchine di Turing. Una macchine di Turing manipola un insieme di dati contenuti nelle celle di un nastro di lunghezza infinita (in ogni fase della computazione, solo il contenuto di una porzione finita di tale nastro è significativo) sulla base di un insieme finito di regole prefissato.

La tesi di Turing-Church afferma che per ogni funzione calcolabile mediante un processo algoritmico, esiste una macchina di Turing che calcola tale funzione. A conferma di tale tesi, comunemente accettata, è stata dimostrata l'equivalenza di tutti i modelli di calcolo alternativi proposti in letteratura alla macchina di Turing. Sulla base di tale tesi, il problema originario può essere ridotto all'esistenza di una macchina di Turing in grado di risolverlo. Dalla prova della non esistenza di una tale macchina, segue l'indecidibilità dell'Entscheidungsproblem.

Sulla base di un'opportuna codifica numerica delle macchine di Turing e dei loro dati di input (codifiche analoghe erano state già utilizzate da Cantor e Gödel), Turing mostrò come il problema di stabilire se, data una macchina di Turing M e un insieme di dati di input I per essa, l'esecuzione di M su I termina o meno sia insolubile, ossia non esista un algoritmo (una macchina di Turing) in grado di risolverlo. La prova sfrutta il metodo della diagonale usato da Cantor per dimostrare che i numeri reali (infiniti) sono "piu" dei numeri naturali (anch'essi infiniti). Dato che il problema dell'arresto della macchina di Turing può essere espresso in logica del prim'ordine, la non esistenza di un algoritmo per l'Entscheidungsproblem segue immediatamente (se un tale algoritmo esistesse, potrebbe essere usato per risolvere il problema dell'arresto della macchine di Turing, che Turing ha mostrato essere indecidibile). Nei decenni successivi, tale tecnica di riduzione è stata impiegata con successo per dimostrare l'indecibilità di un grande numero di problemi algoritmici di natura assai diversa.

Una conferma definitiva della potenza della nozione di macchina di Turing venne dall'idea rivoluzionaria di una macchina di Turing universale. La tesi di Turing-Church afferma l'esistenza di una macchina di Turing per ogni funzione calcolabile. La macchina di Turing universale è una particolare macchina di Turing che riceve in input una descrizione di una qualsiasi (altra) macchina di Turing M e di un input I per essa e restituisce in output il risultato dell'elaborazione di I da parte di M. Turing provò l'esistenza di una tale macchina in modo costruttivo, ossia fornendo l'insieme di regole che la governano. Una delle novità radicali dell'idea di macchina universale è la rimozione della tradizionale distinzione tra macchine e dati. Fra i suoi dati di input, la macchina di Turing universale ha la descrizione di una (altra) macchina di Turing. Se i calcolatori così come noi li conosciamo sono assai diversi dalla macchina di Turing (la loro architettura si basa su un modello di calcolo alternativo equivalente proposto da von Neumann), dal punto di vista concettuale non c'è alcuna differenza: il calcolatore è una macchina di Turing universale.

Nell'ultimo periodo della sua vita, Turing si occupò di questioni che di lì a pochi anni sarebbero diventate l'oggetto di interesse di uno dei settori più rappresentativi dell'informatica quale l'intelligenza artificiale. In particolare, si interrogò circa la possibilità per un calcolatore di sviluppare un'intelligenza di tipo umano.

In un articolo apparso sulla rivista Mind nel 1950, egli propose un test, o gioco dell’imitazione, oggi noto come test di Turing, basato sulla seguente assunzione: una macchina può essere definita intelligente se riesce a convincere una persona che il suo comportamento, dal punto di vista intellettuale, non è diverso da quello di un essere umano medio. Il test si svolge in tre stanze separate. Nella prima si trova l'esaminatore umano (A); nelle altre due vi sono rispettivamente un'altra persona e il computer che si sottopone al test. Dei due A conosce i nomi (B e C), ma ignora chi sia la persona e chi il computer. Sia B che C si relazionano separatamente con A attraverso un computer. Via computer A può porre domande a B e C e leggere le loro risposte. Compito di A è scoprire l'identità di B e C (chi è la persona, chi è la macchina?) entro un limite di tempo prefissato.

A può effettuare qualunque tipo di domanda. Il computer ovviamente cercherà di rispondere in modo tale da celare la propria identità. La macchina supera il test se A non riesce a identificarla nel tempo prefissato. Il test verrà ripetuto più volte, coinvolgendo anche esaminatori diversi, in modo

da ridurre i margini di soggettività. Anche se risulta del tutto evidente l'influenza del funzionalismo e del comportamentismo nella formulazione del test, esso presenta diversi elementi di interesse. Fra questi, vogliamo sottolineare lo stretto legame che esso stabilisce tra intelligenza e capacità linguistiche: esso si basa su una interpretazione operativa/comportamentale dell'intelligenza che si manifesta attraverso la comunicazione linguistica. Una confutazione indiretta della validità del test di Turing verrà fornita alcuni decenni dopo dal famoso argomento della stanza cinese di Searle, ma questa è già un'altra storia.

© Riproduzione riservata.

Tu parli il pc esegue

Adesso impariamo a guidare la tecnologia

Più creativi con il calcolo genetico di Roberto Manzocco, 03 giugno 2012, http://www.ilsole24ore.com/

Accentuare la componente creativa dell'ingegneria, ispirandosi alle leggi dell'evoluzione e al darwinismo. È questa la sfida affrontata negli ultimi anni da tale disciplina applicativa, anche grazie all'avvento di uno strumento concettuale molto innovativo: gli algoritmi genetici. Ma che cos'è un algoritmo genetico? Si tratta di un'euristica, cioè un metodo (in questo caso di tipo computazionale) che può essere utilizzato per simulare al computer progetti di ogni tipo, dalle automobili ai treni, dalle navi agli aerei, dalle scarpe da ginnastica alle lavatrici, dall'ottimizzazione dei consumi energetici alle tecnologie biotech. In particolare, gli algoritmi possono essere impiegati allo scopo di ottimizzare un dato progetto, valutando tutte le alternative e scegliendo la migliore (per esempio, si possono simulare tutti i design possibili di un'ala d'aereo, scegliendo quello migliore in termini di costi e di prestazioni).

Facciamo un passo indietro. Tutto inizia con John Henry Holland, dell'Università del Michigan che, nel 1975, pubblica un saggio fondamentale, «Adaptation in natural and artificial systems». L'idea proposta da Holland, e poi sviluppata da David Goldberg, dell'Università dell'Illinois tra i massimi esperti mondiali di questo tema, è quella di una procedura di calcolo (un algoritmo, appunto) per realizzare simulazioni di ogni genere e ispirata all'evoluzionismo darwiniano. Dato un determinato progetto che presenti uno o più nodi problematici, si possono generare migliaia di soluzioni potenziali (sotto forma di un insieme di stringhe in codice binario, ma sono possibili anche altri metodi). In sostanza è una rappresentazione genetica di tali soluzioni, che le tratta (in senso metaforico) come genomi individuali. E proprio la scorsa settimana Trieste ha ospitato – nel corso dell'edizione 2012 del «modeFrontier users' meeting» organizzato dalla società Esteco – David Goldberg, che è anche consulente del Governo americano per la riforma universitaria per il quale «il ruolo della comunicazione, della filosofia e della creatività è essenziale per la soluzione dei problemi, e in particolare di quelli ingegneristici». Per dirla con Carlo Poloni, presidente Esteco, si tratta di «una metafora di gestione che interpreta in termini di causa-effetto i problemi che possono sorgere in campi diversi». Fatto questo, si sceglie una «funzione di fitness» – un criterio di selezione, stabilito in base alle esigenze progettuali – e la giostra darwiniana può partire. Si sottopone quindi l'insieme delle soluzioni potenziali a tutta la trafila dell'evoluzione biologica: mutazioni casuali, selezione, riproduzione e incrocio degli "individui" (cioè le singole soluzioni) così generati. Tutto questo fino a quando non raggiungiamo una soluzione che ci soddisfi (come un'ala d'aereo che contenga la miglior combinazione di robustezza e basso costo).

Insomma, se l'intervento triestino di Goldberg – un "manifesto" per la riforma dell'insegnamento accademico delle discipline ingegneristiche, che incoraggi la creatività e magari introduca materie "soft", cioè di tipo umanistico, nel loro curriculum di studio – può sembrare scollegato dalle tematiche più squisitamente progettuali, esso in realtà rappresenta proprio lo spirito che anima l'uso degli algoritmi genetici in ambito ingegneristico.

I lavori di Holland prima, e di Goldberg poi, si inseriscono infatti in un ampio settore di ricerca noto come «creatività computazionale»; ossia il tentativo di conferire alle macchine capacità creative analoghe a quelle umane o, al contrario, di renderle in grado di potenziare la creatività umana senza essere esse stesse creative. Per fare un esempio concreto: modeFrontier, il software sviluppato da Poloni, funziona proprio così, cioè, a prescindere dall'ambito in cui stiamo lavorando (aerospaziale, energetico, automobilistico, e così via), esso rappresenta e seleziona tutte le soluzioni possibili fino a raggiungere la cosiddetta «frontiera di Pareto» (dal celebre economista italiano Vilfredo Pareto); ossia la miglior soluzione possibile, che non può subire ulteriori miglioramenti senza che si pregiudichi qualche altro aspetto. Secondo Poloni tale lavoro – eseguito in modo del tutto automatico – toglie «la parte noiosa del lavoro ingegneristico, lasciando spazio all'analisi e alla creatività del progettista».

Vediamo allora qualche applicazione pratica. Basandosi su modeFrontier, Kristian Amadori dell'Università svedese di Linköping ha sviluppato una metodologia per il design automatico e la fabbricazione di Mav (un particolare tipo di droni) che permette di modulare le varie caratteristiche di tali veicoli a seconda del tipo di missione a cui saranno destinati. David Miller dello Us Department of Energy ha invece messo a punto un modello teorico per l'ottimizzazione delle centrali elettriche a carbone che mira a ridurre il più possibile l'emissione di biossido di carbonio, mantenendone nel contempo l'efficienza.

Nell'ambito della sicurezza stradale, Na Li e Jian Xin Liu, della cinese Central South University, hanno sviluppato una simulazione che analizza in modo efficiente i dati medici e biomeccanici relativi ai danni alla testa e al collo in seguito a incidenti automobilistici, utile per finalità preventive. Per quanto riguarda lo sport, Mathew Dickson e Franz Fuss (della Rmit University di Melbourne) hanno analizzato il design di un celebre paio di scarpe da corsa, le Adidas Bounce, per valutare se l'efficienza della scarpa si modifica se il corridore accelera il passo. È infine curioso notare come, tra i settori che si avvalgono degli algoritmi genetici, si sia aggiunta di recente anche la ricerca biotech (un'area di ricerca che negli ultimi anni ha prodotto una quantità immane di dati, rendendo così necessaria la loro ottimizzazione). Per esempio, vista l'esistenza di più procedure di sequenziamento e assemblaggio del genoma, Francesca Nadalin dell'Università di Udine ha mostrato come sia possibile impiegare modeFrontier per selezionare la procedura più adatta alle esigenze dello sperimentatore. Insomma, partiti dal mondo della biologia e dell'evoluzione naturale, gli algoritmi genetici hanno "chiuso il cerchio", tornando sul loro luogo di origine.

Che cervello quel computer - La macchina super intelligente funzionerà come i nostri neuroni Intervista a Bandyopadhyay, lo scienziato che ha inventato le molecole artificiali che mimano il comportamento delle cellule cerebrali , L‘Unita (CRISTIANA PULCINELLI), 28 maggio 2012, http://www.swas.polito.it

I COMPUTER DI OGGI LAVORANO A VELOCITÀ IMPRESSIONANTI: ALCUNI DI ESSI SONO CAPACI DI ESEGUIRE 10MILA MILIARDI DI ISTRUZIONI IN UN SECONDO.

TUTTAVIA, POSSONO ESEGUIRLE SOLO IN SEQUENZA, OVVERO UNA ALLA VOLTA.

Le cellule del nostro cervello invece sono lente: «scaricano», cioè trasmettono impulsi elettrici, solo alcune centinaia di volte al secondo.

Ma sono una squadra: milioni di neuroni lavorano in parallelo simultaneamente e questo fa sì che tutti insieme siano enormemente più efficienti di qualsiasi computer superveloce.

Ma non è finita qui.

Le connessioni tra i neuroni si modificano, evolvono, rafforzandosi o indebolendosi a seconda dell'uso.

In altri termini, la rete che formano, ovvero il cervello, impara.

Infine, il cervello è in grado, almeno in parte, di autoripararsi: se un neurone muore, un altro prende il suo posto.

Allora, perché non prendere esempio da quella macchina biologica perfetta per progettare il computer del futuro? È questa la domanda che si è posto Anirban Bandyopadhyay, fisico indiano di 37 anni che ha al suo attivo una carriera scientifica di tutto rispetto, tanto che si vocifera già di una sua candidatura al Nobel.

Bandyopadhyay oggi lavora al National Institute for Materials Science in Giappone.

Da lì ha creato, insieme a un gruppo di colleghi statunitensi, un nanocervello, ovvero un minuscolo computer costituito di poche molecole che mima le caratteristiche del cervello umano.

Ogni molecola di questa macchina biologica interagisce contemporaneamente con le vicine facendole cambiare di stato e quindi funzionando come un interruttore di un computer che lavora in parallelo.

Inoltre, anche il nanocervello evolve e si autoripara.

Per testare la sua potenza, i ricercatori lo hanno usato per simulare due fenomeni naturali: come il calore si diffonde in un materiale e come un cancro cresce nell'organismo.

Ed è l'applicazione medica che ad Anirban Bandyopadhyay sta più a cuore da quando, nel 2010, ha perso suo padre per un ictus, come ha raccontato nel corso di un suo intervento al festival «Poiesis» di Fabriano.

Il vostro studio apre la strada allo sviluppo del computer molecolare che secondo alcuni sarebbe la nuova rivoluzione in informatica? «Noi crediamo di sì.

Solo che non è chiaro se si potrà chiamarlo computer perché i computer esistenti risolvono problemi in cui l'algoritmo è ben definito, ad esempio l'addizione tra due numeri.

Tuttavia, nel caso in cui non si possa definire bene il problema, questo nuovo apparecchio molecolare ci potrebbe accompagnare nel difficile compito di cercare e trovare le informazioni che ci sono necessarie tirandole fuori da una rete di informazioni astronomicamente grande e complessa.

Si tratta del tentativo di sfruttare le tecnologie biologiche e il modo in cui funzionano.

Finora noi sapevamo che i sistemi biologici erano molto superiori alla tecnologia inventata da noi, ma non sapevamo perché.

Ora capiamo i motivi di questa superiorità».

Qual è il vantaggio del vostro nano cervello rispetto ai normali computer?

 «I computer biologici sono più lenti dei normali computer, questo vale anche per il nano cervello.

Ma, in effetti, non siamo tanto interessati alla velocità del computer, quanto piuttosto alla sua capacità di imparare che lo metterebbe in grado di risolvere problemi mai incontrati prima.

D'altra parte, si è sempre sostenuto che solo il computer quantistico potrebbe generare una velocizzazione esponenziale dell'informatica classica.

Tuttavia, è possibile velocizzare i computer anche usando oscillatori e sincronia, proprietà che troviamo in natura, ad esempio in uno stormo di uccelli o in un branco di pesci.

L'uccello che migra è guidato da un orologio interiore, un oscillatore potremmo dire, che si sincronizza con quello di tutti gli altri uccelli.

Usando questo meccanismo, invece di scrivere fantastiliardi di algoritmi sotto forma di proposizioni "se allora", noi possiamo scrivere le istruzioni direttamente nell'hardware della macchina fissando particolari parametri di sincronia tra le molecole.

Possiamo pensare agli oscillatori come a diapason, ma in questo caso sono progettati in modo che invece di un unico canale di risonanza o di comunicazione ne hanno molti.

Questo favorisce l'elaborazione simultanea di molti livelli di informazione, o una logica di livello superiore.

È un automa cellulare dotato di intelligenza».

Cosa sarebbe in grado di fare un computer costruito su questi principi? «In teoria, potrebbe risolvere problemi che un computer classico non sarebbe in grado di affrontare neppure lavorando per tutti gli anni di vita dell'universo.

Inoltre, mentre le future generazioni di computer "exascale" (ovvero computer mille volte più potenti degli attuali, n.d.r.) avranno bisogno di un'energia pari a 800-1000 mega watt, il nostro automa ha bisogno di pochi watt perché usa una comunicazione non radiativa, ovvero che avviene senza emissione di energia.

Infine, l'hardware e i circuiti di questa macchina cambiano con il tempo, cosicché evolve».

Quali sono le applicazioni pratiche delle macchine molecolari che state studiando? «Queste macchine potrebbero funzionare come un cervello robotico e quindi essere utilizzate nelle operazioni da svolgere nello spazio.

Oppure per la chirurgia medica a distanza, anche se per fare questo dobbiamo prima raggiungere l'obiettivo di rendere la nostra macchina operativa in una cellula e non solo in laboratorio.

Inoltre potrebbe essere utile per il risparmio energetico trasformando ogni singola macchina che vediamo intorno a noi e che opera utilizzando enormi quantità di energia».

CHI È

Lo studioso della tecnologia «organica» Anirban Bandyopadhyay, 37 anni, ricercatore del Nims di Tsukuba (Giappone), ha inventato i «nanobrain», molecole artificiali che mimano il comportamento dei neuroni cerebrali e si occupa di organizzare una piattaforma per creare un computer super intelligente.

A «Poiesis» ha affrontato il tema delle decisioni, sottolineando come ogni scelta avviene selezionando tra un numero astronomico di alternative.

La fisica quantistica potrebbe essere la soluzione, poicé ci consente di trattare vasti insiemi di stati possibili ad enormi velocità, grazie a processi come la sovrapposizione e la correlazione.

IL FESTIVAL

Una edita miscela di pensieri e visioni, di parole e di passioni: musica e teatro, cinema e poesia, arte e scienza.

In concreto parliamo di incontri, dibattiti, concerti, proiezioni, mostre, letture e performance artistiche.

Questo è «Poiesis», il Festival di Fabriano ideato e diretto da Francesca Merloni, che quest'anno ha chiamato ospiti illustri e di respiro internazionale come l'archistar olandese Rem Koolhaas, il filosofo Giulio Giorello, il teologo Vito Mancuso, gli scienziati Massimo Piattelli Palmarini, Giuseppe Vitiello, Anirban Bandyopadhyay, lo scrittore Raffaele La Capria che hanno illustrato l'idea di Grande Opera (tema di questa edizione) dal punto di vista logico, architettonico, filosofico, fisico-quantistico, letterario.

Il lavoro, inteso come Grande Opera dell'uomo, è stato invece discusso, tra gli altri, da Guglielmo Epifani, il Ministro Corrado Clini e Giovanni Minoli.

Tra i numerosi altri testimoni, sono saliti sul palco del festival Pierfrancesco Favino, Elisa, Paolo Fresu, Petra Magoni, Marracash, Alessandro Bergonzoni, i fratelli Taviani e Carolyn Carlson, che ha proposto una performance tra danza e poesia; i poeti Stefano Massari, Antonio Riccardi, Gian Mario Villalta; i fotografi Gabriele Basilico, Monika Bulaj, Giorgio Barrera, Andrea Jemolo.

TECNOLOGIA IL COLOSSO DEL WEB PREPARA LA «RICERCA SEMANTICA» - Non solo link, ma vere risposte Google ragionerà come un uomo di Serafini Marta, 16 marzo 2012, http://archiviostorico.corriere.it

MILANO - Trovare tutto su Internet, prima e meglio. Con un sistema che si avvicina al linguaggio umano e che permette di dialogare con il computer per ottenere le informazioni desiderate. Dimenticate le parole chiave, il futuro dei motori di ricerca ha un nome: ricerca semantica. E questo nome ora può vantare l' imprimatur di Google. Non a caso infatti il search executive di Google Amil Singhal, intervistato dal Wall Street Journal , ha svelato che «big G» sta lavorando a un motore di nuova generazione, in grado di fornire risultati adeguati a «come le persone percepiscono il mondo». La rivoluzione annunciata acquista contorni più nitidi. «Se digitiamo su un motore di ricerca "lago Tahoe", vogliamo conoscere anche dettagli sul lago, l' altitudine, la temperatura media dell' acqua e la popolazione della regione», spiega Singhal. Pretendiamo di più dunque di un semplice link. E con la ricerca semantica potremmo essere accontentati perché il motore si evolve da semplice erogatore di informazioni aggregate dall' algoritmo a distributore di conoscenza, quasi fosse un cervello umano. Una missione impossibile? «Questo processo è iniziato nel 2010 con l' acquisizione da parte di Mountain View di un database che raccoglie tutte le informazioni fornite da Wikipedia», spiega Marco Varone, presidente e Cto di Expert System, azienda italiana da anni impegnata nel settore. Ma più che di una soluzione, si tratterebbe, sempre secondo Varone, di una scorciatoia: «A Google manca ancora - almeno stando a quanto sappiamo - la capacità di estrarre dati e informazioni da tutte le pagine web, non solo da Wikipedia». Ma non solo. «Da qui alla creazione di un software vero e proprio ce ne passa». Come a dire che se la rivoluzione sta per iniziare, la strada verso la ricerca semantica è tutt' altro che in discesa. Marta Serafini RIPRODUZIONE RISERVATA