Introduction to Computing: Explorations in Language, Logic, and Machines

This book is a survey introduction to the most important ideas in computing. It focuses on the big ideas in computer science including the major themes of recursive definitions (we can define things in terms of smaller versions of themselves), universality (programs are just another kind of data), and abstraction (hiding unnecessary details and giving things names). It covers how to describe information processes by defining procedures, how to analyze the costs required to carry out a procedure, and the fundamental limits of what can and cannot be computed mechanically.