CS 464/664 Assignment 1

Winter 2002

Due: Monday, January 28, 2002 (in class)

1. 1.4.15
2. Construct a Turing machine to divide nonnegative integers by 2 (note: 4/2 =2, 5/2=2) if
   • the input is in decimal (base-10)
   • the input is in binary (base-2)
   • the input is in unary (base-1)
   Be sure you give reasonable TIME bounds on your TM's.
3. 2.8.8
4. 2.8.17
5. 3.4.1 (a), (c), (e), (f), (g)
6. 3.4.3
7. 3.4.8
8. (Bonus for 464, Required for 664) 2.8.4