This page contains questions and answers for the third quiz 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.
Question 1: An "interpretor" is a certain type of computer program. Give a rief outline of the way in which an interpretor program operates.
Answer: An interpretor can be thought of as a way of simulating the operation of a computer by imitating the fetch-and-execute cycle of that comptuer's CPU. More specifically, an interpretor program runs in a loop that gets one instruction at a time from a program, does whatever is necessary to carry out that instruction, and then goes back for the next instruction.
Question 2: Explain the differences between an interpretor and a translator.
Answer: When a translator program is run, it takes a program written in some language (the machine language for a computer, for example), and writes a new program equivalent to the first, but in a different language (such as the machine language for another computer). The translator does not actually execute the program; it produces a new program that can be run on its own.
An interpretor, on the other hand, takes a program and executes it directly. You can think of it as reading the program instruction by instruction and translating as it goes, but it does not save the tranlation and so, for example, to repeat a loop over and over it has to translate it over and over.
Note: To sumarize: A translator translates the program all at once ond one time only. An interpretor interpretes it instruction by instruction every time it is run.
Question 3: What is the Church-Turing Thesis?
Answer: The Church-Turing Thesis is the claim that anything that can reasonably be called computation can be done by a computer. (This is not something that can be definitively proved, because it depends on what exactly can be "reasonably" be called computation.)
Note: Another version of this thesis claims that any procedure that can be specified by an unambiguous set of rules can be carried out on a computer.
Question 4: What is the Halting Problem?
Answer: The Halting Problem is to take any given program and input data for that program and to say, correctly and in advance, whether or not that program will ever halt when it is run with that data as input.
Note: You could also say that the problem is to write o program that will answer this question. If you believe the Church-Turing Thesis, this is equivalent to asking for an unambigulus set of rules that will answer the question correctly in all cases.
Question 5: The Halting Problem is unsolvable--at least by computers. What are some of the philosophical and practical implications of this fact?
Answer: There are limitations to what computers can do. There are very natural questions, such as the halting problem, that computers cannot answer. Some of these questions are very practical: It would be very useful to know in advance how long a program will run, or to be sure that it will give the right answer. However, we can't in general even be sure whether the program will halt at all! (Of course, we can always try to write specific programs for which we can be sure; the unsolvability of the Halting Problem only says that you can't be sure in all possible cases.)