La categoría de los ensamblajes, el topos efectivo y la tesis fuerte de Church

Ponente(s): Francisco Netzahualcóyotl Martínez Aviña

Existen distintas categorías, tales como la categoría de los ensamblajes (Asm) y el topos efectivo (Eff), en las cuales es válida la tesis fuerte de Church (SCT): todas las funciones (totales) de N a N son funciones (totales) recursivas. Esta tesis contradice uno de los resultados fundacionales de la teoría de la computabilidad, a saber, que existen funciones de N a N que no son recursivas. Mi objetivo en esta plática es triple: dar una descripción de los objetos y morfismos de Asm y Eff, tal que sea posible explicar por qué en ellas vale (SCT), a diferencia de otras categorías más ``clásicas'', como la de los conjuntos y las funciones totales entre ellos; discutir el rol que juega el cambio de lógica en la obtención de dichos resultados y, finalmente, extraer consecuencias a partir de los mismos acerca de nuestra noción de computabilidad.