This page contains questions and answers for the first test in CS100: Principles of Computer Science, a course based on the book The Most Comples Machine. The answers given here are sample answers only. There is always some variation in the answers that would receive full credit. The Notes contain any extra comments I happen to have; they are not parts of the answers.
Question 1: Define each of the following terms as they relate to this course
(a) fetch-and-execute cycle
Answer: The fetch-and-execute cycle is how a computer executes a machine language program: it copies one machine language instruction from memory into the CPU and then carries out that instruction, and it repeats this cycle over and over.
(b) computational universality
Answer: Computational univerality refers to the fact that, ignoring limitations of time and memory, all computers are equivalent in the sense that any problem that can be solved by one computer can be solved by any other. [Note: This is not the same as the Church-Turing thesis, which says that any "computation" can be done by computers. Computational universality is a provable fact, but the Church-Turing thesis might still be false if it turns out that there are computations that cannot be done by any computer. This is regarded as unlikely, but it is not something that has been proved or disproved.]
(c) control circuit
Answer: The control circuit is the part of the CPU that directs the overall operation of the computer. It does this by turning control wires on and off in the right sequence to carry out the steps of the fetch-and-execute cycle.
(d) CPU
Answer: The CPU, or Central Processing Unit, is the active part of the computer that actually executes the machine language instructions in a program.
Question 2: Explain what is meant by structured complexity and why it is important. Give some examples of structured complexity that you have seen in this course.
Answer: Structured complexity refers to the fact that complex systems can be built up in relatively easy stages. Simple components can be "chunked" together into somewhat complex structures that then can be used as building blocks in even more complex structures and so forth, for as many levels of structure as needed. This is important because it would be impossible to deal with things as complex as computers and computer programs if they had to be understood all at once in complete detail. Computers are built from transistors, but there are many levels of structure between transistors and computers. Transistors are chunked into gates, which are used to produce simple circuits such as half-adders and one-bit memories, which can then be combined into more complex circuits such as multi-bit adders and multi-bit memories, and so forth. Similarly, programs are built from very simple instructions using structuring devices such as loops, decisions, and subroutines.
Note: No one will ever get full credit in one of my courses for any question about structured complexity unless they show some understanding of the idea of levels of structure.
Question 3: A logic circuit is needed to perform a certain task. It will have three input wires; call them A, B, and S. It will have one output wire. If S is ON, then the output must be the same as the first input A. If S is OFF, then the output must be the same as the second input B.
(a) Write a Boolean algebra expression that describes the output in terms of the inputs A, B, and S. (You can figure this out by "thinking logically" about the condition for the output to be ON, or you can procede mechanically by first creating an input/output table.)
Answer: The output of the circuit should be ON if either (A is ON and S is also ON) or (B is ON and S is OFF). This condition can be expressed in Boolean algebra as: (A and S) or (B and (not S)).
(b) Draw the circuit, using the Boolean expression from part (a) as a blueprint. (You can get partial credit for this even if your expression is wrong, so don't skip this even if you can't do part (a).)
Answer:
Note: To do this problem "mechanically", you can make an input/output table that follows the description of the circuit. There are 8 possible combinations of inputs. Where S is ON, the OUTPUT should be the same as A; where S is OFF, the output should be the same as B. Here is the table:
A B S | OUTPUT
------------------|---------
OFF OFF OFF | OFF
ON OFF OFF | OFF
OFF ON OFF | ON
ON ON OFF | ON
OFF OFF ON | OFF
ON OFF ON | ON
OFF ON ON | OFF
ON ON ON | ON
A formula for the output can be read off from this table, as described in the text:
((not A) and B and (not S)) or (A and B and (not S)) or
(A and (not B) and S) or (A and B and S)
This leads to a very complicated circuit, but at least this method has the advantage that if you follow the procedure correctly, you know that the answer has to be right. By the way, if you think about it, you will see that the first line of the above formula is eqivalent to (B and (not S)) while the second is equivalent is equivalent to (A and S).
Question 4: Find the Boolean albegra expression that describes the putput of the following circuit in terms of the inputs A, B, and C.
Answer: (not (A and B)) and (B or C)
Question 5: What role does the clock play in a computer
Answer: The clock is the compontent of the computer that makes everything happen. As the clock "ticks," it turns an output wire on and off. Each time the wire comes on, the COUNT register is incremented by one, and the next step in the fetch-and-execute cycle is performed.
Note: Changing the number in the COUNT register changes the inputs to the Control Circuit. When this happens, its outputs will also change so that certain control wires will be turned on and others will be turned off. This in turn causes whatever action is necessary for the next step of the fetch-and-execute cycle.
Question 6: Consider the Turing machine defined by the following rule table:
Current Current | New
State Symbol Write | Move State
------------------------------|------------------
0 # # | R 0
0 0 0 | R 0
0 1 1 | R 0
0 x x | R 0
0 y y | R 0
0 z z | R 0
0 $ $ | R 1
1 # # | R 1
1 0 # | R 1
1 1 # | R 1
1 x # | R 1
1 y # | R 1
1 z # | R 1
1 $ $ | L h
(a) Suppose that this machine is started in state 0 on the following tape, on the square that contains a z. Show exactly what the tape will look like after the tape halts, and indicate where the machine will be after it has halted.
----------------------------------------------------------------
| | | | | | | | | | | | | | |
. . . | | z | | 1 | $ | | 1 | 0 | y | 1 | $ | x | | | . . .
| | | | | | | | | | | | | | |
----------------------------------------------------------------
Answer:
Machine halts here ___
|
v
----------------------------------------------------------------
| | | | | | | | | | | | | | |
. . . | | z | | 1 | $ | | | | | | $ | x | | | . . .
| | | | | | | | | | | | | | |
----------------------------------------------------------------
(b) Explain in words exactly what this machine will accomplish when it is started on any tape. Don't try to list the individual steps in the computation. What does the computation accomplish?
Answer: This machine seems to be designed to erase a segment of tape between two $'s. It searches to the right for a dollar sign and then erases eveything between that dollar sign and the next dollar sign to the right. (If it is started on a tape that has only one $ to the right, it will run forever.)
Note: Part (b) of this question was about "this machine", that is, THIS PARTICULAR MACHINE, not about Turing machines in general.
Question 7: We have talked a lot about how the fetch-and-execute cycle is executed in xComputer. The whole point of this cycle is to execute a program stored in main memory. Explain as clearly and exactly as possible how it is that program instructions stored in memory can control the computations of the CPU.
Answer: The simple answer is that each instruction is copied into the CPU to be executed. Specifically, the instruction is placed into the IR (Instruction Register). From there, the instruction can "control" the CPU since the IR provides some of the inputs to the Control circuit, which uses these inputs to determine what needs to be done to execute the instruction.
Question 8 (a): State the Halting Problem.
Answer: The problem can be stated as: Write a program that can correctly predict, in all possible cases, whether or not a given program will ever halt when it is run with given data as input.
Note: Many people answered part (b) instead of part (a). The point of separating (a) and (b) was to make sure that you understood that the Halting Problem is a "challenge" to write a program to write a program that performs a specific task. To say that the Halting Problem is unsolvable is to say that it is impossible ever to meet this challenge.
(b): What does it mean to say that the Halting Problem is unsolvable?
Answer: There is no single program that can make a correct prdiction in all cases.
(c): What is the significance of the fact that the Halting Problem and other similar problems are unsolvable?
Answer: The existance of unsolable problems tells us that there are very natural questions about computation that can't be answered by computers. More specifically, we can see that computation is in some sense "irreducible". The only completely general way to find out what a program will do is to run it and see.
Question 9: One of the exercises on Lab 0 asked you to "Make a file--not just a window!--" with certain specified contents. What is the essential difference between a file and a window?
Answer: The essential difference is that a file is permanent. That is, a file is a collection of information that has been stored in the computer's permanent memory (such as on the computer's hard disk). It can be re-opened later and will stay around until someone explicitly throws it away. On the other hand, the contents of a window are temporary. They will disappear when you close the window, unless you have saved them into a file.
Note: It might be that a window shows the same information that is in some file, but it is only a copy. When you change the contents of a window, you don't automatically change the file; you have to explicitely save the changes. A window can be a way of viewing the contents of a file.
Question 10: A computer consisting of a CPU and main memory has no moving parts, so what does it mean to say that it is a "machine" and that it operates "mechanically"?
Answer: The word "mechanically" is used here to mean following definite, unambiguous rules, without thought and without understanding of any sort of meaning that might be perceived by a human observer. A computer--like a clock or a car or a pulley or any machine with "moving parts"--operates without thought or choice, simply because of the way it is physically put together.