La màquina de Turing

dissabte, 23/06/2012

Alan_Turing_Estatua.jpg

Estatua de Alan M. Turing als Whitworth Gardens, a Manchester (de Wikipèdia)

Avui, 23 de juny, fa cent anys que va néixer Alan Turing.

Alan Mathison Turing va néixer a Wilmslow, Anglaterra. Turing era un matemàtic. S’el considera el primer científic de la computació, el precursor de la informàtica moderna i un dels seus pares. Turing va completar i va donar sentit al treball que havia començat un segle abans Charles Babbage amb la seva màquina analítica, junt amb Lady Ada Augusta, comtessa de Lovelace i filla de Lord Byron (Ada Byron és considerada la primera programadora informàtica de la història, perquè va escriure programes per a la màquina analítica). Turing Babbage i Lady Ada son alguns dels pares i mares dels nostres portàtils, dels nostres telèfons inteligents i de molts altres aparells que usem cada dia. Però avui és el dia de Alan Turing, com haureu vist que ens recorda Google.

Turing va ajudar el seu pais durant la segona Guerra Mundial. Va desxifrar els codis secrets dels nazis, i en concret els de la màquina Enigma. Un cop acabada la guerra, va dissenyar alguns dels primers ordinadors electrònics, al Laboratori Nacional de Física del Regne Unit i a la Universitat de Manchester.

Els darrers anys de la vida de Alan Turing, però, van ser terribles. Als quaranta anys, el 1952, va ser acusat d’homosexualitat, jutjat i condemnat en base a les lleis homofòbiques vigents en aquells moments a Anglaterra. Va haver d’escollir entre la presó o la castració quimica, i finalment va preferir la castració. No en va poder superar els efectes físics i psíquics. Alan Turing es va suïcidar dos anys després, el 1954. La intolerància havia acabat amb el fundador de la informàtica moderna, amb el pare de la intel·ligència artificial, amb la persona que havia tant havia ajudat el seu país durant la segona guerra mundial.

Amb la seva màquina de Turing, va formalitzar els conceptes d’algorisme i de calculabilitat i va contribuir al disseny dels actuals ordinadors basats en algorismes emmagatzemats a la seva memòria interna. La màquina de Turing és molt simple, treballa amb una cinta que conté les dades i només veu la dada que té davant d’una finestreta. En cada moment, pot canviar la dada que està veient, o moure la cinta una posició. Aquí en teniu un exemple.

 

Turing va demostrar que la seva màquina podia resoldre qualsevol problema algorísmic dels que resolen els actuals ordinadors, per complicat que fos. La seva màquina pot resoldre tots els problemes que tenen solució. Per això la va anomenar “màquina universal”.

Algunes vegades, no obstant, els ordinadors no poden resoldre resoldre un determinat problema i entren en bucle, repetint i repetint càlculs sense acabar mai. Una altra de les coses que va demostrar Alan Turing és la no decidibilitat del problema de parada. Donat un problema qualsevol, no podem saber si una màquina de Turing (i per tant, un dels nostres ordinadors actuals) el podrà resoldre o bé entrarà en bucle infinit.

En Ramón López de Mántaras comenta l’extraordinària importància que té, en ciència, demostrar impossibilitats. Hi estic totalment d’acord. Conèixer els límits de les matemàtiques i de la computació ens permet saber, en paraules del matemàtic Gregory Chaitin, en quines ocasions és millor que no intentem allò que serà impossible…

Quina és la longitud de la costa de Menorca?

dijous, 21/06/2012

Menorca2.jpg Sembla una pregunta senzilla. Segur que si ens fan una pregunta com aquesta, anirem a internet a cercar la resposta. Diuen que hi podem trobar tota (o quasi tota) la informació, no?.

Doncs en aquest cas, si ho feu, no quedareu massa satisfets. A alguns llocs llegim que Menorca té 200 Km. de costa, a d’altres ens parlen de 216 Km. o de 220 Km. de costa, i alguns ens parlen fins i tot de 286 o de 299 Km.

Què passa? Qui té raó? Quina és la resposta correcta?

La resposta és sorprenent, perquè és negativa: no podem parlar de la longitud de la costa de Menorca (ni de longitud de quasi cap costa). La pregunta està mal formulada. Si dues persones diferents mesuren de manera independent la longitud de la costa de Menorca, obtindran resultats diferents. No podem parlar de la longitud de la costa de Menorca perquè, en general, les costes són fractals. I la mesura, en els objectes fractals, no és tan senzilla com estem acostumats. Benoît Mandelbrot va elaborar la teoria dels fractals entre els anys 1967 i 1977, tot basant-se en conceptes ja elaborats per Fèlix Hausdorff abans de la segona guerra mundial. L’any 1967 va publicar a la revista Science el seu article “Quant mesura la costa de Gran Bretanya?”, on ja plantejava el que ningú abans havia observat: cada llibre de geografia i cada enciclopèdia en donava un valor diferent.

Una de les característiques dels fractals és que la seva mesura no és fixa, si no que depèn de la unitat de mesura. Si ens demanen que mesurem la longitud d’un tros de costa i disposem d’un mapa, podem agafar un regle, anar-lo movent per la costa damunt del mapa i anar sumant longituds, mil·límetre a mil·límetre (podem fer-ho també caminant per la costa de veritat, però sempre serà més incòmode). Suposem que el mapa té una escala de 1:250000. Amb molta paciència, trobarem la llargada en mil·límetres en el nostre mapa i, amb una proporció o regla de tres, tindrem una estimació de la longitud real de la costa (sabem que cada 4 mil·límetres del mapa corresponen a un kilòmetre real). El problema és que la mesura que hem obtingut depèn de l’escala del mapa. Si encara ens queda paciència i repetim el procés amb un mapa més detallat, per exemple d’escala 1:50000, trobarem una longitud en kilòmetres que serà diferent. El mapa té més detalls, i ara haurem estat mesurant entrants i sortints de la costa que abans no vèiem. Com més detallat és el mapa, més gran és la longitud que trobem. Si recorrem tota la costa de Menorca i comptem els nostres passos, trobarem un resultat bastant més petit que el que obtindria un hipotètic esquirol de les faules de Esopo que fes el mateix. I si ho pogués fer una formiga, el resultat encara seria més gran perquè passaria per entrants i sortints que cap de nosaltres pot recórrer.

Els fractals són recargolats, tenen formes complexes. I aquest recargolament es manté encara que ens acostem i els mirem de molt aprop. És per això que la seva mesura depèn de la unitat de mesura. Si l’experiment de mesurar una costa el fem amb un tram de carretera, veurem que obtenim el mateix resultat independentment del mapa que utilitzem. Les carreteres no són fractals, com tampoc ho són les cases o els ponts de les obres públiques. Els fractals teòrics, els geomètrics, ens mostren la mateixa estructura complexe i laberíntica encara que ens hi acostem molt. Els entrants i sortints que veiem en un penya-segat són similars als que podem fotografiar en un trosset de pocs centímetres de la seva roca. Les parts d’un fractal són similars al tot. Per això diem que els fractals són estructures geomètriques autosimilars. Alguns arbres, com els avets, tenen una aparença fractal. Per això no és fàcil saber si ens estan venent un avet de Nadal o només una branca d’avet…

No deixa de ser interessant que, a la nostra llista, qui dona un dels valors més elevats de la longitud de la costa de Menorca, és una associació relacionada amb la nàutica. Des de la mar, la costa s’ens apareix amb tota la seva complexitat fractal, mentre que quan caminem per terra ferma tendim a fer dreceres, tallant i fent més curt el nostre recorregut.

Quan els científics formulen teories per donar resposta a algunes de les seves preguntes, poden equivocar-se. La teoria de la dinàmica d’Aristòtil va ser capgirada per Newton, la mecànica de Newton va ser refinada per la teoria de la relativitat general d’Einstein, i això probablement no s’ha acabat. Però, molt de tant en tant, els científics demostren que alguna cosa NO es pot fer. Cada cop que ens demostren que no ho podem fer o que no hi podem arribar, hem d’acceptar que les conclusions són correctes. Els fractals ens descobreixen unes estructures geomètriques que han conviscut sempre amb nosaltres, però que no vam descobrir i comprendre fins l’any 1967. Però els fractals també són un NO. Un no a la pretensió de que tot és fàcilment mesurable i etiquetable. Un no a la vanitat i a la pretesa omnipotència humana. Un no que no és massa llunyà del principi d’incertesa de Heisengerg (del que en parlaré un altre dia) o dels teoremes de Turing i de Goedel.

El que ens van dir Hausdorff i Mandelbrot és que podem entendre els fractals en base a estudiar la funció que relaciona la mesura amb la unitat de mesura. En unitats logarítmiques, la gràfica d’aquesta funció és una recta. I el pendent d’aquesta recta ens permet calcular la dimensió fractal de l’objecte que estem observant, dimensió que mesura la complexitat de la seva forma i el seu grau de recargolament.

Estem envoltats de fractals. En Benoît Mandelbrot ens hi va acostar quan l’any 1977 va escriure el llibre “La geometria fractal de la Natura”. De fet, som el que som i el nostre cervell pot treballar com treballa, gràcies a un mecanisme molt sofisticat d’oxigenació de la sang que funciona gràcies a l’estructura fractal dels nostres alvèols pulmonars. La costa de Menorca és fractal, amb formes complexes i gens rectes. Els nostres pulmons són fractals, complexes i recargolats perquè així maximitzen la superfície de contacte entre l’aire i els vasos sanguinis. En Darwin parlava de la supervivència dels més dotats. L’estructura fractal dels nostres pulmons ha possibilitat la “supervivència dels més oxigenats”.
Menorca1.jpg

Què volem? EuroVegas o més educació i recerca?

dijous, 14/06/2012

Havia pensat començar el blog amb una entrada de ciència que parlés dels fractals, però les recents notícies m’han fet canviar. No puc entendre com és que els nostres polítics dediquen temps i part dels nostres diners a negociar per aconseguir atreure el complex de EuroVegas, i com és que ofereixen facilitats i un tracte especial de favor.

Per què es destinen ajuts i esforços a incentivar el negoci del joc (i d’altres temes relacionats) enlloc d’incentivar i promocionar la recerca i l’educació?

Quin país volem tenir, d’aquí a uns anys?  Un pais com el que descriu en Roderic Guigó a la seva carta?  O bé un país que valori, incentivi i promogui la creació de coneixement, la creativitat i la producció?  Un país amb espais naturals protegits, o un país-casino?

Hem de continuar cercant el diner fàcil, invertint a curt termini i afavorint l’especulació, o bé hem d’invertir en educació, ciència i innovació tecnològica?  Ens volem reconvertir tot apostant per la creativitat, o ens volem vendre als interessos d’uns quants estrangers?  Què volem ser, quan siguem grans?  Què volen que siguem, els nostres polítics?

Em sento avergonyit de l’espectacle, en un moment en el que els nostres dirigents estan desmuntant l’estructura de recerca en ciència i tecnologia que tants anys ha costat construir, i quan les empreses no tenen accés al crèdit, tot plegat enmig d’un clar desinterès polític per l’activitat productiva. I em sento proper al pintor Antonio López, quan deia, ara fa un any, que “la cosa se va a poner seria. Habría que escuchar a los hombres de ciencia más que a los banqueros. Asi debe ser por el bien de todos”

Per si us interessa, aqui teniu més informació i podeu veure com us podeu adherir a la plataforma per aturar EuroVegas.