April 11, 2006

**Printed Name:**________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

**Signature:**___________________________________________

- (2 points)
Assume a specific encoding scheme for representing Turing machines
as binary strings.
The number of different Turing machines is (circle one):

finite, countably infinite, uncountably infinite.

- (2 points)
Define the language L_d.

- (1 point)
*True or False:*L_d is recursively enumerable.