2
$\begingroup$

As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts?

The decision problem, more formally:

Given a Turing machine $M$ where it is assumed it halts on all inputs, determine if it runs in $O(1)$ time.

Is this decidable?

$\endgroup$
  • $\begingroup$ Can you explain what you mean by "time complexity is independent of input"? Give a formal definition. $\endgroup$ – Yuval Filmus Feb 14 at 17:00
  • $\begingroup$ I realized my question was very poorly phrased so I have modified it significantly. $\endgroup$ – Tomer Aberbach Feb 14 at 18:58
  • $\begingroup$ What does "$f = O(1)$" mean? What do you mean by constant time? Which machine model do you have in mind? Your question is still very much imprecise. $\endgroup$ – Yuval Filmus Feb 14 at 19:05
  • $\begingroup$ I have clarified my question further. Is it sufficiently precise now? If not, could you explain what is unclear about it? $\endgroup$ – Tomer Aberbach Feb 14 at 19:25
  • $\begingroup$ Yes, much better. $\endgroup$ – Yuval Filmus Feb 14 at 19:26
2
$\begingroup$

This answer is for the following version of the question:

Can we decide whether an algorithm runs in constant time (that is, within $N$ steps, for some $N$), given that it is guaranteed to always halt?

This is not decidable. Given a Turing machine $T$, construct a new Turing machine $M$ which on input $t$ runs $T$ for up to $t$ steps. Then $M$ runs in constant time iff $T$ halts.

$\endgroup$
1
$\begingroup$

It is still undecidable. Pick some algorithm M that has a time complexity dependent on the input (whatever exactly that means).

Now given some Turing machine T, consider the algorithm A that works as follows:

1) Simulate T on empty input until it halts. 2) Run M on the original input.

If T does not halt, then A never halts for any input, hence has time complexity independent of the input. If T halts after k steps, then A essentially takes k steps more than M does for any input. Since M's time complexity depends on the input, so should the time complexity of A.

$\endgroup$
  • $\begingroup$ Sorry, I realized my question was very poorly phrased so I have modified it significantly. $\endgroup$ – Tomer Aberbach Feb 14 at 18:57

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.