Algorithm Checking

Is it possible giving a well defined problem, to write an algorithm which takes in as input another algorithm and checks if that algorithm is correct.

If it isn't possible, I'm thinking of storing solutions to a large number of problem sizes, randomly selecting a smaller number of problem instances and seeing if the algorithm solves those particular problem cases.

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Jun 15 '17 at 12:46

In theory, testing weather an algorithm terminates in a finite time is undecidable! This is the Halting Problem. Checking the correctness is harder.

But in practice, you can try to test it. This book may help you:

Introduction to Software Testing

• Welcome to the site! Note that "terminates in finite time" just means "terminates", since there's no such thing as "terminates in infinite time". – David Richerby Jun 15 '17 at 7:30
• But that isn't my question. I know what the halting problem is, I'm trying to test if the algorithm is correct. I think they are different; aren't they? – Tobi Alafin Jun 15 '17 at 8:02
• Halting is easier than testing the algorithm. Consider a trivial problem that the answer is always $0$. For an instance of halting problem, add "print 0" in the last line. If the instance terminates, it will print $0$ and is a correct algorithm. Otherwise, it's wrong. – Mohemnist Jun 15 '17 at 8:43
• @DavidRicherby, Mohemnist, does this mean that proof verification is impossible? – Tobi Alafin Jun 15 '17 at 9:28
• @TobiAlafin I don't know what you mean by "proof verification" or why that would depend on the fact that Turing machines by construction either halt after a finite number of steps or run forever. The relevance of the halting problem is that, to be correct, an input must halt for all inputs and output the correct answer. If you can't even tell if it halts, you certainly can't tell if it halts and does something else. – David Richerby Jun 15 '17 at 9:31

"randomly selecting a smaller number of problem instances and seeing if the algorithm solves those particular problem cases".

That's not quite trivial. First, you can't test algorithms. You can test implementations. An algorithm doesn't actually do anything, an implementation does. And you can have an incorrect implementation of an algorithm, which might fail even if the algorithm is correct.

Second, you either need to know the solutions, or need a method to check that a solution is actually the correct solution. Third, it might be that the implementation doesn't find a solution. In that case, you need to have proof whether a solution exists or not, or the implementation needs to provide a verifiable proof that no solution exists.