Chapter 9 --- Little Quiz                                                        

For each problem except Problem 3, select an incorrect item.

1. (a) All nontrivial problems about the language accepted by the TM are undecidable.(b) A language is recursive enumerable if there exists a TM to accept it.(c) A recursive enumerable language is a decidable language.(d) A language is recursive if there exists a TM which accepts it and always halts for all input strings.

2.(a) All TM’s may be represented by binary strings.(b) Each binary string may be used to represent a TM.(c) The diagonalization language L_d consists of all binary strings w such that the TM represented by w does not accept the input w.(d) There exists a TM which can accept the diagonalization language L_d.

3. Which of the following about a language L is not equivalent to the others? (a) Language L is not recursively enumerable.(b) No TM accepts language L.(c) Language L is recursive.(d) The languages of all TM’s are not L.

4. (a) A TM which accepts a recursive language corresponds to an algorithm.(b) A given language, when regarded as a problem, is called decidable if it is a recursive language.(c) The recursive language is closed under complementation.(d) The universal language L_u is recursive.

5. (a) If a language and its complement are recursively enumerable, then both of them are recursive.(b) The TM which accepts the universal language is a universal machine.(c) There exists no language which cannot be accepted by a TM.(d) The universal language is recursively enumerable.