Archivo de la categoría: Divulgación

Nos vemos en Desgranando ciencia

fondo-twitter_04

Desde el 8 hasta el 14 de diciembre, la ciencia ha tomado la ciudad de Granada. Desgranando ciencia está llenando de talleres y charlas las calles de Granada y el fin de semana tomaremos el parque de las Ciencias.

La entrada es gratuita, lo único que tendréis que soportar una charla por parte de un servidor. Se han vuelto locos y me han dado 10 minutos para hablar de física ¡a mí! Y este es el engendro que tengo ya preparado:

primicia

Así que os esperamos durante todo el fin de semana en el Parque de las Ciencias de Granada. Aquí tenéis el programa, lleno de talleres, mucha ciencia, monólogos y diversas actuaciones. Y si tenéis niños, no dudéis en venir, se lo pasarán pipa en los talleres.

¡Nos vemos en Graná!

Anuncios

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.

#Trending Ciencia: Desarrollan un filtro que solo deja pasar la luz que incide en un determinado ángulo

NewsImage_Optical1

 

Investigadores del MIT han desarrollado un filtro que únicamente deja pasar la luz que llega a él en un determinado ángulo. Hasta ahora no teníamos problemas para filtrar la luz según su color o su polarización, pero había muchas dificultades para hacerlo según el ángulo y solo se había conseguido para ciertas longitudes de onda fuera del espectro visible. Este nuevo filtro funciona con todo el espectro visible. Podéis saber más del tema escuchando mi Trending Ciencia de hoy:

e0189bd6b17fe1f9a135d858a97a3315

04/04/2014. Desarrollan un filtro de luz basado en el ángulo de incidencia.

Más información

Artículo en MIT news.

Enlace al podcast.

Aquí tenéis un vídeo en el que se puede ver el filtro en funcionamiento:

 

Ya no se redondea como en los viejos tiempos

Hoy he asistido sorprendido a uno de esos momentos que hace que te explote la cabeza. Todo empezó con este tuit:

tuit1

Rápidamente me puse manos a la obra y lo probé en python, con la ventaja de que por las particularidades de este lenguaje siempre tengo instaladas dos versiones en los ordenadores que uso.

Capturapython

Así que en la versión 2.7 de Python vemos el redondeo “de toda la vida”, en el que el redondeo de 1.5 es 2 y el redondeo de 2.5 es 3. Pero si ejecutamos el mismo código para la versión 3.2 de Python tenemos que para ambos casos el resultado es 2.

¿El mundo se ha vuelto loco? Eso es lo primero que pensé, pero resulta que no, todo esto tiene su lógica. En pocos tuits se resolvió el misterio:

tuit2

tuit3

Y de paso se demostró que soy un empanado que no se había enterado de este cambio. El IEEE 754 es un estándar para el tratamiento de números en coma flotante, o hablando para no informáticos: para tratar números con decimales. Y en este estándar se recomienda, desde 2008, que el redondeo que se debe usar es Round half to even. 

Con este redondeo lo que se hace es el redondeo de toda la vida con una excepción para los números que tienen como decimal 0.5. Cuando la parte decimal es 0.5 lo que se hace es redondear al entero par más cercano al número. Por eso al redondear 2.5 lo que obtenemos es un 2 en lugar de un 3, ya que 2 es el número entero par más cercano a 2.5.

¿Por qué? Maldita sea ¡Por qué!

Después de mi sorpresa e ira inicial y de buscar un poco de información me di cuenta de que el asunto tenía mucha lógica. ¿Por qué un número que acaba en 0.5 debe ser redondeado al entero inmediatamente superior? Al fin y al cabo está a medio camino entre dos enteros, elegir el entero superior es simplemente un acuerdo al que hemos llegado los falibles humanos. Lo justo en este caso, sería que en la mitad de los casos el redondeo sea hacia arriba y en la otra mitad, el redondeo fuera hacia abajo. Y precisamente eso es lo que consigue este método.

Además el redondeo clásico provocaba un problema al tratar con números negativos:

Capturapythonnegativos

En el redondeo clásico de números con 0.5 como parte decimal en nuestros programas estábamos eligiendo el entero inmediatamente superior para números positivos y el inmediatamente inferior para números negativos (3 es mayor que 2.5 y -3 es menor que -2.5). Si lo pensamos fríamente, no parece demasiado correcto. Con el nuevo método los números negativos y positivos pueden ser redondeados a su entero inmediatamente superior o inferior.

[Añadido] Como bien apunta darth_suicune en los comentarios, el motivo de escoger este método es más profundo y afecta directamente al hecho de realizar cálculos una vez realizado el redondeo. En banca se lleva usando muchos años este redondeo y también se le denomina redondeo Gaussiano o estadístico. Pues bien, con este redondeo los cálculos posteriores al redondeo (y sobre todo medias) son más precisos que cuando se usa un redondeo estándar.

Así que ya sabéis, hemos redondeado por encima de nuestras posibilidades y ha llegado la troika de los estándares y nos ha dado un buen meneo. Lo único que este meneo nos lo dieron hace años y yo no me he enterado hasta ahora, empanado que es uno.

Así me siento hoy. (Fuente Wikipedia)

Así me siento hoy. (Fuente Wikipedia)

PD: Podéis comprobar en Wolfram Alpha que la cosa va en serio:

round25wa

Viaje locuelo a otras dimensiones con Monte Carlo

Hace tiempo publiqué una entrada sobre la historia de los métodos Monte Carlo, entrada que tuvo su réplica en El escriba matemático, explicando la pequeña locura que fue mezclar Python y Geogebra 5 en fase beta. De estos dos posts surgió esta animación de cálculo del número PI:

Cálculo de PI mediante el método Monte-Carlo

 

Pero ¿se puede afinar más en la búsqueda del número PI por este método? La respuesta es un SÍ rotundo. Una característica importante a la hora de ejecutar un método Monte Carlo es realizar una buena elección del generador de números aleatorios, cosa que no hice.

El cálculo de PI es un ejemplo de integración mediante método Monte Carlo: calculamos el área del sector del círculo y, gracias a la relación entre el área de ese sector y del cuadrado que lo contiene, obtenemos la aproximación de PI.

El área del cuadrado será

A_{cuadrado} = r^2

y el área del sector será

A_{sector} = 1/4 \pi r^2

Si dividimos el área del sector por el área del cuadrado, tendremos:

\frac{A_{sector}}{A_{cuadrado}} = \frac{\pi r^2}{4 r^2} = \pi/4

Si realizamos la división del número total de puntos que tenemos dentro del círculo respecto al número total de puntos que se han señalado en toda la área del cuadrado, tendremos una aproximación del valor de π

\frac{puntos dentro circulo}{puntos totales} \approx \pi/4

En este tipo de problemas, un buen generador de números aleatorios será aquel que consiga cubrir el espacio estudiado lo más homogéneamente posible. De esta forma, habrá más probabilidad de que la razón entre el total de puntos lanzados y los puntos dentro de nuestro objeto sea similar a la razón real entre el volumen de nuestro campo de pruebas y el objeto circunscrito que deseamos medir.

Investigando el tema, descubrí un generador de números pseudoaleatorios llamado secuencia de Sobol (más información aquí) y que distribuye puntos de una forma muy homogénea a lo largo de las dimensiones que elijamos. A continuación, un ejemplo de una distribución de puntos obtenida uniformemente y otra obtenida mediante una secuencia Sobol:

Comparativa de la generación de números aleatorios mediante el generador uniforme de python y la secuencia Sobol

Comparativa de la generación de 1000 puntos aleatorios mediante el generador uniforme de python y la secuencia Sobol

Lo siguiente fue comprobar si realmente se notaba la diferencia al realizar el cálculo de PI usando un método u otro. Aquí tenéis la comparación del cálculo de PI con un generador uniforme de números aleatorios y con un generador de secuencias Sobol:

Cálculo de pi mediante distintos tipos de generadores de números aleatorios.
Cálculo de pi mediante distintos tipos de generadores de números aleatorios. En el eje y tenemos el valor de pi y en el eje x el número de puntos utilizados en el cálculo.

El cálculo se realizó para distintos números de puntos lanzados, hasta un máximo de 100.000 puntos. Se puede ver con claridad la mejora que produce el uso de una secuencia Sobol (azul) respecto a un generador de números aleatorios uniforme. La convergencia hacia el valor de PI es muy evidente cuando usamos secuencias Sobol. Para ver el código fuente usado puedes ir a la parte final.

¿Por qué conformarnos solo con dos dimensiones?

Poco después descubrí un enlace a un artículo, ya con solera, de Gaussianos:

¿Cuál es el volumen de la bola unidad de dimensión N?

Grosso modo lo que nos cuenta es el particular comportamiento del volumen de una esfera de radio 1 a medida que aumentamos el número de dimensiones. Podemos ver cómo en principio el volumen aumenta con el número de dimensiones para luego decrecer, tendiendo hacia cero a medida que aumentamos n. La fórmula para el volumen de una n-esfera de radio 1 es:

V = \frac{\pi^{n/2}}{\Gamma \left ( \frac{n}{2}+1 \right )}

La explicación es bastante lógica; para que un punto del espacio de n-dimensiones se encuentre dentro de la n-esfera de radio 1 correspondiente, debe cumplir que su distancia al origen sea menor o igual a 1, y a medida que aumentamos las dimensiones llega un momento en el que es muy difícil encontrar puntos que cumplan esta condición, ya que para cada dimensión tenemos que sumar el cuadrado de un nuevo término.

La fórmula para saber si un punto está dentro de una n-esfera es:

\sum_{i=1}^n x_i^2 \leq 1

La rabia del asunto es que es imposible visualizar una n-esfera de más de tres dimensiones dentro de un cubo, a su vez, de n-dimensiones. Quizás sea imposible imaginarlo, pero una computadora sí que puede ayudarnos a hacer algo similar: podemos calcular aproximadamente el volumen de una n-esfera de la misma forma que hicimos antes con el área de un círculo. Así que toca lanzar n-puntos a cascoporro para meter el dedo en la yaga y ver si todo esto es cierto.

Para cada dimensión, el cálculo del volumen de la n-esfera de radio 1 será el siguiente:

V_n = V_{n cubo} \frac{puntos\ dentro\ n-esfera}{puntos\ totales}

Siendo el volumen del n_cubo: V_{n cubo} = 2^n ya que cada arista del cubo tendrá longitud 2: [-1,1].

El código para realizar el cálculo sería el siguiente:

#Calculo del volumen de una n-esfera. Como parametro recibe el numero de dimensiones y de puntos a generar, como salida devuelve el volumen
def calc_n_sphere_sobol(n_dimensions, n_points):
    #numero de puntos dentro de la n-esfera
    hits = 0
    #inicializador de la secuencia sobol
    sout = random.randint(1,10000)

    for i in range(0, n_points):
        #generar punto n-dimensional
        p, sout = sobol_lib.i4_sobol ( n_dimensions, sout )

        #transforma el numero del intervalo [0,1] al intervalo [-1,1]
        p = (p*2)-1
        j = 0
        s = 0

        #sumar cuadrado de las componentes
        while (j<n_dimensions and s<=1):
            s+=p[j]**2
            j+=1
        #comprobar si el punto esta contenido en la n-esfera
        if (s<=1):
            hits += 1
    #devolver volumen de la n-esfera
    return  (2**n_dimensions)* float(hits) / n_points

Y los resultados comparados con el volumen dado por la fórmula:

Cálculo del espacio ocupado por una n-esfera de radio 1 para distintas dimensiones

Cálculo del espacio ocupado por una n-esfera de radio 1 para distintas dimensiones. En el eje y tenemos el volumen y en el eje x las dimensiones.

Voi-lá, podemos ver cómo el método Monte Carlo se acerca a la función que describe el volumen de la n-esfera. Aquí están los datos obtenidos para 1.000.000 de puntos lanzados para las distintas dimensiones:

dimensiones volumen n-cubo volumen n-esfera Monte Carlo Puntos dentro
1 2 2,000000 2,000000 1000000
2 4 3,141593 3,141700 785425
3 8 4,188790 4,188096 523512
4 16 4,934802 4,936320 308520
5 32 5,263789 5,263712 164491
6 64 5,167713 5,174656 80854
7 128 4,724766 4,734080 36985
8 256 4,058712 4,066048 15883
9 512 3,298509 3,289088 6424
10 1024 2,550164 2,516992 2458
11 2048 1,884104 1,837056 897
12 4096 1,335263 1,314816 321
13 8192 0,910629 0,950272 116

El número de puntos que cumplen las condiciones de la n-esfera disminuye con el número de dimensiones, pero a la vez aumenta el volumen del n-cubo en el que está circunscrita. La relación máxima entre los puntos “acertados” y los lanzados respecto al volumen del n-cubo se da cuando llegamos a cinco dimensiones, y a partir de ahí el volumen de la n-esfera empezará a converger hacia cero.

Otra consideración a tener en cuenta es que cada vez que aumentamos una dimensión, el volumen del n-cubo aumenta. Como consecuencia, la muestra de 1.000.000 de puntos es menos significativa, por lo que los resultados empeoran si no aumentamos el número de puntos aleatorios utilizados.

∞∞∞

Este artículo se publicó originalmente el 12 de diciembre de 2012 en El escriba matemático, un blog donde incluyo artículos más técnicos y relacionados con la programación y herramientas matemáticas. Le tengo especial cariño a esta historia porque fue mi primera participación en un carnaval de matemáticas y tuvo su premio.

Este artículo participó en la 3.141592653 Edición del Carnaval de Matemáticas que alojó Que no te aburran las M@tes y ganó el premio al mejor artículo, porque los informáticos que estudiamos física a veces les caemos bien a los matemáticos 😛

Precioso, ¿verdad?

Referencias y enlaces de interés

La historia del método Monte Carlo: con ordenadores prehistóricos, bombas nucleares y personajes ilustres como Fermi, Ulam y Von Neumann.

Código fuente usado para realizar las pruebas

¿Cuál es el volumen de la bola unidad de dimensión N? en Gaussianos

Secuencias Sobol en Wikipedia

Implementación de Sobol en Python

A %d blogueros les gusta esto: