-2
$\begingroup$

I'm new to theoretical 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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ This seems more suitable for our sister site Computer Science. ps: Look up Rice's theorem. $\endgroup$
    – Kaveh
    Jun 7, 2016 at 5:19
  • $\begingroup$ I agree. I realized it later. Sorry for that. $\endgroup$
    – musigma
    Jun 8, 2016 at 6:44

1 Answer 1

Reset to default
-1
$\begingroup$

I suppose that your programs are written in a Turing complete language; almost all common languages fall into this category. Then the answer is NO. We know that there is no program/machine that can decide whether two Turing machines compute the same function, see also a question on this topic. And Turing complete languages can implement the funtions of all Turing machines.

This supposes that the potential number of inputs is infinite. When you say "without actually running the 2 programs for all input values", does this mean that there is only a finite number of these pairs? In that case there could be programs to decide equivalence that are more clever than computing all pairs. It would depend on how restricted your set of functions is.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I also depends on whether the programs can loop and never produce an answer. In this case you cannot decide equivalence even for one input ( they are equivalent if they both loop or both give the same answer). $\endgroup$
    – Denis
    Jun 7, 2016 at 10:37
  • $\begingroup$ Thanks for the careful reading. You are right about the loop. - unless it is a type of infinte loop that can be detected ;) For a restricted type of function, also halting might be decidable. Anyway, this is probably not the case that is asked for. $\endgroup$
    – Peter Leupold
    Jun 7, 2016 at 10:40
  • $\begingroup$ @peter, denis: thank you for that. For input variables, I assume that the number of possible values is infinite like a set of all integers or reals. I asked this question to understand how Online judges like spoj and Code forces judge whether a program submitted by a user is correct or not. They do so by running the code on certain inputs. I feel they may not be entirely correct in their judgement. We can perhaps say they are most probably correct. Am I wrong in saying that? -- Thanks $\endgroup$
    – musigma
    Jun 8, 2016 at 6:41

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