Why does the halting problem make it impossible for software to determine the time complexity of an algorithm

Question

I've read some articles about big-Oh calculation and the halting problem. Obviously it's not possible for ALL algoritms to say if they ever are going to stop, for example:

while(System.in.readline()){

}

However, what would be the big-Oh of such a program? I think it's not defined, for the same reason it's not possible to say if it's ever going to halt. You don't know that.

So... There are some possible algorithms, where you cannot say if it's ever going to halt. But if you can't say the, the big-Oh of that algorithm is by definition undefined.

Now to my point, calculating the big-oh of a piece of software. Why can't you write a program that does that? Because it is either a function, or not defined.

Also, I've not said anything about the programming language. What about a purely functional programming language? Can it be calculated there?

Chartography

Answer 1

OK, so let's talk about Turing machines (a similar discussion using the Random-Access model could be had, but I adopt this for simplicity).

An upper-bound on the time complexity of a TM says something about the order of the rate at which the number of transitions the TM makes grows according to the input size. Specifically, if we say a TM executes an algorithm which is O(f(n)) in the worst case for input size n, we are saying that there exists an n0 and c such that, for n > n0, T(n) <= cf(n). So far, so good.

Now, the thing about Turing machines is that they can fail to halt, that is, they can execute forever for some inputs. Clearly, if for some n* > n0 a TM takes an infinite number of steps, there is no f(n) satisfying the condition (with finite n0, c) laid out in the last paragraph; that is, T(N) != O(f(n)) for any f. OK; if we were able to say for certain that a TM would halt for all inputs of length at least n0, for some n0, we're home free. Trouble is, this is equivalent to solving the halting problem.

So we conclude this: if a TM takes forever to halt on an input n > n0, then we cannot define an upper bound on complexity; furthermore, it is an unsolvable problem to algorithmically determine whether the TM will halt on all inputs greater than a fixed, finite n0.

Teutonize

Answer 2

The reason it is impossible to answer the question "is the 'while(System.in.readline()){}' program going to stop?" is that the input is not specified, so in this particular case the problem is lack of information and not undecidability.

The halting problem is about the impossibility of constructing a general algorithm which, when provided with both a program and an input, can always tell whether that program with that input will finish running or continue to run forever.

In the halting problem, both program and input can be arbitrarily large, but they are intended to be finite.

Also, there is no specific instance of 'program + input' that is undecidable in itself: given a specific instance, it is (in principle) always possible to construct an algorithm that analyses that instance and/or class of instances, and calculates the correct answer.

However, if a problem is undecidable, then no matter how many times the algorithm is extended to correctly analyse additional instances or classes of instances, the process will never end: it will always be possible to come up with new instances that the algorithm will not be capable of answering unless it is further extended.

I would say that the big O of "while(System.in.readline()){}" is O(n) where n is the size of the input (the program could be seen as the skeleton of e.g. a line counting program).

The big O is defined in this case because for every input of finite size the program halts.

So the question to be asked might be: "does a program halt on every possible finite input it may be provided with?"

If that queston can be reduced to the halting problem or any other undecidable problem then it is undecidable.

It turns out that it can be reduced, as clarified here: https://cs.stackexchange.com/questions/41243/halting-problem-reduction-to-halting-for-all-inputs

Undecidability is a property of problems and is independent of programming languages that are used to construct programs that run on the same machines. For instance you may consider that any program written in a functional programming language can be compiled into machine code, but that same machine code can be produced by an equivalent program written in assembly, so from a Turing machine perspective, functional programming languages are no more powerful than assembly languages.

Also, undecidability would not prevent an algorithm from being able to calculate the big O for a countless (theoretically infinite) number of programs, so any effort in constructing an algorithm for that purpose would not necessarily be pointless.

Negrete