For each problem, is it decidable? If so$,$ how? if not, why not?

a$.$ Given a Turing machine $M$ and a string w$,$ does $M$ accept w within $100,000$ steps?

b$.$ Given a Turing machine $M$ and a string $w,$ does $M$ accept w$?$

c$.$ Given an Nondeterministic Finite Automaton M and a string w$,$ does M accept w$?$

d$.$ Given a CFG G$,$ does G generate some string of length $5?$

Answer the following briefly but completely.

e$.$ Define the problem HALTTM.

f$.$ Church$-$Turing Thesis

Draw a diagram showing the Chomsky Hierarchy of Languages $($Venn diagram, showing which

sets are

subsets of other sets$).$ Include at least $4$ sets in your diagram.