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>
>
> In both cases, the problem is in general undecidable. Of course
> individual
> instances of the problem may be decidable.
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