This book serves both as a completely self-contained introduction and as an exposition of new results in the field of recursive function theory and its application to formal systems.