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]