Computabilidad e insolubilidad

Opiniones de los lectores

El libro de Martin Davis «Computability and Unsolvability» ofrece un tratamiento formal y riguroso de la teoría de la computabilidad y sus implicaciones en matemáticas e informática. Aunque ha sido apreciado por su profundidad y rigor, muchos lectores han señalado su difícil notación y la falta de ejemplos concretos, lo que lo hace menos accesible para quienes no tienen una sólida formación matemática.

⬤ Tratamiento exhaustivo y riguroso de la computabilidad y la teoría de funciones recursivas.
⬤ Estructura bien organizada; los teoremas se interconectan eficazmente.
⬤ Contenido valioso sobre cuestiones profundas acerca de la computabilidad y el décimo problema de Hilbert.
⬤ Reimpresión asequible de Dover.

⬤ Estilo muy formal que puede resultar difícil para lectores no versados en matemáticas.
⬤ Faltan ejemplos concretos para ilustrar conceptos.
⬤ Las pruebas pueden parecer tediosas y pueden saltarse pasos necesarios para la comprensión.
⬤ Algunas secciones son criticadas por ser áridas o sin vida.

(basado en 12 opiniones de lectores)

Título original:

Computability and Unsolvability

Contenido del libro:

En este texto clásico, el Dr. Davis ofrece una introducción clara a la computabilidad, a un nivel de licenciatura avanzado, que satisface las necesidades de especialistas y no especialistas por igual.

En la primera parte (capítulos 1-5), el profesor Davis esboza la teoría general de la computabilidad, tratando temas como las funciones computables, las operaciones sobre funciones computables, las funciones recursivas, las máquinas de Turing, los problemas de decisión autoaplicados e irresolubles. El autor ha tenido cuidado, especialmente en los siete primeros capítulos, de no suponer ninguna formación matemática especial por parte del lector.

La segunda parte (capítulos 6-8) comprende un tratamiento conciso de las aplicaciones de la teoría general, incorporando material sobre problemas combinatorios, ecuaciones diofantinas (incluido el décimo problema de Hilbert) y lógica matemática. Los tres últimos capítulos (Parte 3) presentan un mayor desarrollo de la teoría general, abarcando la jerarquía de Kleene, los funcionales computables y la clasificación de los problemas de decisión irresolubles.

Cuando se publicó por primera vez en 1958, esta obra introdujo mucha terminología que desde entonces se ha convertido en estándar en la informática teórica. De hecho, el prestigio del libro es tal que muchos informáticos lo consideran su introducción teórica al tema. Esta nueva edición de Dover hace que este texto pionero y ampliamente admirado esté disponible en un formato económico.

Para la edición de Dover, el Dr. Davis ha incluido un nuevo Prefacio y un Apéndice, El décimo problema de Hilbert es irresoluble, un importante artículo que publicó en The American Mathematical Monthly en 1973 y que fue premiado por la American Mathematical Society y la Mathematical Association of America. Estas adiciones aumentan aún más el valor y la utilidad de una exposición inusualmente clara y estimulante (Centre National de la Recherche Scientifique, París), ahora disponible por primera vez en rústica.