Re: Unpredictable programming

From: Bob Badour <>
Date: Thu, 29 Jun 2006 07:36:29 GMT
Message-ID: <1qLog.3563$>

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