Acerca del problema de la decisión. De la lógica a la computabilidad (Antonio Nakid)

Expositor: Antonio Nakid Cordero

Cuándo 08/03/2017  de 14:30 a 15:30
Dónde Salon de seminarios Graciela Salicrup

Resumen

En 1928 como parte del programa formalista, Hilbert propone el entscheidungsproblem (problema de la decisión, en español): encontrar un algoritmo que determine, dado un conjunto de axiomas y una proposición, si la proposición puede ser probada a partir de esos axiomas. Responder a esta pregunta llevó a matemáticos de la talla de Church, Turing y Gödel a formalizar la noción de algoritmo, pues para dar una respuesta negativa al problema hacía falta probar que ningún algoritmo que pudiese pensarse podría realizar la tarea.

En esta plática nos concentraremos en el trabajo realizado por Alan Turing en su artículo “On computable numbers, with an application to the entscheidungsproblem”, en el cual propone lo que ahora conocemos como máquina de Turing y resuelve el problema de la decisión mediante la reducción de este a un problema más sencillo.

¡No se requieren conocimientos previos!