UNAM
You are here: Home / Actividades académicas / Seminarios en C.U. / Seminario Junior / Actividades / Acerca del problema de la decisión: De la Lógica a la Computabilidad

Acerca del problema de la decisión: De la Lógica a la Computabilidad

Ponente: Antonio Nakid Cordero
Institución: Facultad de Ciencias, UNAM
Tipo de Evento: Divulgation

When Mar 08, 2017
from 02:30 PM to 03:30 PM
Where Salon de seminarios Graciela Salicrup
Add event to calendar vCal
iCal

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!

Filed under: