3
$\begingroup$

Title is self explanatory.

I have searched here on this site and haven't found any discussion about this.

Is it somehow related to Turing's Halting problem (which is undecidable)?

$\endgroup$

marked as duplicate by Juho, David Richerby complexity-theory Dec 10 '18 at 16:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

Yes, you are right. There is no program that can calculate all algorithms' time complexity.

More formally speaking, there is no Turing machine which, given any Turing machine $T$ and an input of length $n$, it can calculate a finite upper bound for the computation time that will be used by $T$ and that input in case that computation does halt, or infinity in case that computation does not halt. The reason is simple, as you have mentioned, there is no Turing machine that can decide whether an arbitrarily computation will run forever or not in the first place. In fact, we cannot algorithmically tell even whether a given Turing machine halts on the empty input.

Notice that a trivial time complexity of all algorithms is an upper bound of running forever for any input. There are also trivial lower bounds such as whether the computation will run for less than for 7 steps. Those trivial time complexities have to be excluded from our discussion so as to keep our discussion interesting.

We can ask refined questions. For example, does an arbitrary Turing machine run in time $O(1)$? It turns out this question is undecidable as well.

For more information, you may want to read Verifying Time Complexity of Turing Machines by David Gajser.

$\endgroup$
  • $\begingroup$ Thank you for the answer and the reference! $\endgroup$ – ihavenoidea Dec 10 '18 at 18:40
  • $\begingroup$ You are welcome! $\endgroup$ – Apass.Jack Dec 10 '18 at 19:34
1
$\begingroup$

Yes, not possible. Halting problem can be reduced to this problem.

Let $L_{com}=\{<M,n>| M \ is \ a \ TM \ with\ n\ input \}$ which is decided by $M_{com}$. Then it can be shown that Halting Problem $D$ can be reduced to this problem.

Let $D = "On\ input\ <M,w>"$

  • Encode/Map $w$ to unique number $n$ if $w$ is accepted by $M$ else make $n=-1$.
  • Feed $<M,n>$ to $M_{com}$, if complexity is positive accept otherwise reject.

Now, since we know Halting problem is undecidable and it is reducible to the problem of finding complexity of turing machine, the problem of finding complexity of turing machine is undecidable.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer, I still don't have the background to fully understand how to reduce an algorithm to another (and so to 100% understand your explanation) but I'll come back to your answer once I study more on this subject. $\endgroup$ – ihavenoidea Dec 10 '18 at 18:42
  • $\begingroup$ Sure. You are welcome. @ihavenoidea $\endgroup$ – Mr. Sigma. Dec 11 '18 at 0:19

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