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.
$\begingroup$
$\endgroup$
1
asked Jun 15, 2017 at 6:47
-
$\begingroup$ 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! $\endgroup$– Raphael ♦Jun 15, 2017 at 12:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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:
-
1$\begingroup$ Welcome to the site! Note that "terminates in finite time" just means "terminates", since there's no such thing as "terminates in infinite time". $\endgroup$ Jun 15, 2017 at 7:30
-
$\begingroup$ 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? $\endgroup$ Jun 15, 2017 at 8:02
-
1$\begingroup$ 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. $\endgroup$ Jun 15, 2017 at 8:43
-
$\begingroup$ @DavidRicherby, Mohemnist, does this mean that proof verification is impossible? $\endgroup$ Jun 15, 2017 at 9:28
-
1$\begingroup$ @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. $\endgroup$ Jun 15, 2017 at 9:31
$\begingroup$
$\endgroup$
"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.
