CPSC 433: Quiz 10
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."


  1. (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. (2 points) Define the language L_d.

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