Teoría clásica de la computación

Abstract

[en] In Computer science, the Entscheidungsproblem (literally, decision problem) represented one of the most transcendental mathematical and logical challenges of the last centuries, delimiting the boundary between the computable and the uncomputable. This paper presents a theoretical revision to the negative answer to this problem, focussing on the contribution of Alan Turing, who formalized the concept of algorithm through the introduction of the Turing Machine. Furthermore, Church’s Theorem is examined in depth; a result of paramount importance that establishes the undecidability of tautologies in first-order logic. Moreover, some results central to the classical theory of computation are presented, which allow proving that lots of computational problems are not solvable. Through the analysis of these results, the close relationship between theory of computation and formal logical systems is elucidated, as well as the intrinsic unsolvability of some problems.

[es] En Ciencias de la computación, el Entscheidungsproblem (literalmente, problema de decisión) representó uno de los desafíos matemáticos y lógicos más trascendentales de los últimos siglos, delimitando la frontera entre lo computable y lo no computable. Este trabajo presenta una revisión teórica de la respuesta negativa a este problema, centrada en la contribución de Alan Turing, quien formalizó el concepto de algoritmo mediante la introducción de la Máquina de Turing. Asimismo, se examina en profundidad el Teorema de Church, un resultado de suma importancia que establece la no decidibilidad de las tautologías en la lógica de primer orden. Se presentan también resultados centrales de la teoría de la computación clásica, que nos permiten demostrar que muchos problemas computacionales son irresolubles. A través del análisis de estos resultados, se dilucida la estrecha relación entre la teoría de la computación y los sistemas lógicos formales, además de la irresolubilidad intrínseca de algunos problemas.