Computability, Unsolvability, Randomness
by Stephen G. Simpson
Publisher: The Pennsylvania State University 2009
Number of pages: 151
Description:
I exposit Turing’s 1936 theory of computability and unsolvability, as subsequently developed by Kleene and Post. This theory is of the essence in theoretical computer science and in the study of unsolvable mathematical problems. Second, I provide an introductory account of a research area which is currently very active: algorithmic randomness and Kolmogorov complexity.
Download or read it online for free here:
Download link
(910KB, PDF)