There doesn't exist an algorithm which decides on the following problem: Does a given Turing machine work in time limited by $5n$? $n$ is the length of $w$. $w$ is an input word.

The answer is:

No, because if it was true then we would decide on problem: Does an universal machine accept a word $w$.

I don't understand why that argument works. Please explain.

  • 1
    $\begingroup$ What do you mean by "...Turing machine works in time..."? Works for at least $5n$ steps? Also please define what $n$ is. $\endgroup$ – fade2black Aug 27 '17 at 2:20
  • 1
    $\begingroup$ @Evil The set of Turing machines which halt in time (at most) $5n$ steps on all inputs is decidable, for some fixed $n$. No? $\endgroup$ – fade2black Aug 27 '17 at 3:02
  • $\begingroup$ @fade2black yes, you are absolutely right, it is decidable. I have parsed the question differently, 5n not as the numbers of steps it performs, so given that I retract my comment, it does matter what $n$ denotes, thank you. $\endgroup$ – Evil Aug 27 '17 at 3:32
  • 2
    $\begingroup$ Could you please indicate the source of the question? Book, notes...? $\endgroup$ – fade2black Aug 27 '17 at 3:37
  • 1
    $\begingroup$ The are proposing a reduction partner here, leaving you to come up with the reduction. Try doing so! $\endgroup$ – Raphael Aug 27 '17 at 7:54

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.