# Decidable Program Equivalence

Determining whether two programs always return same output for same input is undecidable (easily reduced to the halting problem). My question is, is there a complexity class in which this problem is decidable for machines on that class?

Seems like it must be below PTIME, as Datalog is P-Complete and equivalence of Datalog programs is undecidable.

• What do you mean by "complexity class"? Does the class of regular languages count as one, for instance? Note that not all complexity classes have a machine model that correspond to them. – dkaeae Jul 16 '19 at 16:18
• Your question contains a category error. Complexity classes are classes of problems (e.g., "Is this graph 3-colourable"), not classes of programs (e.g., algorithms which may or may not compute 3-colourings of graphs"). – David Richerby Jul 16 '19 at 17:17
• they're classes of programs too - all machines that run in say polynomial time wrt the input size. im just talking from descriptive complexity point of view – Troy McClure Jul 16 '19 at 20:30
• more explicitly and for example, one can take any machine that runs in PTIME and convert it into a datalog program. if we could decide equivalence of any two PTIME machines, then we could decide equivalence of datalog programs. therefore such is undecidable – Troy McClure Jul 16 '19 at 21:25

Given a Turing machine $$M$$, we can construct another Turing machine $$T$$, which on input $$1^n$$ simulates $$M$$ for $$\log n$$ steps, and returns whether $$M$$ halted within these steps. The new Turing machine runs in linear time, and is equivalent to the constant time Turing machine which always returns "No" iff $$M$$ doesn't halt. Therefore program equivalence is undecidable even for linear time Turing machines.

• sorry but im sure im missing something here. can you please elaborate a little more? – Troy McClure Jul 16 '19 at 23:22
• @TroyMcClure if ive gotten the argument right, Yuval is saying « the turing machine that decides program equivalence could solve the halting problem » – D. Ben Knoble Jul 17 '19 at 0:14
• @TroyMcClure Above $M$ is any arbitrary TM. TM $T$ simultaes $M$ only for $\log n$ steps, so $T$ has linear complexity, no matter what $M$ is. If $M$ does not halt, $T$ will answer "no" to all inputs. If $M$ halts, $T$ will answer "no" for small inputs, and "yes" for large enough inputs. So, if we can decide the equivalence of the linear-time $T$ with the constant time "always no" TM, we decide the halting problem on any $M$. – chi Jul 17 '19 at 11:42
• but it can solve the halting problem only for M and even that is after we constructed a machine that solves the halting problem for M (so we already know whether M halts). or im missing something – Troy McClure Jul 17 '19 at 12:50

Reversal Bounded Counter Automata have decidable equivalence. They're a fascinating class, because augmenting them in any obvious way makes one of their main properties (equivalence, emptiness, etc.) undecidable. Oscar Ibarra's work explored their properties extensively: http://www.lsv.ens-cachan.fr/~demri/Ibarra78.pdf

If I recall correctly, visibly pushdown Automata also have decidable equivalence, though I'm as familiar with that class.

• what can we tell about their expressive power? – Troy McClure Jul 17 '19 at 14:46
• @TroyMcClure They're not comparable with Context Free languages i.e. more powerful in some respects, weaker in others. I think in the unary case they're equivalent to Presburger arithmetic, but I don't remember the reference for that offhand. – jmite Jul 17 '19 at 17:58
• thanks, so it doesn't correspond to any standard complexity class? – Troy McClure Jul 17 '19 at 18:23
• @TroyMcClure the class accepted by the deterministic variant at least is a subset of P. – jmite Jul 17 '19 at 19:46