Posts etiquetados ‘Georg Cantor’

Viendo este magnífico vídeo uno entiende el neoplatonismo de Bertrand Russell o de Roger Penrose ¿Quién se atrevería a decir que todas las reglas que dominan el funcionamiento de estos números son una construcción social o histórica? ¿Quién se atrevería a decir que dichas reglas podrían ser diferentes? No, esas reglas son las que son y no podrían ser de otra manera con total y absoluta independencia de que el hombre existiera o no. Y si existen con independencia del sujeto habría que determinar qué tipo de entidad tienen ¿Son materiales? Si así lo fueran podríamos ubicar, por ejemplo, el número siete, en un lugar determinado del espacio, ya que la ubicación espacial parece ser uno de los rasgos más característicos de lo material. Sin embargo, el número siete no parece estar en ningún lado concreto. Tiene, por así decirlo, en don de aparecer allá donde se lo necesita cada vez que alguien lo utiliza para hacer una operación aritmética. Entonces habría que postular algún tipo de existencia diferente a la puramente material para estos mathematas. Platón no era imbécil, desde luego.

Un dato que sale en el vídeo y que me ha dejado perplejo ha sido cuando dice que 1 es igual a 0,9 periódico ¿Cómo? No puede ser. Lo lógico sería pensar que 0,9 periódico está siempre a punto de llegar a 1 pero nunca lo consigue. Pues no, queridos amigos, y la demostración es, además, trivial. Declaremos una variable N que vale 0,9999999999… Ahora la multiplicamos por 10 de modo que 10N = 9,999999999… Ahora, sencillamente, restémosle N a 10N:

Nos da que 9N = 9. Despejamos La N y 9 entre 9 da 1, quod erat demostrandum. Increíble. Pero pensémoslo de otra manera. Sabemos que entre dos números cualquiera siempre podemos meter infinitos números racionales, por lo que, tal y como se afirmaba en la paradoja de Aquiles y la tortuga, hay infinitos números entre cualquier par de números que escojamos por muy “cerca” que pensemos que están. Por ejemplo, entre el 1,3 y el 1,4 podemos meter el 1,31, el 1,32, el 1,33… y luego seguir con el 1,311, el 1,312, el 1,313, etc. ad infinitum. Pero si hacemos lo mismo entre el 1 y el 0,9 periódico… ¿Qué número podemos meter en medio? ¡Ninguno! ¡Intentadlo! No cabe absolutamente nada entre ambos, precisamente porque son el mismo y único número.

Y por si nos hemos quedado con ganas de más, vamos a contar otra demostración que, en el momento en el que la conocí, me dejó absolutamente perplejo. Si comparamos el conjunto de los números naturales y el de los números enteros, el más sano sentido común nos dice que hay más números enteros que naturales…

¿Parece obvio, no? Pues no, porque puede establecerse, trivialmente, una relación biunívoca entre ambos conjuntos de números, es decir, podemos emparejar cada número natural con un número entero de forma que haya la misma cantidad de números. Para hacerlo podemos comenzar emparejando el 0 con el 1, y luego generamos los enteros positivos emparejándolos con los naturales pares y los enteros negativos con los naturales impares. Ya está, podemos seguir hasta el infinito por arriba y por abajo y… ¡siempre tendremos el mismo número de elementos a ambos lados!

Por si nos hemos quedado con ganas, el señor Georg Ferdinand Ludwig Philipp Cantor va a demostrar de una forma tan sencilla como genial que los números reales (todos los números que existen) no son numerables. Operando por reducción al absurdo, va a suponer lo contrario. Que una lista de elementos sea numerable quiere decir que podemos contarlos, es decir, que como pasaba con los números enteros, podemos emparejarlos con la lista de todos los números naturales. Vamos a intentar hacerlo. Si yo empiezo por el natural 1 y lo emparejo con el real 0,1… ¿con cuál emparejo el 2? Pues con el 0,11 por ejemplo ¿Y el 3? Con el 0,111… Pero, ya nos hemos atascado. Podemos seguir añadiendo unos y jamás llegaremos al 0,2… ¿Cómo lo hacemos? ¡Es muy difícil hacer una lista de números reales cuando podemos meter infinitos entre cada par de números! Cantor nos dice que no vayamos por ahí. Simplemente nos hace falta suponer que todos los números reales pueden ponerse en una tabla y emparejarse con los naturales, por ejemplo, así…

La primera columna representa todos los números naturales y las siguientes representarían todas las posibles combinaciones numéricas de números reales declaradas con la variable a, un índice para el número de fila y un subíndice para el número de columna. La tabla puede extenderse hasta el infinito hacia la derecha y hacia abajo, de modo que da igual lo largo que fuera el número o, incluso, que fuera infinito.

Entonces parecería que da igual cómo ordenemos los números o si tuvieran infinitos decimales. Cualquier número que imaginemos podría ponerse en esta lista y emparejarse con un natural, por lo que habríamos demostrado que los números reales son numerables… No tan deprisa que viene el ingenio de Cantor. Vamos a sumar la unidad a todo número cuyo número de fila y de columna coincidan, trazando así una infinita diagonal que atraviese toda nuestra tabla. El número resultante siempre diferirá en una unidad de cualquier número que esté en la tabla, de modo que existirá, al menos un número, que no hayamos emparejado con un número natural, es decir, que existirá algún número que no hemos contado. Conclusión, los números reales no son numerables ¡Ya está! ¡Así de simple! Pero, ¿a quién se le habría ocurrido hacer una demostración así?

Pero es que no solo existirá un número que no está en la lista. Sencillamente, en vez de sumar la unidad, sumemos dos a cada elemento de la diagonal… y luego 3, 4, 5 y así ad infinitum… ¡Hay infinitos números que no están en la lista y que, por tanto, no hemos contado!

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.