CS4123 Theory of Computation. A99
Homework 2
Homework 2
Due on Tuesday, Sept. 21, 1999 at 5:00 p.m.
You can either turn in your homework in class or bring it to my office
FL232 before 5 p.m. (If I'm not in, please slip your homework under my door).
Problems:
 Exercise 4.1 from the textbook.
 Exercise 4.3 from the textbook.
 Exercise 4.4 from the textbook.
 Problem 4.11 from the textbook.
 Exercise 5.1 from the textbook.

Let Sigma be an alphabet. Show that
INFINITE_TM = { < M >  M is a Turing machine and M accepts infinitely many words}
is undecidable.
Hint Show that A_TM <=m INFINITE_TM.
Additional Problems for students taking this course for graduate
credit:
 Problem 4.17 from the textbook.
 Problem 4.22 from the textbook.
 Problem 5.9 from the textbook.