Una introducción matemática a la computabilidad

El libro proporciona una introducción independiente a la teoría de la computabilidad para estudiantes universitarios avanzados o estudiantes de posgrado iniciales en matemáticas e informática. El material técnico está ilustrado con numerosos ejemplos, problemas con soluciones totalmente resueltas y una serie de ejercicios propuestos. La Parte I se centra en nociones y resultados fundamentales de computabilidad, comenzando con los conceptos fundamentales de modelo computacional (un lenguaje de programación abstracto de alto nivel), función computable, conjunto decidible y listable, función universal adecuada, problema de decisión y la técnica de reducción para transferir la decidibilidad. y propiedades de listabilidad. 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 la 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 a la computación con oráculos. Se introducen operadores computables y no computables, así como operadores monótonos y finitos. Se analiza la relación entre ellos, en particular a través del teorema de Myhill-Shepherdson. También se presenta el teorema del mínimo punto fijo de Kleene. Finalmente, la Parte I termina con una sesión informativa sobre el modelo computacional de Turing, la reducibilidad de Turing y los grados de Turing. La parte II del libro se concentra en las aplicaciones de la computabilidad en varias áreas, a saber, en lógica (indecidibilidad de la aritmética, satisfacibilidad en lógica proposicional, decidibilidad en lógica modal), geometría euclidiana, gráficos y complejidad de Kolmogorov. Sin embargo no se requieren conocimientos previos sobre estas materias. Se proporcionan los detalles esenciales para comprender las aplicaciones.

• | Autor: Amílcar Sernadas, Cristina Sernadas, Joao Rasga
• | Editorial: Publicaciones universitarias
• | Fecha de publicación: 07 de noviembre de 2018
• | Número de páginas: 280 páginas
• | Idioma: inglés
• | Encuadernación: Tapa blanda
• | ISBN-10: 1848902964
• | ISBN-13: 9781848902961