1. Consider a language L0 that is enumerated by a Turing Machine T M0. Is it possible to create a Turing Machine T M ′
0 that only accepts strings in L0, instead?
2. Consider a Turing Machine T Ms which simulates a k-tape Turing Machine T Mk. Show that
if T Mk has polynomial time complexity, so does its simulation. (
