Computability, Unsolvability, Randomness

Computability, Unsolvability, Randomness

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/

February 5, 2009

Please send corrections to the author at simpson@math.psu.edu .

1

Preface

This book originated as a set of lecture notes for a junior-senior-level course which I taught at the Pennsylvania State University in Fall Semester (August 27 through December 14), 2007. The note-taker was my teaching assistant in the course, Jonas Kibelbek, a Mathematics Ph.D. student at Penn State. The students in the course were outstanding undergraduate mathematics majors from colleges and universities around the United States. These students were partipating in our Mathematics Advanced Study Semester program, also known as MASS. The MASS program is sponsored by the United States National Science Foundation. The purpose of my Fall 2007 course and of this book is twofold. First, 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.

2

Contents

Title Preface 1 Computability 1.1 Computable functions . . . . . . 1.2 Composing computable functions 1.3 Computable predicates . . . . . . 1.4 Primitive recursion . . . . . . . . 1.5 Prime power coding . . . . . . . 1.6 Computable real numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....