Este proyecto recibió la máxima distinción académica (Matrícula de Honor) durante su evaluación oficial.
Esta tesis investiga los fundamentos y límites intrínsecos de la computación y el razonamiento formal desde una perspectiva algorítmica, culminando en un análisis riguroso y una demostración del Primer Teorema de Incompletitud de Gödel.
El trabajo une lenguajes de programación prácticos con modelos clásicos de computación para hacer conceptos teóricos profundos accesibles a través de la computación, los sistemas formales y las estructuras de demostración.
Problema y Motivación
Comprender las capacidades y límites de los sistemas de razonamiento formal es central tanto en la teoría de la computación como en áreas de machine learning donde surgen preguntas de expresividad, decidibilidad y representación.
Este trabajo plantea:
- ¿Qué significa que un problema sea computable?
- ¿Pueden los lenguajes de programación prácticos tratarse como sistemas matemáticos formales?
- ¿Cuáles son los límites fundamentales de la demostración y de la verdad?
Lo que Construí
- Introduje una clase de programas Python SISO y demostré que son tan expresivos como programas Python generales.
- Establecí una equivalencia constructiva entre programas Python y máquinas de Turing, permitiendo usar código real para razonamiento formal.
- Definí y clasifiqué problemas como decidibles, semidecidibles e indecidibles desde un enfoque computacional.
- Utilicé técnicas de autorreferencia y reducción para explicar la existencia de problemas indecidibles, destacando el Problema de la Parada.
- Formalicé conceptos de demostración, verdad y sistemas lógicos, conectando la demostrabilidad sintáctica con la verdad semántica.
- Ofrecí una demostración detallada del Primer Teorema de Incompletitud de Gödel en dos formas complementarias (semántica y sintáctica).
- Analicé las implicaciones matemáticas y filosóficas de la incompletitud.
Aspectos Técnicos Destacados
- Modelos de computación: Equivalencia entre Python y máquinas de Turing
- Teoría de problemas: Definición formal y clasificación de problemas computacionales
- Lógica y demostración: Sistemas formales, verdad, sintaxis vs semántica
- Incompletitud: Demostraciones duales del Teorema de Incompletitud
Impacto
Esta tesis demuestra la capacidad de:
- Razonar rigurosamente sobre sistemas computacionales abstractos
- Traducir teoría formal a programas ejecutables
- Comunicar ideas teóricas profundas de forma estructurada y reproducible
Refleja una combinación de programación práctica, razonamiento formal y pensamiento sistémico, habilidades directamente transferibles a sistemas avanzados de ML, diseño algorítmico y fundamentos teóricos de sistemas inteligentes.
Palabras Clave
Computación teórica • Máquinas de Turing • Lógica formal • Decidibilidad • Incompletitud • Computación en Python • Teoría de la computación
