CPSC 120, Spring 2002
Second Test, March 20
This is the second test from CPSC 120:
Principles of Computer Science, Spring 2002.
The answers given here are sample answers only.
Question 1: What are device drivers, and why are they important?
Answer: "Devices" are hardware components such as keyboards, disk drives, and network cards that can be added to a computer system. A device driver is the software that the CPU needs to communicate with and control a particular device. Without a device driver, there is no way for the device to be used. Generally, a device driver contains interrupt handlers, which the CPU runs to respond to signals from the device, and subroutines that the CPU can call when it wants to send signals to the device.
Question 2: What are parameters, and why are they important? Give an example.
Answer: A parameter is a value that is passed to a subroutine, so that the subroutine can use the value in its computations. For example, the "10" in "forward(10)" is a parameter. It tells the "forward" how far the turtle should move. Parameters make it possible to customize subroutines. The same subroutine can have different effects, depending on the value of the parameter. We can have forward(10), forward(-3), and even forward(x) where x is a variable. Without parameters, subroutines would be much less useful.
Question 3: Write xTurtle commands that will draw the following picture. Assume that the line at the top is 10 units long.
Answer: Here are two solutions. The one on the left assumes that the turtle starts at the top left of the picture. The one on the right assumes that it starts at the bottom.
forward(10) turn(90)
turn(-90) forward(5)
forward(5) turn(-90)
turn(-90) forward(5)
forward(5) turn(90)
turn(90) forward(5)
forward(5) turn(90)
forward(10)
Question 4: Draw the picture that is produced by the following xTurtle program:
DECLARE x
x := 1
LOOP
forward(1)
EXIT IF x = 6
turn(90)
forward(x)
back(2*x)
forward(x)
turn(-90)
x := x + 1
END LOOP
Answer: The line "forward(1)" draws a horizontal line of length 1. The lines "turn(90) forward(x) back(2*x) forward(x)" draw a vertical line of length x, centered on the current turtle position. After drawing the line, the turtle is back where it started from, so the next horizontal line segment that it draws will line up with the first one. Since x increases by one each time through the loop, the vertical lines get longer as the program proceeds. The program ends just after drawing a horizontal line if x is 6. Six horizontal lines have been drawn, but only five vertical lines (since the loop ends just before it would have drawn the sixth vertical line).
Question 5: Consider the Turing machine that is described by the following set of rules:
Current | Current Cell | New Cell | Direction | New
State | Contents | Contents | of Motion | State
-----------+--------------+----------+-----------+----------
0 | # | # | R | h
0 | x | y | R | 1
1 | # | # | L | 2
1 | x | x | R | 1
2 | x | # | L | 3
2 | y | # | R | h
3 | x | x | L | 3
3 | y | x | R | 0
a) Suppose this machine is started (in state 0) on an empty tape. What does it do?
b) Suppose this machine is started (in state 0) on a tape that contains a single x. The machine is started on the cell containing the x. What is on the tape when the machine halts?
c) Suppose this machine is started (in state 0) on a tape that contains a string of two x's. The machine is started on the cell containing the leftmost x. What is on the tape when the machine halts?
d) Suppose this machine is started (in state 0) on a tape that contains a string of any number of x's. The machine is started on the cell containing the leftmost x. Describe the contents of the tape when the machine halts, in terms of the number of x's that were on the tape when it started.
Answer: a) The Turing machine starts in state 0. Since the cell it is on is blank (#), it follows the first rule in the table. That is, it leaves the blank in place, moves to the right, and halts immediately.
b) The tape will be blank. (The TM changes the x to a y, moves right, and changes to state 1. In state 1, it sees a blank, so it moves left and goes into state 2. This moves it back to the cell that contains the y. Since it's in state 2 and sees a y, it replaces the y with a blank, moves right, and halts. The original x was changed to a y and then was erased, leaving the tape blank.)
c) There will be one x on the tape.
d) The tape will contain a string of x's that contains half as many x's as the original string. If the original number of x's is odd, the answer is rounded down to the nearest integer. For example, if there are 5 x's originally, then there will be 2 x's when the TM halts. (This happens because the TM "marks" an x by changing it into a y, then erases an x from the right end of the string, then changes the y back to x and moves on to the next x in the string. So, it erases one out of every two x's. If the original number is odd, there won't be any x corresponding to the final y. The TM erases this y, rather than changing it to an x, before halting.)
Question 6: The first working computers were developed during World War II. Why were these computers built? What motivated people to work on them, and how where they used?
Answer: There were two main motivations for working on computers as part of the war effort. In England, the Colossus computer was developed to help decode secret German communications. In the United States, the ENIAC was developed to compute firing tables for artillery guns (but it wasn't actually used for this during the war because it was finished too late). In both cases, people wanted to automate computations that took "human computers" too long to do.
Question 7: When discussing the social impact of computers, one major area of concern is "privacy issues." Why is this a concern? What are some specific ways in which computers affect people's privacy? Do you think this is a serious problem?
Answer: Computer databases are used to store large amounts of data about individuals. People generate this data almost inevitably as they go about their daily lives: by using credit cards, browsing the Internet, getting a driver's license, applying for loans, taking books out of a library, and even buying groceries with a shopper's card. There are some legal limits on what can be done with this information, but they are not very strong -- and there are also problems with people accessing the data illegally and with errors in the data. In general, laws for protecting privacy should probably be made stronger.
Question 8: The Halting Problem is the most famous example of an "unsolvable problem" in computer science. What is the Halting Problem? What does it mean to say that it is unsolvable? What are the philosophical implications?
Answer: One of the most basic questions about a computer program is: If this program is run, will it ever halt? Trying to answer that question without actually running the program is the Halting Problem. (Running it won't work anyway, because there is no way to know how long to wait before concluding that it's not going to halt.) This problem can be proved to be unsolvable in the following sense. It is impossible to write a program that answer this question in all cases. (Note that this does not automatically imply that people will be unable to answer the question in all cases -- although it does seem to mean that it is impossible to come up with a set of rules that can be used to answer the question. Note also that it is possible to answer the question for many particular programs. The only thing that is proven to be impossible is to find a program that can answer the question for all programs.) Philosophically, we can look at this result in two ways: It seems to show that there are things that computers can never do, so the power of computation is limited. On the other hand, it shows that computing is complex because there are simple questions about computing that can't be answered.
Question 9: Computers and Turing machines are examples of "universal" machines. Discuss this statement. What does it mean? What is the evidence for it? Why is it important? How does this compare with other types of machines?
Answer: Most machines are built to serve a single purpose. A car car can be used for driving, but it can't fly. A clock tells time, but it can't be used to cook a hot dog. Computers are different because they are programmable. The same computer can be used for different things, depending on what program it is running. With one program, it can decode secret messages. With another, it might compute firing tables for guns. With others, it can be used to write an essay or play a game of chess, or compose music. So, a computer can do many things. One of the most amazing thing about computers is that they can all do exactly the same things -- at least if we ignore differences in speed, memory, and user interface. This is what we mean by computational universality: Except for differences in speed and memory, all computers are equivalent in their computational power. The set of problems that can be solved by one computer is the same -- given enough time and memory -- as the set that can be solved by any other computer. So, if you want to understand "computation", it's enough to look at one model of computation. Even a very simple form of computation, such as Turing Machines, can be powerful enough to be computationally universal. Turing Machines are often used in the theoretical study of computation because they are simple, and yet they have as much computational power as much more complex machines. The question arises why we should believe in computational universality. One form of evidence is provided by simulation. It's possible to program one machine to imitate another. This shows that the first machine can do anything that the second one can do, and so it is at least as powerful. The real reason this works is that all computing machines are built up, ultimately, from simple parts. Since the parts are simple, you don't really need a lot of computational power to simulate them.