Máquinas Turing, problemas indecidibles y los límites de la computación

Abstract

Este Trabajo de Fin de Grado tiene como objetivo fundamental explorar los fundamentos teóricos de la computación desde una perspectiva matemática, abordando cuestiones clave como qué es una máquina Turing, cuál es el origen de los ordenadores y qué significa realmente “computar”. Se parte de los planteamientos de David Hilbert y la definición formal de máquina Turing para comprender cómo este modelo abstracto permite formalizar el concepto de algoritmo y, con ello, establecer los límites de lo que puede ser resuelto por una máquina. A través del estudio de sus extensiones, restricciones y capacidad de simulación, se profundiza en el análisis de las máquinas Turing. En la segunda parte, se analizan los problemas indecidibles, como el problema de la parada, y su relación con la clase de lenguajes recursivos y recursivamente enumerables. Finalmente, se abordan las clases de complejidad P, NP, NP-completo y NP-duro, incluyendo una demostración formal de que el problema SAT (satisfacibilidad booleana) es NP-completo.

This Final Degree Project aims to explore the theoretical foundations of computer science from a mathematical perspective, addressing key questions such as what a Turing machine is, what the origin of computers is, and what it truly means to “compute”. It begins with David Hilbert’s proposals and the formal definition of a Turing machine to understand how this abstract model allows us to formalize the concept of an algorithm and thereby establish the limits of what can be solved by a machine. Through the study of its extensions, restrictions, and simulation capabilities, the analysis of Turing machines is deepened. In the second part, undecidable problems—such as the Halting Problem—and their relationship with the classes of recursive and recursively enumerable languages are examined. Finally, the complexity classes P, NP, NP-complete, and NP-hard are addressed, including a formal proof that the SAT problem (Boolean satisfiability) is NP-complete.