Sample Midterm questions

(Cmps 132, Winter 07, Warmuth)

1. Given a TM. figure out what
language it accepts or function it computes.

2. Construct a TM for solving a simple problem.

3. Give the Church-Turing thesis.
Is your laptop equivalent to a TM?

4. Defs of universal and completeness.

5. What are the inputs to a universal TM?
What does it do?

6. Defs of T. acceptable and T. decidable.

7. Closure properties of T. a. and T. d.
languages (Thms 10.1 to 10.6) 	

8. Equivalence between T. a. and T. enumerable.

9. Equivalence between T. d. and T. enumerable in
lexicographic order

10. Diagonalization argument for showing
that for example the set of languages over
a finite alphabet is uncountably infinite.

11. Show that the countable union of
countable sets is countable.

12. Use a counting argument to show that
there are languages that are not T. a.

13. Def. of SA and NSA

14. Use the fact that NSA is not T.a.
to show that SA is not T.d.

15. Given an (unrestricted) grammar,
show what language it accepts.

16. Given a description of a language,
construct an unrestricted grammar that
generates it.

17. What is the relationship between
the languages generated by unrestricted
grammars and the T. a. languages?

18. Show that context sensitive languages
are decidable.

19. Know the definition of the Halting
Problem and the language H.
Know what it means that the Halting Problem
is undecidable.

20. Give a proof that the Halting Problem is
undecidable.

21. Be familiar with diagonalization arguments! 

22. Show that a problem is unsolvable by
reducing a known unsolvable problem to it.

23. Know the statement of Rice's theorem
and how to apply it