Computability Theory

Computability as a theory is a specifically twentieth-century development. It started with the fundamental work of Gödel, Turing and Kleene, among others, in the 1930’s. History of the subject is unusual, because the history (like the Universal Turing machine) preceded its physical embodiment by around ten years. The book presents a wide range of topics such as computably enumerable sets, the degree structures, subrecursive hierarchies, complexity of computations and also some recent work on computability of structures and algorithmic randomness. It provides an excellent introduction to contemporary computability theory. All substantial techniques and results are explained, historical and logical context is also given. The book includes both the standard material for a first course in computability and also more advanced material on forcing, priority methods, determinacy and algorithmic randomness.

Reviewer: 
akč
Book details
Author:  Publisher: 
Published: 
2003
ISBN: 
1-58488-237-9
Price: 
$69,95
Categorisation