Re: Unpredictable programming

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Thu, 29 Jun 2006 07:36:29 GMT
Message-ID: <1qLog.3563$pu3.87190_at_ursa-nb00s0.nbnet.nb.ca>


Marshall wrote:
> 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
> individual
> 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

Original text of this message