This is Quiz #3 from CPSC 100: Principles of Computer Science, Fall 1995. The answers given would receive full credit, but in many cases, there are variations or even completely different answers that would also receive full credit. The "Notes" are meant to clarify the answer or to provide some interesting extra information.
Question 1: Explain what is meant by computational universality.
Answer: Computational universality refers to the fact that, ignoring limitations of time and memory, all computers are equivalent in the problems they can solve.
Question 2: No real computer is truly computationally universal. Why not? What's the "catch"?
Answer: For real computers, it is not possible to ignore limitations of time and memory. For any given real computer, there will be some problems that it cannot solve because it simply does not have enough memory, even though there are other computers that can solve the problems. Furthermore, getting a much faster computer will make it practical to solve problems that your old computer would have taken longer to solve than you were willing to wait.
Note: It is not correct to quote the unsolvability of the Halting Problem as a "catch". Computational universality says that all computers (given time and memory) can solve the same problems. The Halting Problem cannot be solved by any computer. This doesn't challenge the fact that computers are equivalent as to the problems they can solve.
Question 3: One way for one computer to simulate another is to run an interpreter program. Explain briefly how an interpreter program works.
Answer: An interpreter program takes a program that was written for a different computer (or perhaps in a high-level language). It reads that program one instruction at a time, figures out what the instruction means, does whatever is necessary to carry out the instruction, and then goes back for the next instruction. This is something like a fetch-and-execute cycle, so that the interpreter is imitating the fetch-and-execute cycle of the computer that it is simulating.
Note: It might take the interpreter many steps to simulate the execution of a single instruction. For example, the instruction might be to multiply two numbers. Since the xComputer has no multiply instruction in its machine language, an interpreter running on the xComputer will have to execute a complicated subroutine just to simulate that one multiply instruction.
Question 4: Explain what is meant by the Halting Problem and what it means to say that the Halting Problem is "unsolvable."
Answer: The Halting Problem is to determine in advance whether a given program will ever halt when it is run with some given input data. This problem is unsolvable in the sense that there is no computer program that can correctly answer this question in all cases.
Question 5: What is the point of talking about the Halting Problem? What is its philosophical significance? What is its practical significance?
Answer: The unsolvability of the Halting Problem shows that there are things computers can never do. It also implies that computation can be surprising and unpredictable.
Note: Some people said that the unsolvability of the Halting Problem contradicts the Church-Turing thesis. But the Church-Turing thesis is the claim that any computation can be done by a computer. If solving the Halting Problem cannot be done by computation, then the Church-Turing thesis makes no claim at all about it.
[by David Eck]