La máquina de Turing

cabecera

A principios de 1936, un joven Alan Turing terminó un artículo que sentó en gran parte las bases de lo que sería un ordenador actual. Para resolver el Entscheidungsproblem, uno de los problemas que traían de cabeza a los matemáticos de la época, Turing ideó un sorprendente experimento mental. Había nacido la máquina de Turing.

Alan empezó por definir lo que era un número computable: números reales cuya expresión como decimal puede calcularse por medios finitos.

A partir de esta definición, Turing ideó una máquina imaginaria que pudiera tratar con números computables. Las características son las siguientes:

  • Alberga un número finito de condiciones, a las que llamó configuraciones-m (q_i).
  • La máquina tiene una cinta dividida en celdas, cada una de los cuales puede tener escrito un símbolo. La cinta pasa a través de la máquina y tiene una longitud infinita.
  • En cada momento de funcionamiento de la máquina, una sola celda de la cinta estará dentro de ella.

A la celda de la cinta que puede leer la máquina, le llamaremos la celda activa. El símbolo dentro de esta celda es el único dato de entrada que conoce la máquina en un momento dado, pero a través de cambios de configuraciones, se puede tener conocimiento de los símbolos leídos anteriormente.

La configuración-m activa en la máquina, junto al símbolo de la celda activa, forman la configuración de la máquina en un momento dado.

Turing definió también las posibles acciones que podía realizar la máquina:

  • Escribir un símbolo en la celda activa (P).
  • Borrar símbolo de la celda activa (E).
  • Mover la cinta una posición hacia la izquierda (L).
  • Mover la cinta una posición hacia la derecha (R).
  • Finalmente, en cada paso puede producirse un cambio en la configuración.
Esquema de una máquina escrito por Turing. En concreto para la máquina que escribe la secuencia 001011011101111...

Esquema de una máquina escrito por Turing. En concreto para la máquina que escribe la secuencia 001011011101111…

Turing dio dos ejemplos sencillos de máquinas. Una escribía la secuencia 01010101… y otra escribía la secuencia 001011011101111… A continuación vamos a ver un ejemplo de ésta última. En concreto esta máquina escribe la secuencia con un espacio entre cada dígito, algo que Turing encontró muy cómodo a la hora de realizar estas secuencias.

La primera tabla que podéis ver en el ejemplo es la tabla de configuraciones, que consta de:

  • Configuración: identificador de la configuración
  • Símbolo: símbolo que junto al código de configuración activa las acciones
  • Acciones: acciones a realizar cuando la máquina se encuentra en ese modo de configuración y con uno de los símbolos correspondientes en la celda activa.
  • Nueva configuración: configuración a la que pasa la máquina cuando acaba sus acciones.

En la fila que se puede ver abajo tenemos la cinta. La máquina comienza escribiendo una secuencia de inicio, que le servirá para controlar el proceso.

En verde aparecerá la próxima configuración que se ejecutará, en naranja la que se acaba de ejecutar. Si la siguiente configuración es la misma que la que se acaba de ejecutar, se mantiene el color naranja.

El pase de diapositivas requiere JavaScript.

Podemos realizar cualquier cálculo que se nos ocurra con una máquina de Turing. Los ejemplos que dio Turing eran sencillos porque buscaba la comprensión del lector. A poco que busquéis, veréis que se han hecho todo tipo de ejemplos de máquinas de Turing, en la documentación de un curso de análisis de algoritmos de la universidad Cornell, hay un artículo, que en la página ocho, describe como hacer una criba de Eratóstenes para saber si el número de símbolos 1 de una cadena de entrada es primo.

Una vez definido el funcionamiento de la máquina, Turing pasó a buscar una forma de encontrar un número que describiera a la máquina. Para ello modificó la forma de expresar la escritura en la cinta y pasó de los símbolos P0, P1 o Px a identificar cada escritura con un número. Por ejemplo, si el alfabeto con el que permite trabajar la máquina es {x, 0, 1,…},  tendríamos que Px pasaría a ser S0, P0 pasaría a ser S1 y P1 pasaría a ser S2. A continuación estableció una correspondencia entre configuraciones y acciones y letras:

  • Cada configuración-m q_i, será sustituida por una D, seguida de un número de Aes igual al subíndice i.
  • Cada escritura S_i, será sustituida por una D y tantas Ces, como valor tenga i.
  • R (mover a la derecha), L (mover a la izquierda), E (borrar) se escribirán con sus letras correspondientes.
  • Si no hay acciones en la configuración, se escribe una N.
  • Para separar una configuración de otra, se usará el punto y coma.

Además ya no podremos resumir la tabla, cada entrada de la tabla de configuración tendrá un solo símbolo activo. En nuestro ejemplo teníamos una fila de la tabla configuración así:

q3 0 o 1 R, R q3

Ahora lo que tendremos es dos líneas: q3S1RRq3 y q3S2RRq3

Los valores dentro de estas cadenas los traduciremos por:

  • q3: DAAA
  • S1: DC
  • RR: RR
  • S2: DCC

Quedándonos DAAADCRRDAAA; DAAADCCRRDAAA;

A esta cadena de texto, Turing la llamó “la descripción estándar de la máquina”. A continuación asignó un número a cada letra (A=1, C=2, D=3, L=4, R=5, N=6, ;=7), así que nuestra descripción estándar anterior pasaría a ser:

31113255311173111322553117

Y a este número Turing lo llamó “número de descripción (DN) de la máquina”. Gracias a este número, tenemos una forma de darle un único identificador a cada máquina de Turing que ideemos, un identificador que además la describe totalmente.

 La máquina de Turing universal

¿Y qué hacemos con este número? El siguiente paso de Turing fue idear una nueva máquina, a la que llamó “máquina universal”, a partir de ahora U. Ésta máquina tiene una configuración tal que, si le introducimos a través de la cinta un número de descripción de otra máquina, puede configurarse de tal manera que se convierte en la máquina que describe ese número.

Es decir, tenemos una computadora (máquina universal) a la que podemos introducirle cualquier software que se nos ocurra (número de descripción) y ejecutará las instrucciones que correspondan.

El primer paso que realizó Turing para abordar el Entscheidungsproblem fue solucionar primero un problema más simple: ¿se podría construir una máquina (D) que al recibir un número de descripción de otra máquina (T) pudiera decirnos si T termina su ejecución?

Para Turing que una máquina terminara su ejecución quería decir que en algún momento de su funcionamiento, no tenía más pasos que realizar. La máquina no era cíclica. En el caso de que la máquina estuviera realizando operaciones sin fin, la máquina se consideraba cíclica.

Si existiera esa máquina D, podríamos pasarle a través de la cinta el número de descripción de una máquina (G) que para cada número par entero n mayor que dos, busca dos números primos cuya suma sea n y pasa a calcular el siguiente número, a no ser que no encuentre esos dos números primos, entonces parará. Si la máquina D nos indica que la máquina G no termina nunca, habríamos demostrado la conjetura de Goldbach.

¿Puede existir la máquina D? Por desgracia no puede existir. Para demostrarlo Turing utilizó la diagonalización de Cantor, pero incluso él mismo indica que éste método es engorroso y ofreció una explicación más sencilla.

Imaginemos que la máquina D existe. Por tanto podemos pasarle cualquier número de descripción de una máquina T y nos dirá si ésta es cíclica o no.

Ahora utilizamos esta máquina D y creamos una máquina híbrida, denominada DU. La máquina DU en primer lugar funcionará en modo D, y comprobará si el número de descripción de la máquina T que llega en la cinta corresponde a una máquina circular. Si la máquina T es circular, finaliza el trabajo de DU. Si la máquina T no es circular, DU pasa al modo U, que se configurará con el número de descripción de T y realizará los pasos determinados por esta máquina (T).

DU es una máquina no cíclica, ya que cuando reciba el número de una máquina cíclica desechará éste número y terminará. Cuando le pasemos un número de una máquina no cíclica, la ejecutará, y ya sabemos que es no cíclica. Por tanto DU es una máquina que siempre termina su ejecución en algún punto.

¿Pero qué pasa si a la máquina DU le pasamos el número descriptor de la propia DU?

1.- DU se sitúa en modo D y comprueba que el número de descripción, correspondiente a DU, pertenece a una máquina no cíclica.

2.- DU se sitúa en modo U y se configura para ejecutar la máquina DU’ (le ponemos el ‘ para distinguirla de la máquina DU inicial).

3.-DU’ inicia su ejecución, se sitúa en modo D y comprueba que el número de descripción que se encuentra en la cinta, correspondiente a una máquina DU, pertenece a una máquina no cíclica.

4.- DU’ se sitúa en modo U y se configura para ejecutar la máquina DU”.

Podéis imaginar como sigue el proceso, cada máquina DU configurada volverá a crear otra máquina DU, hasta el infinito. Con esta elegante demostración, Turing reducía al absurdo la posibilidad de la existencia de una máquina D.

Todavía le quedaban unos cuantos pasos para acabar con el Entscheidungsproblem, pero si sigo, puedo acabar así:

life_of_brian___stoning_gif_by_kraljaleksandar-d3c7mbj

De pronto me han dado ganas de lentejas.

 

Legado

Los conceptos que presentó en este documento, junto a su trabajo en las máquinas Colossus para el descifrado de códigos de Enigma, situaron a Turing como uno de los mayores expertos en computación al final de la Segunda Guerra Mundial. Von Neumann quiso contar con él, pero en su breve visita a EEUU no se sintió cómodo y volvió a Inglaterra, donde creó el primer ordenador británico: ACE.

Mientras, en EEUU, se creaba el ENIAC y Von Neumann ponía nombre, de manera un tanto injusta, a su arquitectura. Prácticamente todos los ordenadores de hoy en día utilizan la arquitectura Von Neumann, en la que tanto  el programa a ejecutar como los datos, se encuentran en una misma memoria. Éste era el concepto que Turing adelantó en 1936 que acabaría imponiéndose en la breve historia de los computadores.

Arquitectura Von Neumann (Fuente Wikipedia)

Esta entrada participa en la edición 5.7 del Carnaval de Matemáticas, dedicada a Alan Turing y alojada por este blog.

turing

Referencias

On computable numbers with an application to the Entscheidungsproblem. Alan Turing.

Alan Turing. El hombre que sabía demasiado. David Leavitt. Antoni Bosch editor.

Carnaval de Matemáticas: #micromates, el concurso

Este mes el Carnaval de Matemáticas ha llegado al blog y como hicimos en febrero con el Carnaval de Física, vamos a aprovechar la semana del Carnaval para dar rienda suelta a nuestra creatividad en 140 caracteres. El 20 de octubre iniciaremos la semana de:

 

micromates

Las reglas son muy sencillas:

1.- Los microrrelatos incluirán el hashtag #micromates.
2.- Podrán enviarse vía twitter o, en caso de no tener usuario en twitter, como comentario dentro de esta entrada.
3.- El límite de tamaño será de 129 caracteres (los 140 de límite de Twitter menos los 11 del hashtag).
4.- Deberán tener relación con las matemáticas.
5.- No hay límite de microrrelatos por participante.
6.- Los microrrelatos podrán enviarse entre el lunes 20 de octubre y el domingo 26 de octubre.

Un microrrelato podría ser:

Se despertó y la integral seguía allí #micromates

(ya lo pongo yo por si a alguien se le ocurría hacer la versión del microrrelato del dinosaurio ;P)

¿Y qué haremos con estos microrrelatos? Pues una vez llegado el día límite, nuestro jurado elegirá los mejores, que formarán parte del resumen final del Carnaval. Además, el mejor relato recibirá como premio un libro. Como esta edición está dedicada a Alan Turing, he elegido un libro que habla sobre su vida y que me encanta:

libro

 

Nuestro magnífico jurado y yo esperamos leeros a partir del día 20. ¡Salud y Matemáticas!

 

turing

Carnaval de Matemáticas. Edición 5.7: Alan Turing

El Carnaval de Matemáticas nos visita, un carnaval al que le tengo especial cariño porque, aunque soy un “extranjero”, siempre ha recibido mis locuelas historias con los brazos abiertos. Este año se dedica cada una de las ediciones a un matemático y, como informático de formación que soy, elijo a:

turing

Alan Turing

La máquina de Turing

Alan Turing es una de las figuras más apasionantes del siglo XX. En 1936, con 24 años de edad, publicó uno de los artículos más influyentes en el mundo de la informática: “On computable numbers, with an application to the Entscheidungsproblem“.

Entscheidungsproblem era un problema a caballo entre las matemáticas y la filosofía. Se trataba de saber si había un algoritmo que dada una fórmula de lógica de primer orden, pudiera determinar si era un teorema o no. Por ejemplo, este algoritmo podría aplicarse a la conjetura de Goldbach y nos diría si es un teorema o no.

Para resolverlo, Turing se valió de un experimento “mental”. Ideó una máquina capaz de procesar una serie de datos con unas reglas fijas. A partir de esta primera máquina ideó una segunda, la cual era capaz de leer una descripción de la anterior junto a los datos de entrada y obtener el mismo resultado. En esta idea residía el germen del ordenador actual: una máquina que podía recibir como información un algoritmo y unos datos y obtener un resultado.

Finalmente Turing demostró que este algoritmo no podía existir,  pero esto es algo de lo que os hablaré durante el carnaval, tened paciencia.

La Guerra y los primeros ordenadores

Todavía le quedaba mucha cuerda a este corredor de fondo. Durante la Segunda Guerra Mundial, Alan fue uno de los puntales principales del arma secreta más importante de Churchill. Desde los pabellones de Bletchley Park, Turing y un ejercito de matemáticos, técnicos y personas de toda índole se dedicaron a descifrar los códigos secretos alemanes. Turing colaboró activamente en la creación de Colossus, una máquina de análisis capaz de destripar los códigos del dispositivo Enigma. Los códigos cambiaban diariamente y las máquinas Colossus británicas los descifraban a primeras horas de la mañana. Según palabras del propio Churchill, el trabajo en Bletchley Park redujo la duración de la guerra en dos años.

colossus

una máquina Colossus en plena operación

Del trabajo en las máquinas Colossus, Turing extrajo una gran experiencia que pudo emplear en la creación del primer ordenador británico: ACE. Los americanos acabaron adelantándose con ENIAC, y la falta de presupuesto y sus propios fantasmas acabaron llevando a Turing a la depresión y a la pérdida del control de este proyecto.

Alan fue también una figura importante para la inteligencia artificial. “¿Las máquinas piensan?” fue la pregunta que se hizo Turing y llegó a crear el test de Turing, para intentar dar una primera respuesta a esta pregunta.

El final

Turing cree que las máquinas piensan

Turing yace con hombres

Luego las máquinas no piensan

Alan Turing

Por desgracia Turing también es conocido por su trágico final. Una denuncia por un robo en su apartamento, acabó en una investigación sobre sus tendencias sexuales. El resultado final fue un proceso legal en su contra que acabó con la obligación de realizarse un tratamiento hormonal.

En realidad se trataba de una castración química. A Turing se le retiraron todas las credenciales de seguridad y acceso a edificios del gobierno que había ganado con su importante trabajo durante la guerra. El tratamiento le hizo ganar mucho peso y Alan, un hombre acostumbrado a correr largas distancias, se vio de pronto en un cuerpo que no reconocía y prácticamente solo. El suicidio fue la consecuencia final.

El carnaval

Desde el lunes 20 de octubre hasta el domingo 26 de octubre, tendréis la oportunidad de mandar vuestras historias matemáticas para participar en este carnaval.  El tema es completamente libre y las normas para poder participar son las siguientes:

  1. Publicar, entre el 20 y el 26 de octubre, algún contenido que tenga relación con las matemáticas. (Si no tienes blog, te prestamos el del Carnaval de Matemáticas).
  2. En tu publicación, enlazar a la web del Carnaval de Matemáticas y a esta entrada. Por ejemplo así:

    Esta entrada participa en la Edición 5.7: Alan Turing del Carnaval de Matemáticas, cuyo anfitrión es el blog El zombi de Schrödinger.

    Y si quieres puedes incluir el logo de la edición.

  3. Avisarme para que pueda incluir tu aportación en el resumen enviando tu enlace de cualquiera de estas formas:

 

La sorpresa

Habrá sorpresa durante la semana del carnaval. Si seguís este blog, ya os imaginaréis lo que estamos preparando. Dentro de unos días ampliaremos la información, id afinando vuestro ingenio matemático en 140 caracteres.

Yf0tR4v

Aquí me quedo, esperando vuestras historias.

Ediciones anteriores

 

En el infinito, las cosas no son lo que parecen

Dividir un número entre cero no da como resultado un número infinitamente grande. La razón es que la división se define como una multiplicación a la inversa: si se divide entre cero, y luego se multiplica por cero, debería recuperarse el número con el que se comenzó. Sin embargo, multiplicar infinito por cero da como resultado cero, y ningún otro número. No hay nada que pueda ser multiplicado por cero para dar un resultado que no sea cero; por tanto, el resultado de una división entre cero está literalmente “indefinido”.

Ted Chiang. Dividido entre cero.

Cuando se estudian matemáticas en el bachillerato y en la universidad, el infinito aparece en todo su esplendor. Nos acostumbramos tanto a calcular límites cuando x tiende a infinito y a obtener límites cuyo resultado es “infinito”, que acabamos considerándolo como algo normal.

Sin embargo, el infinito es un concepto peliagudo, que nos puede llevar a paradojas que van contra la propia razón. Georg Cantor dedicó gran parte de su carrera al estudio del infinito y obtuvo resultados que van en contra del sentido común y que le acarrearon más de un enemigo y muchos disgustos personales.

El campo de estudio de George Cantor fue la teoría de conjuntos, y utilizó esta teoría para acercarse al infinito. Por ejemplo, para demostrar que los números enteros pares e impares son conjuntos con el mismo número de elementos, Cantor asignaba a cada número del conjunto de los pares, un número del conjunto de los impares:

pares

Asignación entre los números pares e impares positivos

Si conseguimos que esta asignación sea biunívoca, es decir que a cada elemento de un conjunto le pertenezca un único elemento del otro conjunto y viceversa, habremos demostrado que ambos conjuntos tienen el mismo número de elementos. Una idea elegante y sencilla, pero veamos a dónde nos lleva esta idea si seguimos avanzando.

¿Qué os parece si ahora comparamos los números enteros con los números racionales? Los números racionales son aquellos formados por una fracción en la que numerador y denominador son números enteros. Por ejemplo, 2/1 es un número racional, que a la vez es 2, un número entero. Sin embargo 1/2 es un número racional, pero no es un número entero, ya que tiene parte decimal. Todos los números enteros pueden expresarse como un número racional, simplemente tenemos que dividirlos entre uno, pero no ocurre a la inversa.

Pero ahora comparemos ambos conjuntos a la manera de Cantor. En esta ocasión, Georg ordenó los números racionales de la siguiente forma:

En primer lugar los números cuyo numerador y denominador suman 2, luego los números cuyo numerador y denominador suman 3, y así sucesivamente, colocando primero las fracciones con un numerador menor:

racionales1

Fracciones para las que la suma de denominador y numerador es 2, 3, 4 y 5.

Ahora que hemos conseguido un orden, nos bastará con ir asociando números enteros positivos a cada número racional positivo:

racionales2

Vamos situando las fracciones según la suma de denominador y numerador y vamos asignando a cada una un número entero.

Y como a cada fracción podemos asociarle un número entero y viceversa, podemos deducir que el conjunto de los números racionales tiene el mismo número de elementos que el de los números enteros.

contando

No me miréis así, a Cantor le criticaron tanto que el hombre acabó un poco deprimido, así que ahora no os paséis conmigo, que soy un simple mensajero y queda lo mejor por contar.

Puntos, puntos y más puntos

Vamos ahora a comparar los números enteros con los números reales. Tomemos una recta cualquiera, como esta:

recta

En esta recta hay infinitos puntos: tenemos el 0, el 1, el 0.5, el 0.5000000001, etc. Un día me preguntaron cómo representaría el concepto de infinito, pinté esta misma recta y solté una charla. Sí, tal como estáis pensando, no tengo muchos amigos.

Vamos a ver si podemos relacionar el conjunto de puntos de esta recta con los números enteros. Lo primero será buscar una forma de ordenar los puntos de la recta para poder asociarle, a cada uno, un número entero.

Veamos, podemos empezar por el cero, luego podemos coger el 0.1 y entonces mmmh… No.  Si ponemos luego el 0.1 nos dejamos por el camino el 0.01, y el 0.001, y el 0.o001 y ¡UFF! ¡Podemos seguir hasta tener infinitos ceros antes de poner un miserable 1! Y bueno, estos ejemplos son números racionales, podríamos usar un truco parecido al anterior, pero es que por medio también habrá números irracionales y cada vez que queramos realizar una ordenación, el listo de turno podrá añadir un nuevo decimal y reírse de nosotros.

tfacepalm

Cuando abrimos el tarro de las esencias de los números reales, nos aparece un número infinito de decimales y en muchas ocasiones sin ningún tipo de periodicidad.

No podemos conseguir una ordenación de los puntos que hay dentro de nuestra recta que nos permita asociar cada uno de ellos a un número entero. Para realizar la demostración, Cantor pensó en un orden cualquiera asociado a los números reales entre 0 y 1, por ejemplo:

ordenacionimposible4

En esta matriz estarían todos los números reales entre cero y uno, con un número entero asociado. Ahora bien, formemos un número de la siguiente forma: del primer número escogemos el primer decimal, le sumamos uno y lo colocamos en el primer decimal de nuestro nuevo número; del segundo número escogemos el segundo decimal, le sumamos uno y lo situamos en el lugar del segundo decimal y así sucesivamente. En nuestro caso tendríamos: 0.309448498…

Pues bien, el número que acabamos de crear, no forma parte de la ordenación anterior. En cualquier lugar que lo coloquemos, el decimal correspondiente a esa posición será incorrecto. Por ejemplo, si lo colocáramos en la posición 9, el noveno decimal es diferente, ya que su valor es el de ese mismo decimal más uno. El número que hemos creado siempre “chocará” en la diagonal independientemente de donde queramos colocarlo. La ordenación que hemos supuesto inicialmente es imposible.

Ante este hecho, Cantor declaró que el infinito del número de puntos que se encuentran en una recta es de un orden superior al infinito del número de elementos de los números enteros.

Pero, ¿y si comparamos nuestra pequeña recta con una más grande?

triángulo

En este simple esquema, podemos ver cómo siempre podremos asignar a cada punto de la recta más grande (roja), uno de la recta más pequeña (azul). Solo hay que colocar las rectas formando un triángulo y lanzar líneas paralelas como las que vemos en el esquema.

¿Y si la segunda recta es infinitamente larga? Para verlo mejor me vais a permitir un truco: doblar la primera recta hasta formar un círculo, y lo  colocamos así en nuestra recta infinita:

lineaycirculo

Bueno, imaginad que la línea roja sigue hacia el infinito por la derecha y por la izquierda, tampoco seamos tiquismiquis.

Ahora ponemos un punto fijo arriba, en la parte del círculo más alejada de la recta, y un punto móvil abajo:

lineacirculointerseccion

Al trazar una recta que atraviesa ambos puntos, tenemos una intersección con la línea roja. Ahora movamos el punto móvil bordeando el semicírculo que queda debajo de la línea roja:

infinitoabajo0

Al mover el punto sobre el semicírculo de abajo, podemos obtener cada uno de los puntos de la recta que quedan dentro del círculo. Solo tenemos que tomar pasos cada vez más pequeños si queremos más precisión. ¿Pero qué pasa cuando movemos el punto por el semicírculo que queda encima de la recta?

infinitoarriba0

Podemos obtener todos los puntos que hay en la recta y que han quedado fuera del círculo jugando con el desplazamiento del punto móvil; a medida que lo hagamos con más precisión, podremos obtener cualquier punto que deseemos. Si queremos obtener los puntos negativos, solo tenemos que recorrer el resto del semicírculo.

Así que el conjunto de puntos de cualquier recta que elijamos tiene la misma cardinalidad, independientemente de su tamaño, incluso si tenemos una recta de un tamaño infinito.

cantorinfinito2

Subiendo de dimensión

¿Y los puntos de un cuadrado? Evidentemente el conjunto de los puntos de un cuadrado tendrá un número infinito de elementos, pero ¿será comparable a una recta?

Habrá que buscar una forma de ordenar los pares de puntos de un cuadrado de forma que cada uno se corresponda con un único punto de la recta. Vamos a escoger un cuadrado de lado 1 y una recta de longitud 1:

cuadradoyrecta

Escogemos un punto del cuadrado y obtenemos sus coordenadas, por ejemplo (0.25, 0.33). Podríamos crear a partir de estas coordenadas el siguiente número: 0.2533, incluyendo primero los decimales de la primera coordenada y luego los de la segunda.

cuadradomal1

Pero ¿y si cogemos el par de puntos (0,2 ,0,533)? Pues no, no funciona, porque el punto de la recta que obtendríamos sería 0.2533, el mismo que habíamos obtenido antes.

cuadradomal2

¿Cómo podemos conseguir una ordenación que nos permita asignar a cada par de puntos del cuadrado un punto de la recta? Piénsalo un poco, intenta dar con la forma correcta para formar el valor asignado a la recta y, cuando quieras ver la solución, ve al final del artículo.

La solución existe y llevó a Cantor a proclamar que el segundo orden de infinito era el formado por el conjunto de puntos de cualquier objeto geométrico, en un número de dimensiones cualquiera. Es decir, el conjunto de los puntos que se encuentra dentro de un cubo de cualquier tamaño tiene la misma cardinalidad que el conjunto de los puntos que hay dentro de una pequeña recta.

Hay un tercer orden de infinito descubierto por Cantor, pero esa es otra historia que merece ser contada en otra ocasión, ahora os dejo con una última paradoja.

La paradoja final

Si has llegado hasta aquí, te estoy infinitamente agradecido, aunque debo confesarte que en todo lo que he contado hay oculta una paradoja muy curiosa.

Hemos visto cómo a partir de un círculo podemos obtener todos los puntos de la recta real. ¿Todos?, ¿seguro?

A medida que acercamos el punto móvil al fijo, por la derecha o por la izquierda, obtenemos cada vez valores más grandes, prácticamente imposibles de transcribir. ¿Cuándo alcanzaremos el valor infinito exactamente? Lo lógico sería pensar que lo obtendremos cuando los dos puntos se junten, ocupando el mismo espacio.

paradoja

Pero si se trata del mismo punto, ¿cómo podemos trazar la línea recta que servía para conseguir la intersección con la recta real? No, no se puede. Con un solo punto no puede definirse una línea porque, amigos, el infinito es indefinido.

bart

MULTIPLÍCATE POR CERO

Hay una forma de llegar a formar esa línea recta, al prescindir del punto móvil y usar “otra cosa”, pero también llegaríamos a una paradoja. ¿Te animas a intentarlo?

La solución al cuadrado

Para obtener un solución al problema del cuadrado hay que utilizar un truco muy ingenioso:

Tenemos 0.25 y 0.5. Pues bien, lo que haremos será ir escogiendo en cada ocasión un decimal de cada uno de los puntos. Primero cogeremos el 2 de 0.25, luego el 5 de 0.53, a continuación el 5 de 0.25 y así sucesivamente. De esta forma tendremos:

coordenadas1

Cuando una de las coordenadas no tiene el mismo número de cifras significativas que la otra, utilizaremos el cero. Por ejemplo (0.200, 0.553)

Mediante este sistema, podemos situar cada par de puntos del cuadrado en un único punto de la recta. Además, si nos fuéramos a un número mayor de dimensiones, solo tendríamos que ir repitiendo el proceso para más coordenadas, por ejemplo:

coordenadas2

En definitiva, Cantor era un genio.

Este artículo participa en la edición 5.6: Paul Erdős del Carnaval de Matemáticas. El carnaval tiene lugar en el blog Cifras y teclas, un lugar que no os podéis perder.

Y este artículo fue el más votado en la edición 5.6: Paul Erdős del Carnaval de Matemáticas y en consecuencia, puedo lucir este bonito entorchado:

Premio-CarnaMat56

Más información

One Two Three . . . Infinity: Facts and Speculations of Science (Dover Books on Mathematics). George Gamow.

Georg Cantor en Wikipedia en español, Wikipedia en inglés (más completo).

La historia de tu vida. Recopilatorio de relatos de ciencia ficción en el que aparece división por cero.

@SamuelDalva este artículo le ha recordado la paradoja de la rueda de Aristóteles.

@Gaussianos nos ha recordado un artículo sobre la diagonalización de Cantor.

Por último, tengo que agradecer a mi profesor de Métodos Matemáticos I en la UNED, Juan Perán, por descubrirme esta historia en una de sus magníficas clases.

Meme(z): Descripción musical

Pues sí, he caído en las redes de un meme(z) por culpa de DrLitos, de hecho tengo pendiente varios. Como este iba de música, me ha picado el gusanillo y voy a salir de mi retiro mediático para dar respuesta al desafío.

  • Normas : Escoge una banda/grupo favorito, y responde solo con títulos de sus canciones.
  • Nominado por: DrLitos
  • Banda o grupo elegido: Dream Theater, últimamente están un poco cascadetes, pero que años 20 me hicieron pasar :_)

¿Eres hombre o mujer?

As I Am.

Descríbete

Caught in a web.

¿Qué sienten las personas acerca de ti?

Enigma Machine.

¿Cómo describirías tu anterior relación sentimental?

6:00.

Describe tu actual relación con tu pareja

The dance of eternity.

¿Dónde quisieras estar ahora?

Peruvian skies (visitando cierto array de telescopios).

¿Cómo eres respecto al amor?

Through her eyes.

¿Cómo es tu vida?

Genial, digo stream of consciousness.

¿Qué pedirías si tuvieras un solo deseo?

A change of seasons (como el de las elecciones europeas, pero a lo bestia).

Escribe una cita o frase sabia

Lines in the sand.

Ahora despídete

Finally free.

Y ahora solo queda nominar a alguien para que perpetúe este ejercicio de egoblogoirrelevancia en el que nos embarcó inicialmente eulez. Y los nominados son:

 

Aquí tenéis la lista de canciones para los que disfrutéis de Spotify: meme(z).

Nos vemos al final de los exámenes : )

¡VIVA LA EGOBLOGOIRRELEVANCIA!

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 1.393 seguidores

A %d blogueros les gusta esto: