CPSC 100: Principles of Computer Science
Spring 1997
Week 4 Reading Guide

This is the fourth of the weekly reading guides for Computer Science 100.


Week 4 (April 21 to 25)

The reading for this week consists of the introduction and Section 1 of Chapter 4, plus Section 2 of Chapter 5. I will ask you to read the rest of Chapter 5 next week, but we will permanently skip the remainder of Chapter 4, except that I will briefly discuss the Halting Problem in lecture.

There is a test in class next Monday, April 28. It will cover Labs 1, 2, and 3, and it will cover the material we have done from the text through Section 4.1. It will not cover Section 5.2, even thought that is part of the reading for this week, and it will not cover Lab 4. Material from all of Chapter 5 and from Lab 4 will be on the next quiz, on May 5.

This week we look beyond the relatively simple model circuits and computers. We will look, actually, in two rather different directions. First, we consider "theoretical computers" and ask basic questions about the capabilities and limitations of computers. We begin with the somewhat surprising fact that in a theoretical sense -- ignoring limitations of time and memory -- all computers are equivalent. This is called computational universality. Computers are sometimes referred to as universal machines, meaning that any computer can be programmed to do anything that any other computer can do. (In practice, of course, there are real limitations imposed by the amount of memory available and the amount of time that you are willing to let the computer run.)

Computational universality is something that can be proved, but there is an even stronger statement that most people believe is true. This is the Church-Turing Thesis, named after Alonzo Church and Alan Turing, which is the claim that anything that can reasonably be called computation can be done by a computer. (This cannot actually be proved, because it depends to some extent on what people are willing to call computation.)

Having learned that computers are immensely powerful computational machines, it is wise to consider their limitations. It is possible to prove certain fundamental limitations on the power of computing devices. The most fundamental example of such limitations is the unsolvability of the halting problem. The halting problem is: given any program, determine in advance whether or not that program will eventually halt when it is run. This problem is unsolvable by computer. In other words, it is impossible to find a computer program that can answer the question in all possible cases.

In addition to looking at these theoretical issues this week, we will begin a discussion of how real computers work. A real computer consists of much more than just a CPU and main memory. Real computers have to do input/output with the rest of the world, including with the user. A computer system includes a large number of devices such as a keyboard, a monitor, disk drives, and network cards, that make this possible. A real computer system also includes an operating system, which is the basic software that is essential to make the computer operational. The operating system is the program that has overall control of the computer. It also includes device drivers, which are software used by the CPU to communicate with and control various devices.

Much of the coordination between the CPU and other devices uses interrupts. When a device needs the attention of the CPU, it signals an interrupt by turning on an interrupt wire connected to the CPU. This signal causes the CPU to put aside what it is doing and to go off and execute an interrupt handler, which is the software that handles the situation that caused the interrupt.

Section 4.1 Concept List (for the test):

Section 5.2 Concept List: