I'm having trouble proving if the following language is recursive, recursively enumerable, or not r.e. at all: the set of all encodings of Turing machines $M$ such that the number of positions in the tape used by $M$ when the input is 0011 is less than 10.

I'm suspicious the problem is unrecognizable but I can't come up with any reduction to prove it. Any help would be appreciated.

  • 1
    $\begingroup$ You can run $M$ on $0011$ until it either loops or uses more than $10$ positions. $\endgroup$ – Yuval Filmus Apr 8 '20 at 16:18
  • 1
    $\begingroup$ Hint, the above comment tells you the way to show the problem is decidable. $\endgroup$ – John L. Apr 8 '20 at 16:44
  • $\begingroup$ @JohnL. I have to know what happens if M loops forever. If I "bound" the number of steps looping within the same 10 positions, it is guaranteed that, if M loops forever, it will do it without visiting more than those positions. But I can't find a pattern. $\endgroup$ – Fran Castro Apr 8 '20 at 17:11
  • $\begingroup$ @YuvalFilmus but M might loop and use less than 10 positions. $\endgroup$ – Fran Castro Apr 8 '20 at 17:13
  • $\begingroup$ If it uses more than 10 positions, you can immediately stop. Otherwise, either it halts at some point, or it loops at some point (we even have an a priori bound on when that must happen, though this is not necessary). $\endgroup$ – Yuval Filmus Apr 8 '20 at 17:16

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.