# Proof that there is a recursive language that is not decidable in $O(n)$ time

I having some trouble tackling an assignment. We're asked to prove that there exists a recursive language that's not decidable by a Turing machine in $O(n)$ time for inputs of length $n$. We're supposed to do so using diagonalization.

Here's what I have so far:

Assume that for each recursive language $L$, there exists a TM that decides $L$ in $O(n)$ time for each input of length $n$.

We build a TM, $U$, that for each input, $w$, $U$ interprets $w$ as $w = 1^k0\langle M\rangle$, where $\langle M\rangle$ is an encoding of a TM for language recognition. It then runs $M$ on $w$, and if $M$ halts, then $U$ outputs the opposite of $M$'s output. Therefore,$U$ must perform at least $k$ steps in order to extract the encoding of $M$ from the input. I'm still not sure how to continue from here.

• Are you familiar with the time hierarchy theorem? – David Richerby Nov 22 '16 at 12:54
• @DavidRicherby R is the set of recursive languages. I'm not familiar with that theorem. – Caesar23 Nov 22 '16 at 12:57
• I suggest you have a look at it -- you're essentially being asked to prove a special case of it. – David Richerby Nov 22 '16 at 13:18
• I've read the proof in the link that you've provided. I have a few questions : 1. Do I have to prove that H belongs to R? 2. the proof is for machines that run precisely f(n) steps, I'm required to prove so for O(n) steps,so for different machine f may be a different function, e.g, M1 runs for 3n steps, and M2 runs for 100n steps. – Caesar23 Nov 22 '16 at 14:05
• @Caesar23 You can ignore the constant factors because of the linear speedup theorem. – skankhunt42 Nov 22 '16 at 15:39