<p>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 href="https://cs.stackexchange.com/questions/45683/given-two-total-turing-machines-is-it-undecidable-problem-to-detect-whether-the">a question on this topic</a>. And Turing complete languages can implement the funtions of all Turing machines.</p>

<p>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.</p>

CC BY-SA 3.0
2016-06-07T10:37:24.313Z
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).
Denis
CC BY-SA 3.0
2016-06-07T10:40:39.023Z
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.
Peter Leupold
CC BY-SA 3.0
2016-06-08T06:41:11.717Z
@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
musigma
CC BY-SA 3.0
2016-06-07T10:13:30.437Z
2016-06-07T10:13:30.437Z
2017-04-13T12:48:30.830Z
Peter Leupold
<p>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?</p>

<p>Thanks.</p>

CC BY-SA 3.0
2016-06-07T05:19:47.983Z
This seems more suitable for our sister site [cs.se]. ps: Look up Rice's theorem.
Kaveh
CC BY-SA 3.0
2016-06-08T06:44:26.173Z
I agree. I realized it later. Sorry for that.
musigma
<pl.programming-languages>
Comparing 2 programs for equivalence w.r.t input - output pairs
musigma
# Comparing 2 programs for equivalence w.r.t input - output pairs

(Asked by: username_0 on 2016-06-07)

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.

**Tags:** pl.programming-languages

> **Comments:**
> **username_1**: This seems more suitable for our sister site [cs.se]. ps: Look up Rice's theorem.  
> **username_0**: I agree. I realized it later. Sorry for that.  

---

## 1 answers

### Answer by username_2 on 2016-06-07. Score: -1 | Accepted answer

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](https://cs.stackexchange.com/questions/45683/given-two-total-turing-machines-is-it-undecidable-problem-to-detect-whether-the). 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.

> **Comments:**
> **username_3**: 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).  
> **username_2**: 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.  
> **username_0**: @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  

---

