Re: Unpredictable programming
Date: Thu, 29 Jun 2006 07:36:29 GMT
> Bob Badour wrote:
>>However, I suspect >>the task of recognizing the equivalence of any two arbitrary algorithms >>is probably close to the complexity of the halting problem.
> In both cases, the problem is in general undecidable. Of course
> instances of the problem may be decidable.
That's what I thought. I figured if I dug around in Turing's or Church's old stuff I would find some famous proof of it. However, I couldn't be bothered with the digging. Received on Thu Jun 29 2006 - 09:36:29 CEST