I have an exercise question as follows:

L is a set of all Turing Machine encodings for which the Turing Machine halts after a number of steps less than or equal to the minimum value among |w| and 1000, where w is the input to the machine

I understand from my textbook that the problem of halting before 1000 steps is decidable, however, with the introduction of the length of w I believe that L is undecidable. How would I go about showing this?

  • 1
    $\begingroup$ What makes you think this is undecidable now? Observe that the minimum value between $|w|$ and $1000$ is at most $1000$, and you can simulate a TM for a 1000 steps, while keeping a step counter (to compare with $|w|$). $\endgroup$
    – Shaull
    May 10 at 11:07
  • $\begingroup$ Oh I see. I was thinking that since the problem of halting on the length of input is undecidable that this would be affect this problem. $\endgroup$
    – TheClash
    May 10 at 11:11

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.