1
$\begingroup$

I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of values for input variables (i.e., min to max values), is it possible to check with another program whether these 2 programs will give the same output values for all possible input values, without actually running the 2 programs for all input values?

Thanks.

$\endgroup$
  • $\begingroup$ Are you saying there are only finitely many input? $\endgroup$ – Raphael Jun 7 '16 at 7:05
  • $\begingroup$ I assume inputs can be of integer or real data types. They can be either within (min, max) range or extend up to infinity. There is no other constraint. $\endgroup$ – musigma Jun 7 '16 at 7:11
  • 2
    $\begingroup$ Stop posting comments as answers. You can always comment on your own posts, and answers to yourt questions. However, you seem to have created multiple accounts; see here on how to remedy that. $\endgroup$ – Raphael Jun 7 '16 at 7:15
1
$\begingroup$

No. That's undecidable. Suppose the first program is

return 42

and the second program is

if (f(x) halts)
    return 0
else
    return 42

where x is the input.

Do these two programs yield the same output, for all possible inputs? That depends whether f always halts on all inputs. And that is exactly the halting problem, which we know is not decidable. It's easy to see that, as a consequence, this problem can't be decidable either (if it were, you could decide the halting problem).

$\endgroup$
  • $\begingroup$ Thank you very much. So, we can say that just because 2 programs give same outputs for identical set of input values, we can't say that they will give same output for another input value. My question is related to the way Online Judges like SPOJ and CodeChef test programs submitted by coders. I assume that they run the submitted program on a specific set of inputs. If it passes then they assume the program is correct. Although it may be true most of the time, it is probably not a fool-proof method. Am I right? Thanks. $\endgroup$ – user53263 Jun 7 '16 at 6:54
  • $\begingroup$ What is f? I guess you want to formulate a decision problem ranging over all f? Note that the OP seems to restrict the problem to a finite range of inputs. $\endgroup$ – Raphael Jun 7 '16 at 7:07
  • $\begingroup$ @musigma The general problem is undecidable. That does however not mean that you can not write a checker for some problems/algorithms. $\endgroup$ – Raphael Jun 7 '16 at 7:08
  • $\begingroup$ @Raphael, well, this is a reduction: f is the instance of the Halting problem. Does the finite range of inputs make the Halting problem decidable? $\endgroup$ – D.W. Jun 7 '16 at 7:11
  • $\begingroup$ @D.W. I don't think so, but one may have to adapt the reduction. $\endgroup$ – Raphael Jun 7 '16 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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