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?



closed as off-topic by user6973, Kaveh, Andrej Bauer, Jan Johannsen, Mohammad Al-Turkistany Jun 7 '16 at 12:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Community, Kaveh, Andrej Bauer, Jan Johannsen, Mohammad Al-Turkistany
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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.

  • 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 '16 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 '16 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 '16 at 6:41

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