Portada

A MATHEMATICAL PRIMER ON COMPUTABILITY IBD

COLLEGE PUBLICATIONS
11 / 2018
9781848902961
Inglés

Sinopsis

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&rsquo,s Theorem, Rice-Shapiro&rsquo,s Theorem, Rice-Shapiro-McNaughton-Myhill&rsquo,s Theorem as well as Rogers&rsquo,á 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. Computable as well as non-computableáoperators are introduced as well as monotonicáand finitary operators. Theá relationship betweenáthem is discussed, in particular via Myhill-Shepherdson&rsquo,s Theorem. Kleene&rsquo,s Least FixedáPoint Theorem is also presented. Finally,áPart I terminates with a briefi ng on the Turingácomputational model, Turing reducibility andáTuring degrees.Part II of the book concentrates on applicationsáof computability in several areas namely in logicá(undecidability of arithmetic, satisfiability inápropositional logic, decidability in modal logic),áEuclidean geometry, graphs and Kolmogorovácomplexity. Nevertheless no previous knowledgeáof these subjects is required. The essential detailsáfor understanding the applications are provided.

PVP
23,51