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

In the past hundred years, computer science has changed the world more than any other field. Without computer science, humans would not have walked on the Moon, modern medicine would not exist, and Wal-Mart would be a small store in Arkansas. But this course is not just about the pragmatic impact of computer science; it is about how computer science changes the ways we think, solve problems and understand the world.

Despite its name, computer science has very little to do with the beige boxes we call computers, and it is far from being a science. It has more in common with music and mathematics than it does with science or engineering. At its core, computer science is the study of imperative knowledge. Whereas mathematics is all about declarative knowledge (“what is”), computer science is all about “how to” knowledge.

Computer science is the study of information processes. Computer scientists study how to describe, predict properties of, and efficiently implement information processes.

Most of what we know about describing information processes stems from three simple ideas:
1. You can define things in terms of themselves (recursive definitions).
2. You can treat procedures and data as one and the same (universality).
3. When you give something a name, it becomes more useful (abstraction).

Although these ideas are simple, they have profound implications that it takes many years to fully appreciate.

The kinds of properties we want to predict about information processes include whether or not there is a procedure that can always solve a given problem (computability), and how much time and space will be required to solve a given problem (complexity).