I- E TM decidable? 15 pts
II- EQ TM decidable? 15 pts
III- E(NFA) decidable? 15 pts
IV-Write Turing machine: 30 pts
a) (001)+(011)+1*
b) (00)+(10)+0*
V-Prove that PATH is in P by analyzing its running time(write algorithm) 15 pts
VI-Profe that if HAMPATH is not in P, then TSP is not in P
Note: TSP = the shortest path that a salesman does, no city can be passed twice
10 pts
Good LUCK