La màquina de Turing

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…

3 comentaris

  • oca

    25/06/2012 12:16

    Com no, un altre exemple que el món el governaven (i el continuen governant) la gent que no toca.

Comenta

*

(*) Camps obligatoris

L'enviament de comentaris implica l'acceptació de les normes d'ús