<p>Consider programs $e_1$, $e_2$ and numbers of time steps $t$.</p>

<p>Let $f_i(t)$ be the output of $e_i$ after $t$ steps, and let $f_i(t)$ output a special message like "none" if there's no output yet.</p>

<p>Then $f_1$ and $f_2$ both always halt, but you can't decide if they always output the same - see <a href="https://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow noreferrer">Rice's Theorem</a>.</p>

CC BY-SA 3.0
2017-12-09T22:41:41.560Z
Would you mind clarifying for me the applicability of Rice's theorem? My reading of the proof sketch by reduction to the halting problem on Wikipedia has that proof inapplicable because my oracle already said they halt, so there's no way to make that reduction (the arbitrary program must halt because my oracle said the enveloping program halts, else I wouldn't be trying to evaluate the equivalence). I haven't quite grokked the other proofs yet.
user
CC BY-SA 3.0
2017-12-09T23:56:51.123Z
Nevermind, I misread your answer. It might be worth emphasizing that because we're discriminating between 'none' and a value as $t$ goes to $\infty$ we're therefore deciding the halting problem.
user
CC BY-SA 3.0
2017-12-10T01:09:31.883Z
@user exactly right
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-12-08T17:11:14.833Z
2017-12-08T17:11:14.833Z
Bjørn Kjos-Hanssen
<p>As a counter-example to this, consider the Context-Free Equivalence problem: it's undecidable to determine, given two context free languages, whether they accept the same set.</p>

<p>If your problem were decidable, we could use it to determine CFL equivalence, since it's always possible to turn a CFL into an always-halting Turing machine.</p>

<p>So even for countably infinite inputs, the problem is undecidable.</p>

<p>It's also worth mentioning that, for standard Turing Machines, all input domains are countably infinite, since they're sets of finite strings.</p>

CC BY-SA 3.0
2017-12-09T07:52:40.353Z
Cool, thanks - but re: the last bit: if I have infinite sized inputs (e.g. streams), can't I diagonalize and show that the set of possible inputs is uncountable? (Or am I mis-remembering what an 'input' is allowed to be? I'd think a machine need not look at its whole input - but I could be very wrong and confused)
user
CC BY-SA 3.0
2017-12-09T08:00:12.700Z
Oh, nvm, you qualified that with 'standard Turing Machines'.
user
CC BY-SA 3.0
2017-12-08T18:52:57.043Z
2017-12-08T18:52:57.043Z
Joey Eremondi
<p>Say I have two programs with possibly infinite state spaces and some oracle has asserted that they both always halt. Can I always decide if they're contextually equivalent? If yes, is there a known effective algorithm (or approach that when applied on a case-by-case or language-by-language basis provides an effective algorithm) to do so?</p>

<p>The answer is obviously yes/yes for finite input domains, but for infinite input domains: does the decidability depend at all on <em>how</em> infinitely huge (e.g. countable vs. uncountable) the input domains are?</p>

CC BY-SA 3.0
2017-12-12T21:43:53.097Z
This is related to (actually, it is basically a duplicate of) [this question](https://cstheory.stackexchange.com/q/21614/20716).
Damiano Mazza
CC BY-SA 3.0
2017-12-13T10:21:14.507Z
@DamianoMazza Youch - burned by isomorphism. I'll claim the upper hand in searchable keywords, however. :-P
user
CC BY-SA 3.0
2017-12-13T13:13:10.670Z
Yes, it can be **very** hard to find out if a question (or something similar) has already been asked.  Sometimes I even have problems retrieving questions I *know* have been asked! :-)  Your question will definitely be easier to find!
Damiano Mazza
<halting-problem><equivalence>
Program equivalence wherein the programs are known to always halt
user
# Program equivalence wherein the programs are known to always halt

(Asked by: username_0 on 2017-12-08)

Say I have two programs with possibly infinite state spaces and some oracle has asserted that they both always halt. Can I always decide if they're contextually equivalent? If yes, is there a known effective algorithm (or approach that when applied on a case-by-case or language-by-language basis provides an effective algorithm) to do so?

The answer is obviously yes/yes for finite input domains, but for infinite input domains: does the decidability depend at all on *how* infinitely huge (e.g. countable vs. uncountable) the input domains are?

**Tags:** halting-problem, equivalence
> **Comments:**
> **username_1**: This is related to (actually, it is basically a duplicate of) [this question](https://cstheory.stackexchange.com/q/21614/20716).  
> **username_0**: @DamianoMazza Youch - burned by isomorphism. I'll claim the upper hand in searchable keywords, however. :-P  
> **username_1**: Yes, it can be **very** hard to find out if a question (or something similar) has already been asked.  Sometimes I even have problems retrieving questions I *know* have been asked! :-)  Your question will definitely be easier to find!  

---

## 2 answers

### Answer by username_3 on 2017-12-08. Score: 6 | Accepted answer

As a counter-example to this, consider the Context-Free Equivalence problem: it's undecidable to determine, given two context free languages, whether they accept the same set.

If your problem were decidable, we could use it to determine CFL equivalence, since it's always possible to turn a CFL into an always-halting Turing machine.

So even for countably infinite inputs, the problem is undecidable.

It's also worth mentioning that, for standard Turing Machines, all input domains are countably infinite, since they're sets of finite strings.

> **Comments:**
> **username_0**: Cool, thanks - but re: the last bit: if I have infinite sized inputs (e.g. streams), can't I diagonalize and show that the set of possible inputs is uncountable? (Or am I mis-remembering what an 'input' is allowed to be? I'd think a machine need not look at its whole input - but I could be very wrong and confused)  
> **username_0**: Oh, nvm, you qualified that with 'standard Turing Machines'.  

---

### Answer by username_2 on 2017-12-08. Score: 4

Consider programs $e\_1$, $e\_2$ and numbers of time steps $t$.

Let $f\_i(t)$ be the output of $e\_i$ after $t$ steps, and let $f\_i(t)$ output a special message like "none" if there's no output yet.

Then $f\_1$ and $f\_2$ both always halt, but you can't decide if they always output the same - see [Rice's Theorem](https://en.wikipedia.org/wiki/Rice%27s_theorem).

> **Comments:**
> **username_0**: Would you mind clarifying for me the applicability of Rice's theorem? My reading of the proof sketch by reduction to the halting problem on Wikipedia has that proof inapplicable because my oracle already said they halt, so there's no way to make that reduction (the arbitrary program must halt because my oracle said the enveloping program halts, else I wouldn't be trying to evaluate the equivalence). I haven't quite grokked the other proofs yet.  
> **username_0**: Nevermind, I misread your answer. It might be worth emphasizing that because we're discriminating between 'none' and a value as $t$ goes to $\infty$ we're therefore deciding the halting problem.  
> **username_2**: @user exactly right  

---

