Equality of Streams is a Π02-Complete Problem

This paper gives a precise characterization for the complexity of the problem of proving equal two streams defined with a finite number of equations: Π02. Since the Π02 class includes properly both the recursively enumerable and the co-recursively enumerable classes, this result implies that one can find no mechanical procedure to say when two streams are equal, as well as no procedure to say when two streams are not equal. In particular, there is no complete proof system for equality of streams and no complete system for dis-equality of streams. 1