Antonio Casares Santos: «¿Podemos programar usando únicamente bucles $\textit{for}$?»

En cualquier lenguaje de programación estándar podemos encontrar algunas operaciones básicas, condicionales (if), y bucles que permiten iterar una acción, en particular los bucles for y while. En casi todos los ejemplos de programas que pensemos podríamos reescribir el código para usar únicamente bucles for, pero, ¿es esto siempre posible?

En esta charla, Antonio Casares nos mostrará cómo una pregunta tan aparentemente inocente puede llevarnos a plantearnos las principales cuestiones de la teoría de la computabilidad. Se presentará la función de Ackermann y cómo se relaciona con la cantidad de bucles for utilizados en un programa, lo que nos permitirá construir una función intuitivamente calculable, pero para la que necesitaríamos utilizar bucles while para calcularla de forma algorítmica.

La introducción de bucles while en nuestro modelo de computabilidad tiene consecuencias muy peculiares, en particular algunos programas no terminarán. De esta forma se llega al problema de la parada: no es posible crear un programa correcto que analice el código de otros programas y decida si van a terminar o no (demostrado por Alan Turing en 1936).  Este fue el comienzo de un apasionante área de las matemáticas en el que se pretende estudiar hasta dónde pueden llegar los ordenadores y la mente humana en su afán por resolver problemas.

Si quieres saber más acerca del ponente, ¡visita nuestra sección de ponentes!