A MATHEMATICAL PRIMER ON COMPUTABILITY

A MATHEMATICAL PRIMER ON COMPUTABILITY

978-1-84890-296-1 / 9781848902961
The book provides a self-contained introduction to computability theory for advanced undergraduate or early graduate students of mathematics and computer science. The technical material is illustrated with plenty of examples, problems with fully worked solutions as well as a range of proposed exercises.Part I is centered around fundamental computability notions and results, starting with the pillar concepts of computational model (an abstract high-level programming language), computable function, decidable and listable set, proper universal function, decision problem and the reduction technique for transferring decidability and listability properties. The essential results namely Rice's Theorem, Rice-Shapiro's Theorem, Rice-Shapiro-McNaughton-Myhill's Theorem as well as Rogers' Theorem and the Recursion Theorem are presented and illustrated. Many-to-one reducibility and many-to-one degrees are investigated. A short introduction to computation with oracles is also included. Co
  • Envío en 3 días

 Aviso legal - Política Privacidad - Política de cookies - Condiciones generales de compra - Desistimiento
© 2024 Todos los derechos reservados.