Descripción
El libro ofrece una introducción autónoma a la teoría de la computabilidad para estudiantes de último año de grado o de primer año de posgrado de matemáticas y ciencias de la computación. El material técnico se ilustra con numerosos ejemplos, problemas con soluciones completamente desarrolladas, así como una variedad de ejercicios propuestos.
La Parte I se centra en las nociones y resultados fundamentales de la computabilidad, comenzando con los conceptos pilares de modelo computacional (un lenguaje de programación abstracto de alto nivel), función computable, conjunto decidible y listable, función universal propia, problema de decisión y la técnica de reducción para transferir propiedades de decidibilidad y 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 Recursión. Se investiga 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 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. Finalmente, la Parte I concluye con una breve descripción del 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, grafos y complejidad de Kolmogorov. Sin embargo, no se requiere conocimiento previo de estos temas. Se proporcionan los detalles esenciales para comprender las aplicaciones.
Autor: Amilcar Sernadas, Cristina Sernadas, João Rasga
Editorial: College Publications
Publicado: 11/07/2018
Páginas: 280
Tipo de encuadernación: Tapa blanda
Peso: 0.87 lbs
Tamaño: 9.21h x 6.14w x 0.59d
ISBN13: 9781848902961
ISBN10: 1848902964
Categorías BISAC:
- Informática | Ciencias de la Computación
- Matemáticas | Lógica
Este título no es retornable