71. The notion of self-reference refers to

a. poems, but not programs
b. programs, but not poems
c. both poems and programs
d. neither poems nor programs




















72. The "black box" definition of a program is so-called because

a. we don't care what type of computer it runs on
b. we don't care what happens inside a program
c. we don't care if a program runs forever or halts
d. we don't care what type of input is provided to a program




















73. We provide two versions of "clear box" definitions of programs because

a. one is more optimistic than the other
b. there may be programs written in Web-based programming languages that cannot be simulated by TMs
c. the TM is a minimal device containing the full functionality of computers
d. the equivalence of compatibility and TM-compatibility is a thesis, not a proven theorem




















74. Which definition includes more objects?

a. the black box definition of program
b. the clear box definition of program
c. neither the black box nor the clear box - they both include all possible programs
d.




















75. One important use for encoding TMs as binary strings is that doing so

a. allows TMs to process binary input data
b. allows us to count the number of possible TMs
c. allows us to put TMs in numerical order
d. allows TMs to accept other TMs as input




















76. The Halting Problem is

a. proven to be unsolvable
b. currently unsolved, but under intensive research
c. irrelevant to the modern practice of programming
d. the problem of "infinite loops" in programs




















77. In a proof by contradiction, we

a. find counter-examples to what we want to prove
b. use the opposite of what we want to prove to derive a contradiction
c. use what we want to prove to find counter-examples
d. use diagonalization




















78. Which of the following is NOT an example of an undecidable problem?

a. the Halting Problem
b. determining prime factorizations for large numbers
c. solving diophantine equations
d. tiling problems




















79. Undecidable problems of today may become decidable in the future thanks to advances in computer technology.

a. True
b. False
c.
d.




















80. When we think of computers in an abstract mathematical sense, they can hardly do anything at all.

a. True
b. False
c.
d.




















 
Congratulations: you've reached the end of the quiz. Return to the list of quizzes to take another chapter quiz, or to reset your score and start over.

If you'd like more information on The Theory of Computation, see the Resources for this Module.