MISTER BRAIN COMPLEIX 90 ANYS

Es compleixen 90 anys de la genial idea de 'Mr.Brain' que va fundar la informàtica moderna- El matemàtic anglès Alan Turing va demostrar que hi ha problemes (en matemàtiques i lògica) que no es poden resoldre mitjançant un procés algorítmic i va concebre la màquina de Turing, la versió abstracta d'un programa informàtic

El 28 de maig de 1936 la prestigiosa revista britànica Proceedings of the London Mathematical Society va rebre un manuscrit titulat “On computable numbers with an application to Entscheidungsproblem”. L'autor era un matemàtic de 23 anys, graduat per la Universitat de Cambridge un parell d'anys abans, anomenat Alan Mathison Turing. Tot i que el jove Turing ja havia donat mostres del seu talent matemàtic (els seus companys del col·legi ja en deien “Mr. Brain”), pocs podien imaginar que aquesta feina (que es va publicar el 12 de novembre d'aquell mateix any) establiria els fonaments de la informàtica moderna.

Turing hi va introduir de manera precisa el concepte de computació per demostrar un dels límits fonamentals de les matemàtiques: que hi ha problemes (en matemàtiques i lògica) que no es poden resoldre mitjançant un procés algorítmic. En primer lloc, va definir els “números computables” com aquells els decimals dels quals es poden obtenir mitjançant un procediment ben definit i finit, el que avui anomenem un algorisme. Com a exemple, va demostrar que constants com pi ye són computables, però que hi ha nombres reals que no ho són. Això va portar a una pregunta més profunda: què vol dir exactament “computar”? Com formalitzar la mateixa noció de càlcul?

Per respondre-la, va introduir el model del que avui dia es coneix com a màquina de Turing, la versió abstracta d'un programa informàtic. Una màquina de Turing es pot entendre com una “impressora” de dades (zeros i uns) i estats sobre una cinta infinita. La màquina se situa en certa posició de la cinta i, a partir de les instruccions de funcionament, realitza una sèrie d'accions. En primer lloc, llegeix el símbol de la posició de la cinta on és i, segons aquesta informació i el seu estat de partida, modifica o no el símbol, canvia el seu estat a un de nou i es mou un pas cap a l'esquerra o la dreta. A continuació, repeteix el mateix procés, a la casella següent. Així, la màquina continua calculant fins a trobar una ordre que la porti a l'estat de parada, en què la màquina s'atura i el càlcul conclou. Si mai no assoleix aquest estat, l'algorisme entra en bucle i continua indefinidament.

Turing va entendre la computació com qualsevol procés que pot ser executat (o simulat) mitjançant una màquina de Turing. Al mateix article, va analitzar la possibilitat que hi hagués una màquina que pogués realitzar “tots els càlculs possibles”, o en altres paraules, una màquina que pogués simular el comportament de qualsevol altra màquina de Turing. El científic va provar l'existència d'aquesta màquina, que avui coneixem com a màquina de Turing universal (realment se'n poden construir moltes, unes més simples i eficients que altres), la qual és considerada com l'avantpassada conceptual de l'ordinador i del programari. És a dir, tots els ordinadors programables que fem servir diàriament, des del mòbil fins al portàtil, es fonamenten en aquestes idees teòriques.

Els èxits anteriors ja haurien estat suficients perquè el treball de Turing del 1936 passés a la posteritat i, tanmateix, encara falta la qüestió central de l'article: l'aplicació d'aquests conceptes a l'Entscheidungsproblem (el problema de la decisió). Es tracta d'una pregunta formulada pel cèlebre matemàtic David Hilbert, que plantejava l'existència d'un algorisme universal que fos capaç de determinar, en temps finit, si qualsevol enunciat lògic o matemàtic donat és veritable o fals. Fent ús de la seva màquina, Turing va demostrar (influint pels famosos teoremes d'incompletitud de Godel) que no podia existir un algorisme d'aquest tipus, destruint així el somni de Hilbert.

Turing va mostrar que no hi pot haver un algorisme capaç de resoldre un problema específic: el problema de la parada. Aquest consisteix a determinar, per a qualsevol algorisme i qualsevol estat inicial, si la seva execució acabarà produint un resultat o si, per contra, continuarà indefinidament, en un bucle infinit. Turing va demostrar que no hi ha cap màquina de Turing capaç de prendre aquesta decisió en tots els casos. Per això, avui diem que el problema de la parada és indicidible. Amb els anys, molts altres problemes, en contextos molt dispars (des de la mecànica newtoniana fins a la mecànica quàntica, passant per l'òptica geomètrica o la dinàmica dels fluids), s'han demostrat indecidibles, però el punt de partida sempre és el famós problema de la parada resolt per Turing el 1936.

Aquell treball —només un dins una carrera plena de contribucions fonamentals— fa que el deute de la societat contemporània amb el llegat matemàtic d'Alan Turing sigui indiscutible. Tot i això, la transcendència de la seva obra contrasta amb el trist i injust final del matemàtic. Dos anys després de ser condemnat i sotmès a castració química per ser homosexual (el que era considerat un crim a Gran Bretanya fins al 1967), va morir per ingesta de cianur, als 41 anys. 

.

Daniel Peralta Salas a eldiario.es

,