2
$\begingroup$

Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?

I've read the similar questions and answers such as here, but I wanted to make sure that they were talking about any machine on any input, not a particular machine or on a particular input.

If it is possible, I'd love for someone to explain intuitively how it's possible generally. Is it done by simulating the Turing machine more efficiently, or is it done by analyzing the Turing machine syntactically and deducing that it must run in n or fewer steps? I'm also curious how it's possible in the specific case, but that is not this question.

I'm trying to come at it from Rice's Theorem, here. It's clearly a decidable property, even generally, since you can run the machine for n steps, but is it decidable by any method other than that?

$\endgroup$
2
  • 1
    $\begingroup$ This is the halting problem, its undecidable. At least if you meant that you want to construct an algorithm that when given as an input a machine $M$ and $w$, will tell you if $M$ halts when ran with $w$ as its input. $\endgroup$
    – nir shahar
    Oct 30 '21 at 18:43
  • $\begingroup$ Well, it is decideable, but only after running for n steps, right? I suspect you're right that it is undecideable otherwise, but I can't think of a good proof why. $\endgroup$ Oct 30 '21 at 20:19
2
$\begingroup$

Theoretical answer: If you only count the "number of steps", yes, there is. See the linear speedup theorem. (Intuition: I can build a new algorithm where each step does twice as much work, then it will only need about half as many steps. You can think of this as basically exploiting a flaw with using "number of steps" as our way to measure the speed of an algorithm.)

Practical answer: I expect there probably is no algorithm that is appreciably faster in practice (in terms of worst-case time to finish running), and that works on every machine and every input. I have no proof for this.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.