Los límites de la computabilidad (III): el número U

Ya comentamos cómo Turing define el concepto de algoritmo mediante las famosas máquinas que llevan su nombre. Así, habría Máquinas de Turing (MT) para encontrar el máximo común divisor entre dos números, resolver raíces cuadradas,ecuaciones de segundo grado… ¡para cualquier acción que pueda realizarse en un número finito de pasos! ¿Podría resolver alguno de los grandes enigmas de las matemáticas propuestos por Hilbert, tal como la peliaguda conjetura de Goldbach?

El genio de Turing se puso en acción: cualquier MT puede codificarse numéricamente. Simplemente se trata de establecer una función entre las instrucciones  de funcionamiento (lo que Turing llamaba la configuración-m) y números. Entonces cada MT tendrá un determinado número de identificación que la diferenciaría de las demás. A partir de aquí puede construirse una Máquina Universal de Turing, es decir, una máquina que pueda hacer lo que todas las demás MT hacen. Si cada MT tiene un código de identificación, podemos hacer una máquina tal que reciba como input tal código e, inmediatamente, devuelva lo que esa MT en concreto devuelve. Si, por ejemplo, le introducimos el código de identificación de la MT que genera la cadena de los números naturales, nuestra nueva máquina devolverá esa misma cadena de números. Esto es una Máquina Universal de Turing (MU), la cual, a su vez, tiene un número de identificación:

7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613

6323593656444434583822268832787676265561446928141177150178425517075540856576897533463569424

7848859704693472573998858228382779529468346052106116983594593879188554632644092552550582055

5989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234

1505698026273468642992183817215733348282307345371342147505974034518437235959309064002432107

7342178851492760079759763441512307958639635449226915947965461471134570014504816733756217257

3446452273105448298078496512698878896456976090663420447798902191443793283001949357096392170

3904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305

47104436869587640517812801194375308138706399427728231564252892375145654438990527807932411448

26142357286193118332610656122755531810207511085337633806031082361675045635852164214865423471

8742643754442879006248582709124042207653875426445413345174856629157429990950262300973373813

7724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006

70086896759034473417412787425581201549366393899690581773859165405535670409281332221631410978

7108145997866959970450968184190629944365601514549048809220844800348224920773040304318842989

93931355266882349662101947161910701461968523192847482034495897709553561107027581748733327296

6789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624

02937487668839751404451665707750060513883991668814072545544665222050724262392379211525318162

51253630509317286314220040645713052758023076651833519956891397481375049264296050100136519801

86945639498

Este es el número U según nos lo ofrece Roger Penrose en La nueva mente del emperador . Tiene 1.653 dígitos y, a priori, prometía ser la leche: en él, de algún modo, se encuentra la solución a todos los problemas matemáticos en tanto que todos los problemas matemáticos tengan solución en una serie de pasos finitos. Y, a pesar de lo que ahora veremos, lo fue: el ordenador desde el que estás leyendo esto es una muy refinada MU (No deja de ser fascinante que lo que en otras épocas fueron descubrimientos que sólo invitaban a soñar, son ahora realidades ordinarias).

Turing utiliza la MU para afrontar el gran problema de la decibilidad de las proposiciones de la matemática (el problema matemático de todos los problemas, el Entscheidungsproblem ): dado una proposición matemática cualquiera, ¿existe un método que nos digera si esa proposición es demostrable dentro del propio sistema? O dicho de otro modo: ¿existe un método que nos digera si la conjetura de Goldbach es demostrable? Turing fabula con la idea de que fuéramos introduciendo en la MU todas las cadenas numéricas posibles (ya que cada una de ellas representaría una MT concreta, aunque, lógicamente la inmensa mayoría darían máquinas absurdas que no funcionan o cuyo funcionamiento es circular). ¿Sería posible diseñar una nueva máquina que, dada una cadena numérica cualquiera, pudiera decidir si la MT que la genera no es circular, es decir, que es una MT perfectamente funcional? Turing llama a esta máquina D (MD). Si esta máquina fuera posible, el problema de la decibilidad (también llamado en este caso «problema de la parada») se resolvería: la MD sería ese método para decidir, dada una proposición matemática cualquiera, si es demostrable dentro del propio sistema. ¡Las matemáticas serían completas y Hilbert sonreiría de felicidad! Todos los teoremas de las matemáticas estarían allí, como en un mundo platónico, esperando tranquilamente a que una nueva generación de matemáticos los resuelva…  ¡Todos los problemas matemáticos estarían dentro de U!

Pero nuestro gozo en un pozo: no es posible construir MD. Turing da dos pruebas: la primera se basa en la ingeniosa diagonalización de Cantor. Podemos ir agrupando en una tabla con filas y columnas toda la serie de cadenas numéricas que devuelve nuestra MU «cargada» con todas las MT concretas posibles que han sido seleccionadas como válidas por MD. Por ejemplo, tendríamos la secuencia de la MT que genera una serie infinita de unos, la que genera toda la serie de números naturales, etc. como mostramos en la tabla de aquí abajo. Podemos entonces dibujar una diagonal seleccionando el número que hay en la primera casilla de la primera fila, en la segunda casilla de la segunda, en la tercera de la tercera, etc. (en la tabla la marcamos en negrita).

1	1	1	1	1	1	1	1	etc
0	1	0	1	0	1	0	1	etc
1	2	3	4	5	6	7	8	etc
1	3	4	7	9	11	13	15	etc
2	4	6	8	10	12	14	16	etc
3	6	12	24	48	96	192	348	etc
2	3	5	7	11	13	17	19	etc
0	1	8	27	64	125	216	343	etc
1	4	9	16	25	36	49	64	etc

 

Podemos después agrupar los números de nuestra diagonal y hacer una nueva fila en la que, a cada número, le sumamos la unidad:

2

2

4

8

11

97

18

344

Etc+1

 

Realizar esta acción es un algoritmo, ya que seleccionar estas casillas y sumarles la unidad es un proceso que hemos hecho en un número finito de pasos (además corto, por lo que la MT necesaria para hacerla es trivial). Entonces, esta secuencia debería ser generada por nuestra MU «cargada» con todas las MT elegidas como correctas por MD, pero… ¡es imposible que la MU nos de esta secuencia! ¿Por qué? Porque al sumarle uno a una casilla de cada fila, todas las cadenas generadas diferirán en alguna de sus casillas, en una unidad con respecto a esta cadena. Es decir, nuestra MU podrá generar todas las cadenas correctas verificadas por MD, menos, como mínimo ésta… ¡Hay al menos, una cadena que no es decidible desde MU! ¡Se le ha escapado un preso a nuestro robótico vigilante de la corrección! Hilbert saca un pañuelo y se pone a llorar. La MD podría no reconocer la MT que resolviera la conjetura de Goldbach.

La segunda prueba (que a Turing le gusta más que la primera) se basa en la idea de que pudiéramos construir una máquina híbrida: una MU y una MD en la misma máquina (DU). Esta máquina se encontraría como input con una cadena cualquiera que la parte MD verificaría como correcta o no. Si fuera correcta, la parte MU replicaría el funcionamiento de la MT codificada y devolvería la cadena que la MT concreta devuelve. Bien, parece que no hay problema. Pero, ¿qué pasaría si le pasamos como input el mismo número de identificación de la propia DU? MD la verificaría como correcta y la pasaría a MU para que replicara su función, a saber, de nuevo verificar mediante DU si es circular para pasarla luego a MU, la cual activaría otra vez DU, que pasaría la cadena otra vez a MU… así sucesivamente hasta el infinito… ¡Al introducir su código en si misma DU se vuelve circular! ¿Pero no habíamos dicho que DU no era circular al pasar por la verificación de MD? ¿Qué pasa aquí? Una paradoja no muy diferente a la de Epiménides y los cretenses. Definitivamente, hay procesos algorítmicos indecidibles, como ya había mostrado Alonzo Church unos años antes que Turing. Pero no nos pongamos a llorar tan rápido, hay que tener en cuenta que Turing sólo había demostrado la indecibilidad de las matemáticas, no su incoherencia . Como el matemático André Weil dijo:

Dios existe, ya que las matemáticas son consistentes; el demonio también, ya que no podemos demostrarlo.

Si te ha gustado lee también sus precuelas: II y I.