Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Set D : Set of decision algorithms X∈D if and only if

  1. X is an Turing machine algorithm with finite length

  2. takes one input i, binary number

  3. X(i)=0 or X(i)=1 or X(i) runs forever

Definition: equivalent
Algorithm X∈D and Y∈D are equivalent if and only if For all i
X(i) =1 ⇔ Y(i)=1 and X(i) =0 ⇔ Y(i)=0

Definition: equivalent checker

Algorithm H is equivalent checker if and only if For all X∈D, for all Y∈D
X and Y are not equivalent algorithms → H( X , Y) = 1
X and Y are equivalent algorithms → H( X , Y) = 0

My Question: Equivalent checker H does exist?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

There is no computable equivalence checker. The reason is that if there were, we could solve the halting problem, as follows: given a Turing machine program $p$ and input $x$, design another program $X$ that on any input $i$ first runs $p$ on $x$, and if this halts, then outputs $1$. So $X$ is equivalent to the always-output-$1$ program if and only if $p$ halts on input $x$. So if we could compute equivalence, then we could decide the halting problem.

But now I claim more, that the equivalence problem is actually strictly harder than the halting problem. Thus, even if you had an oracle for the halting problem, you still couldn't compute whether two programs are equivalent.

Theorem. The equivalence problem is $\Pi^0_2$-complete. Thus, it is Turing equivalent to the double jump $0''$, or in other words, to the halting problem relativized to an oracle for the halting problem.

Proof. First, note that the equivalence of two programs $p$ and $q$ is a $\Pi^0_2$ assertion, since they are equivalent just in case $\forall i\forall s\exists t$ (if $p(i)$ halts in $s$ steps, then $q(i)$ halts in $t$ steps, with the same output, and vice versa). This assertion has complexity $\Pi^0_2$. One can restrict to the class of decision problems, as in the question, without increasing complexity, since it is a $\Pi^0_1$ assertion about a program $p$ to say that it is a decision problem program, namely, assert that every halting computation according to $p$ gives output either $0$ or $1$.

Conversely, suppose that $\forall n\exists k\varphi(n,k)$ is a given $\Pi^0_2$ assertion, where $\varphi$ has only bounded quantifiers. Let $p$ be the program which on input $n$ searches for a value of $k$ for which $\varphi(n,k)$, and outputs $1$ when such a $k$ is found. Thus, this program is equivalent to the always-output-$1$ program just in case the given $\Pi^0_2$ assertion is true. So we can computably reduce instances of $\Pi^0_2$ truth to the equivalence problem, and so the equivalence problem is $\Pi^0_2$-complete. QED

share|improve this answer

[Edited in light of Joel Hamkins's correction] The nonexistence of an equivalence-checking algorithm follows from Rice's Theorem, whose intuitive content is that no property of the function computed by a program is decidable as a predicate of the program (except, of course, the "always true" and "always false" properties).

share|improve this answer
1  
+1. But I think your intuitive description of Rice's theorem, "no run-time property of programs is decidable," is not accurate, since of course we can decide many run-time properties of programs, such as whether a program halts on input 0 in 20 steps or less or whether the head ever changes direction in the first 100 steps on inputs up to 100. But of course what you mean is that Rice's theorem says that no nontrivial property of computable functions is decidable from the programs. That is, we should speak of properties of the functions the programs compute rather than properties of programs. –  Joel David Hamkins Apr 17 '13 at 13:00

Can every positive even integer be written as a sum of two prime numbers? We certainly expect so but do not expect a definitive proof any time soon (or perhaps ever), even though we expect that for all $k$ there is an $N$ so that every even integer greater than $N$ can be expressed as such in over $k$ ways.

Suppose that $X$ always outputs $1$ immediately without even checking the input $i \ge 2$ and $Y$ takes input $i \ge 2$ and outputs $1$ or $0$ according as $2i$ is or is not a sum of two primes, so $Y$ halts for each output in a well behaved bounded time and usually (we expect) quite quickly . Are they equivalent? We don't expect an answer any time soon.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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