# Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

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?

• Can you explain what you mean by "time complexity is independent of input"? Give a formal definition. – Yuval Filmus Feb 14 '19 at 17:00
• I realized my question was very poorly phrased so I have modified it significantly. – Tomer Aberbach Feb 14 '19 at 18:58
• 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. – Yuval Filmus Feb 14 '19 at 19:05
• I have clarified my question further. Is it sufficiently precise now? If not, could you explain what is unclear about it? – Tomer Aberbach Feb 14 '19 at 19:25
• Yes, much better. – Yuval Filmus Feb 14 '19 at 19:26

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.

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