Chapter 8 --- Little Quiz                                                        

For each problem, select an incorrect item.

1. (a)An undecidable problem means that there exists no algorithm to solve it.(b) All computations done by a computer may be done by a TM.(c) We may reduce an undecidable problem P1 to a new problem P2, so that we may prove P2 decidable.(d) Church-Turing hypothesis says any general way to compute will allow us to compute only the partial-recursive functions.

2.(a) The TM may be regarded as a finite automaton with a 2-way infinite tape.(b) The TM is deterministic in nature.(c) Blanks may be used as input symbols for a TM.(d) The head of the finite control of the TM may read and write symbols.

3. (a) The language accepted by the TM is the recursive enumerable language.(b) A TM halts if its transition function is undefined.(c) Recursive enumerable languages are defined by TM’s that halt eventually.(d) TM’s that always halt are a good model of an algorithm.

4. (a) The TM may be used for computing functions without entering final states.(b) All maximal computational models compute the same functions or recognize the same languages.(c) In each move, a TM may write more than one symbol onto the tape.(d) K. Gödel published his incompleteness theorem saying that some formula in predicate calculus can neither be proved nor disproved.

5. (a) The problem reduction technique can be used to prove a problem undecidable based on another undecidable problem.(b) The undecidability of a problem tells a programmer not to try to write a program for the problem.(c) All problems can be solved by modern-day powerful computers.(d) The TM is the most powerful computing device, though seeming very simple.