# Non-polynomial Turing Machine

• Dec 12th 2010, 01:04 AM
skamoni
Non-polynomial Turing Machine
Hi, can anyone help with the following?

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))$

This the first time I have been asked to show a language is not in some class, and I'm quite stumped.