Introducción matemática a la computabilidad

Opiniones de los lectores

Actualmente no hay opiniones de lectores. La calificación se basa en 2 votos.

Título original:

A Mathematical Primer on Computability

Contenido del libro:

El libro proporciona una introducción autocontenida a la teoría de la computabilidad para estudiantes avanzados de licenciatura o de los primeros cursos de posgrado de matemáticas e informática. El material técnico se ilustra con abundantes ejemplos, problemas con soluciones totalmente trabajadas y una serie de ejercicios propuestos.

La Parte I se centra en nociones y resultados fundamentales de computabilidad, empezando por los conceptos fundamentales de modelo computacional (un lenguaje de programación abstracto de alto nivel), función computable, conjunto decidible y enumerable, función universal adecuada, problema de decisión y la técnica de reducción para transferir propiedades de decidibilidad y enumerabilidad. Se presentan e ilustran los resultados esenciales, a saber, el teorema de Rice, el teorema de Rice-Shapiro, el teorema de Rice-Shapiro-McNaughton-Myhill, así como el teorema de Rogers y el teorema de recursión. Se investigan la reducibilidad de muchos a uno y los grados de muchos a uno. También se incluye una breve introducción al cálculo con oráculos. Se introducen los operadores computables y no computables, así como los operadores monotónicos y finitarios. Se discute la relación entre ellos, en particular a través del Teorema de Myhill-Shepherdson. También se presenta el Teorema del punto fijo mínimo de Kleene. Por último, la Parte I termina con un breve resumen sobre el modelo computacional de Turing, la reducibilidad de Turing y los grados de Turing.

La parte II del libro se centra en las aplicaciones de la computabilidad en varias áreas, concretamente en lógica (indecidibilidad de la aritmética, satisfacibilidad en lógica proposicional, decidibilidad en lógica modal), geometría euclidiana, grafos y complejidad de Kolmogorov. No obstante, no se requieren conocimientos previos de estas materias. Se proporcionan los detalles esenciales para comprender las aplicaciones.