Computability and Logic - George Boolos, John P. Burgess, Richard Jeffrey

Este texto constituye una introducción técnica y pedagógica a la computabilidad y la lógica matemática, centrada en definir los límites de lo que puede ser resuelto mediante procesos algorítmicos. La obra comienza estableciendo la distinción fundamental entre conjuntos enumerables (aquellos que pueden listarse de forma exhaustiva, como los números enteros) y conjuntos no enumerables, utilizando el célebre método de diagonalización de Cantor para demostrar que existen infinitos inalcanzables incluso para una capacidad de cómputo idealizada. Posteriormente, el autor introduce la Máquina de Turing como un modelo teórico riguroso que formaliza la noción intuitiva de efectivamente computable, permitiendo así analizar qué funciones pueden ser procesadas por un mecanismo automático. A través de un enfoque didáctico que utiliza configuraciones de cinta, estados internos y diagramas de flujo, el texto busca salvar la brecha entre la matemática abstracta y la teoría de la computación, preparando al lector para comprender teoremas avanzados sobre la indecidibilidad y las limitaciones inherentes a los sistemas lógicos.