Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
