Los métodos efectivos y sus limitaciones
Santiago Figueira
Departamento de Computación, FCEyN-UBA

Sabemos que hay programas para todo. Las computadoras resuelven "problemas" de todo tipo. Lo vemos todos los días en los cientos de dispositivos que tienen adentro una computadora. Si nos abstraemos un poco (no demasiado), nos podemos convencer de que, a través de codificaciones adecuadas, estos "problemas" pueden pensarse siempre como funciones de números naturales en números naturales. Un argumento sencillo muestra que hay más funciones de este tipo que programas, aunque de los dos hay infinitos. Entonces ¿Realmente hay programas para todo? Más aún ¿Conocemos alguna función particular, con nombre y apellido, que no sea programable? Y yendo un poco más atrás ¿Qué es un "programa" y qué quiere decir que una función sea "programable"? En estas cosas se pusieron a pensar algunos matemáticos a principios del siglo XX: en tratar de formalizar la matemática y de entender los métodos efectivos y sus limitaciones. En esta charla les voy a contar la historia de los métodos efectivos, y de dos problemas importantes: uno con nombre largo y difícil (el Entscheidungsproblem) y otro con nombre corto y fácil (el Halt).