¿Parará, Papá?

Mi abuela solía contar un chiste en el que explicaba que la música empezó cuando Pachín estaba con su padre esperando el tranvía. Cuando se acercaba, Pachín preguntaba "¿Parará, Papá?" y el padre respondía "Parará, Pachín". Así que saber si algo va a parar puede ser muy interesante. Hoy vamos a preocuparnos del siguiente problema: tengo un programa y quiero saber si va a parar. Mejor, como quiero automatizar las cosas, quiero escribir un programa que nos diga si otro programa va a parar. Llamemos Parará al programa que hace la comprobación.

Este problema ya interesó a Alan Turing (sí, el de "The Imitation Game") y lo respondió negativamente. Es decir, que si escribimos Parará habrá entradas para las que falle (esto es, programas que paren para los que Parará diga que no o programas que no paren para los que diga que sí o programas que hagan que Parará no pare).

Fíjate que la clave está en que podremos escribir una versión de Parará y funcionará para algunos programas, pero no para otros. Por ejemplo, una primera versión de Parará podría decir que si el programa no tiene ni bucles ni llamadas a función parará siempre. La pena es que esta versión no nos serviría para programas con bucles. Si entonces escribimos la versión 2 que incluye bucles de la forma for x in range(...):, nos fallaría para los bucles while. Y lo que pasa es que por mucho que refinemos nuestra implementación, siempre encontraremos algún programa que lo haga saltar.

A estas alturas seguramente estarás pensando que Parará sería curiosa e interesante para cuatro frikis de la informática pero que no tendría mucha aplicación práctica. Sin embargo, sí que sería tremendamente útil para resolver muchos problemas. Por ejemplo, seguramente conoces la conjetura de Goldbach. Lo que nos dice es que todo número par mayor que dos puede escribirse como suma de dos números primos. Por ejemplo, 18 es la suma de 7 y 11, que son primos. Supongamos que escribo el siguiente programa en Python:


Para resolver la conjetura de Goldbach, me bastará llamar a Parará y pasarle este programa. Si me dice que no parará nunca, la conjetura es falsa; si me dice que parará, ya sabemos que es cierta. Esto ya nos hace sospechar algo: poder escribir un programa así sería un chollo. Así que vamos a ver cómo podemos demostrar que no podemos escribir Parará. Lo haremos por reducción al absurdo.

Para concretar el problema, Parará tendrá un parámetro, que será el nombre del fichero Python con el programa que queremos probar. Asumiremos también que está en nuestra ruta de búsqueda, con lo que podremos ejecutarlo llamando a subprocess (los detalles son irrelevantes, la idea es que desde otro programa podemos llamar a Parará). Cuando se ejecuta Parará, escribe por pantalla la cadena "para" si el programa para y "no para" si no lo hace.

Escribamos ahora un nuevo programa que guardaremos en borde.py:

Ahora, llamemos a borde con Parará. Tendremos que ejecutar parará borde.py. Pueden pasar tres cosas. Si Parará no para, ya hemos encontrado una entrada para la que falla. Por otro lado, si para y escribe para quiere decir que Parará piensa que borde.py parará. Ahora bien, al ejecutar borde.py, vemos que ejecutará en la línea 3 la orden parará borde.py (qué casualidad, ¿no?) por lo que en la línea 4 el resultado será cierto y entrará en el bucle infinito de la 5. Por último,  si lo escrito por Parará es no para, resulta que borde.py no entra en el bucle infinito y sí que termina. Así que, o bien Parará se equivoca, o bien no para. Malo en cualquier caso.

Las malas noticias son que es muy fácil utilizar este resultado para demostrar que muchos problemas que nos gustaría resolver no pueden resolverse mediante un programa. Por ejemplo, nos gustaría que nuestro compilador nos avisara si hay una parte del código a la que no es posible llegar. Muchos compiladores dan avisos en ciertos casos, por ejemplo si están en un if false:, pero nunca pueden resolver la cuestión al 100%. El argumento es sencillo. Supongamos que nuestro compilador pudiera avisarnos con seguridad de que un fragmento no es alcanzable. Tenemos ahora un programa del que queremos saber si para o no. Simplemente escribimos nuestro programa y le añadimos al final cualquier cosa, por ejemplo un print. Si el compilador no nos avisa de nada, es que el programa para. Si nos avisa de que el print es inalcanzable, es que el programa no para. (Es cierto que hay algunas sutilezas que habría que depurar, como qué hacer con llamadas a sys.exit, pero espero que la idea se entienda).

Una función que es la polla y tiene tetas

Introducción

Este post está motivado por la iniciativa lunesPollas. Y como no llegué a lunesTetas, junto las dos aquí (simbólicamente, claro). No seáis muy crueles, es mi primer post.

¿Qué función es la polla?

Empezaremos por un chiste. Pregunta el profesor a una alumna: "¿Qué parte del cuerpo puede aumentar diez veces su tamaño cuando se utiliza?". La alumna responde sonrojada: "Señor, no debería preguntar eso a una señorita decente como yo." a lo que el profesor replica: "Estaba preguntando por la pupila, pero felicite a su novio de mi parte". No hace falta explicar de dónde viene la confusión de la alumna, ¿no? Y si pensamos en crecimientos "desmesurados" la función que nos viene a la cabeza es la exponencial. Así que vamos a por la exponencial por excelencia: \(f(x) = e^x\). Hay varias formas de definirla, pero nosotros utilizaremos una que resultará luego cómoda, su serie de Taylor, igual te suena como polinomio de Taylor (en realidad, usaremos el de McLaurin, pero no nos pondremos muy pijos). Según nuestro amigo Taylor:
\[e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \frac{x^5}{5!} + \ldots \]
Algunas dudas que te pueden entrar son:

• ¿Qué son las exclamaciones? Representan la función factorial, si quiero escribir el producto \(1\times 2 \times 3 \times 4\) puedo ponerlo más corto simplemente como \(4!\).
• ¿Qué quieren decir los puntitos? Simplemente que la serie sigue y sigue hasta el infinito.
• Pero entonces, ¿no será infinito el resultado? Pues, no. Cojamos el término \(n\). Será de la forma \(\frac{x^n}{n!}\) y cuando \(n\) se hace muy grande, nos da un número muy muy pequeño porque tenemos tantos elementos arriba como abajo pero cuando \(n\) sea más grande que \(x\) la mayoría de los términos del denominador serán mayores que los del numerador.
• Aún así, al sumar muchos pequeñitos, ¿no podrían "irse de madre"? Bueno, a eso lo llamamos diverger. Si se te plantea esa duda, seguramente sabes que la serie \(1+ 1/2+1/2^2+\ldots\) es convergente. Para \(e^x\) podemos hacer una demostración formal, pero como estamos haciendo una presentación light, haremos un poco de blah blah. Fíjate que si \(n\) es muy grande, casi todos los números del denominador serán mayores que el doble del denominador y eso quiere decir que \(\frac{x^n}{2^n}\) será menor que \(1/2^n\). Por lo tanto, puedes ver la serie como una primera parte posiblemente muy grande seguida de un segunda parte muy larga pero cuya suma es menor que uno (hay veces en las que la longitud no lo es todo...).

Ya pero, ¿cuanto crece esta función? Para hacernos una idea de como crece, imaginemos que comienzas a andar a un metro por segundo. Es decir, que tu posición será \(x = t\). Al mismo tiempo, supongamos que logras lanzar verticalmente algo de modo que su posición sea \(y=e^t\). Cuando hayas dado veinte pasos, ya habrá pasado la luna y viajará más rápido que la luz. No me dirás que esta función no es la polla.

Ya, pero yo venía por lo de las tetas

Bueno, estamos en matemáticas, así que tenemos nuestras amigas, las funciones teta y coteta, aunque para ser más formales, las llamaremos seno y coseno. Resulta que sus series de Taylor son:
\[\text{sen}(x) = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \ldots \]
para el seno y
\[\text{cos}(x) = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \ldots \]
para el coseno. En ambos casos, \(x\) está en radianes.

Como puedes ver, casi están en \(e^x\) salvo por los signos, que están molestando.  Así que tendremos que usar la imaginación para relacionarlos con ella. En particular, usaremos números imaginarios. Recuerda que \(i\) es \(\sqrt{-1}\), lo que hace que sus potencias sean "raritas". A nosotros nos interesan las potencias de \(xi\) que serán:
\[
  (xi)^0 = 1, (xi)^1 = xi, (xi)^2 = -x^2, (xi)^3 = -x^3i, (xi)^4 = x^4, (xi)^5 = x^5i, \ldots
\]
Como ves, van en un ciclo en que los signos van alternando cada dos términos y las \(i\) aparecen y desaparecen en cada paso. Calculemos ahora \(e^{xi}\):
\[
  e^{xi} = 1 + xi + \frac{(xi)^2}{2!} + \frac{(xi)^3}{3!} + \frac{(xi)^4}{4!} + \frac{(xi)^5}{5!} + \frac{(xi)^6}{6!} + \frac{(xi)^7}{7!} + \ldots
\]
Sustituimos las potencias que hemos visto antes:
\[
  e^{xi} = 1 + xi - \frac{x^2}{2!} - \frac{x^3i}{3!} + \frac{x^4}{4!} + \frac{x^5i}{5!} - \frac{x^6}{6!} - \frac{x^7i}{7!} + \ldots
\]
Y ahora podemos agrupar los términos con \(i\) por un lado y por otro los que no la tienen:
\[
  e^{xi} = \Bigg(1  - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \ldots\Bigg) +
 \Bigg(x - \frac{x^3}{3!} + \frac{x^5}{5!}  - \frac{x^7}{7!} + \ldots\Bigg)i.
\]
 Y mira tú por donde, ya tenemos ahí las tetas de nuestra función:
\[ e^{xi} = \cos(x) + i\text{sen}(x). \]

Por cierto, si te acuerdas de que \(cos(\pi) = -1\) y \(\text{sen}(\pi) = 0\), tenemos que
\[ e^{\pi i} = -1, \]
o, como puede que la hayas visto:
\[ e^{\pi i}+1 = 0,\]
que es la ecuación (o identidad) de Euler, que fue uno de los grandes matemáticos de todos los tiempos. Puedes leer sobre él aquí.
Si te sorprende o no te lo acabas de creer, no estás solo. Esto decía xkcd en uno de sus comics:

 

Esta sorprendente ecuación aparece en lugares insospechados como

Aunque dejo al criterio de cada uno decidir si belleza matemática y estética cutánea están unidas. Lo que es interesante es la circunferencia que tiene encima de la ecuación. Resulta que si dibujamos todos los valores de \(e^xi\) en el plano complejo, podemos darnos cuenta de que son los puntos con coordenadas \((\cos(x), \text{sen}(x))\). Recordando que \(\cos^2(x)+\text{sen}^2(x)=1\) puedes ver que todos estos puntos están en la circunferencia de radio unidad. Así que cuando \(e^x\) se pone a imaginar tetas y cotetas... ¡anda en círculos!

Saludos,
Juan Miguel