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.

  • 1
    $\begingroup$ Are you familiar with the time hierarchy theorem? $\endgroup$ – David Richerby Nov 22 '16 at 12:54
  • $\begingroup$ @DavidRicherby R is the set of recursive languages. I'm not familiar with that theorem. $\endgroup$ – Caesar23 Nov 22 '16 at 12:57
  • $\begingroup$ I suggest you have a look at it -- you're essentially being asked to prove a special case of it. $\endgroup$ – David Richerby Nov 22 '16 at 13:18
  • $\begingroup$ 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. $\endgroup$ – Caesar23 Nov 22 '16 at 14:05
  • $\begingroup$ @Caesar23 You can ignore the constant factors because of the linear speedup theorem. $\endgroup$ – skankhunt42 Nov 22 '16 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.