What is Algorithmic Problem Solving ?

[chiro]

Neither mathematics nor computer science is a natural science, because they do not study the physical world.

While mathematics doesn't study the physical world, mathematics at its core is the generalization of abstractions of the world as we experience it. Nothing comes even closer to providing a mechanism that describes our world other than mathematics.

 

[AUMathTutor]

Here's what I'm getting at: is it possible to look at an algorithm, and for some actual input to that algorithm, prove that it is impossible to prove that it terminates or fails to terminate?

In other words, for these (hypothetical) algorithms the termination of which cannot be determined, do there exist valid proofs demonstrating the impossibility of termination proofs?

Does this make any sense? I'd be very wary of accepting anything of this theoretical nature without proof, especially since it goes against intuition. You seem to be making the argument that "who knows?", but that's different in my mind than "you can't know".

The more that I think about it, I imagine you're right anyway, in a sense, since Godel's incompleteness theorem probably works the same for termination proofs of algorithms as for any other proofs.

My original point: Wikipedia makes it sound like the best we can do is run algorithms and time them, when in reality you usually can tell whether they terminate or not (in fact, if you were to write a deterministic algorithm whose termination was unknown and unknowable, your boss would probably make you write another algorithm...) I maintain that the Wiki page was misleading in this regard.

 

[mXSCNT]

Here's what I'm getting at: is it possible to look at an algorithm, and for some actual input to that algorithm, prove that it is impossible to prove that it terminates or fails to terminate?

No, as I've already mentioned: if you could prove that it is impossible to prove an algorithm terminates, it immediately follows that the algorithm does not terminate. This is because every algorithm that terminates has a proof of termination, namely running the algorithm and observing the termination.

My original point: Wikipedia makes it sound like the best we can do is run algorithms and time them, when in reality you usually can tell whether they terminate or not (in fact, if you were to write a deterministic algorithm whose termination was unknown and unknowable, your boss would probably make you write another algorithm...) I maintain that the Wiki page was misleading in this regard.

The proof of the undecidability of the halting problem doesn't restrict the algorithms that might attempt to solve it. They could do anything, including static analysis and whatever else. It may be intuitive in some cases to think about just running the algorithm and waiting for termination--but it's not the only way to do it.