7
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ This is related to (actually, it is basically a duplicate of) this question. $\endgroup$
    – Damiano Mazza
    Commented Dec 12, 2017 at 21:43
  • $\begingroup$ @DamianoMazza Youch - burned by isomorphism. I'll claim the upper hand in searchable keywords, however. :-P $\endgroup$
    – user
    Commented Dec 13, 2017 at 10:21
  • $\begingroup$ 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! $\endgroup$
    – Damiano Mazza
    Commented Dec 13, 2017 at 13:13

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$
    – user
    Commented Dec 9, 2017 at 7:52
  • $\begingroup$ Oh, nvm, you qualified that with 'standard Turing Machines'. $\endgroup$
    – user
    Commented Dec 9, 2017 at 8:00
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user
    Commented Dec 9, 2017 at 22:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – user
    Commented Dec 9, 2017 at 23:56
  • $\begingroup$ @user exactly right $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Dec 10, 2017 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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