# Non-polynomial Turing Machine

Given the Language $L\ = \{\sigma1^{3k}}\in \{0,1\}^* \mid \sigma\ codes\ a\ Turing\ Machine\ M\ which\ on\ insert\ \sigma1^{3k}}\ halts\ within\ at\ most\ 2^k\ steps\ without\ accepting\ \}$
Show that $L \notin P$ and find a function $T(n)$ such that $L \in Time(T(n))$