Download Computability, Unsolvability, Randomness pdf by Stephen G. Simpson, I exposit Turing's 1936 theory of computability and unsolvability, as later on developed by Kleene and Post. This theory is of the essence within theoretical computer science and in the study of unsolvable mathematical problems. Second, I provide an introductory account of a research area which is presently very active: algorithmic randomness and Kolmogorov complexity. Download the pdf from below to explore all topics and start learning.


1 Computability
2 Partial recursive functions
3 Unsolvability
4 The arithmetical hierarchy
5 Oracles and relativization
6 Kolmogorov complexity
7 The Cantor space
8 Randomness
9 Some advanced topics
10 Solutions to all of the exercises