I'd like to prove by reduction that given a Turing machine $M$, there exists no Turing machine that decides whether $M$ ends in polynomial time on any input.

Any idea as to what problem to reduce, as a first hint?

  • 3
    $\begingroup$ What have you tried and where did you get stuck? Have you tried the Halting problem as default reduction partner? You may want to check out our reference questions, and this one. $\endgroup$ – Raphael Nov 8 '16 at 0:25
  • 1
    $\begingroup$ What does "ends in polynomial time on any input" mean? Polynomial time is an asymptotic notion, and we usually don't have a fixed polynomial in mind. Try to rephrase your question using more basic terms. $\endgroup$ – Yuval Filmus Nov 8 '16 at 7:32
  • $\begingroup$ @YuvalFilmus *shrug* "... no Turing machine that decides whether there is some polynomial $p$ such that $M$ halts within $p(|x|)$ steps for all inputs $x$." I suspect that's not the asker's difficulty. $\endgroup$ – David Richerby Nov 8 '16 at 9:22
  • 1
    $\begingroup$ @DavidRicherby In that case, perhaps every is better than any. $\endgroup$ – Yuval Filmus Nov 8 '16 at 9:32
  • 3
    $\begingroup$ @YuvalFilmus Yeah. I vote to ban the word "any" in mathematical writing. It can be existential or universal depending on context and it's far too easy to interpret it the wrong way. (Actually, I think that, in this case, I might've misread the question as literally saying "every"; I agree that it looks existential in the actual sentence.) $\endgroup$ – David Richerby Nov 8 '16 at 9:36

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.