The complexity T(M,w) of a TM M and a string w is defined as the number of steps needed for M(w) to halt. If M(w) does not halt, then T(M,w) is set to infinity.

1. Suppose you are given a DTM M = <Q,...> and a finite integer k. Define the language L = { w : T(M,w) <= k} = { w : M accepts w within k steps }.
Construct another TM M' to decide L.

2. Draw a DFA to accept { w : w has even number of 0s} over {0,1}. Write down a string representation of D's description, denoted <D>. 

3. Write a pseudocode that takes as input a description of a DFA <D> and some string x and returns True iff D accepts x. Now try to design a TM that decides the language { <D>#w : D is a DFA that accepts w}.
Hint: Describe the TM at "pseudocode" level; it may be too tedious to draw its state diagram.

4. Consider the language L = { <D>#w : where <D> is the 5-tuple encoding of a DFA over {0,1} and w is a binary string and D accepts some z of which w is a substring}. The alphabet of L is ASCII. Show that L is decidable.
Hint: Use non-determinism.