Re: Ants, trees, etc.

[David Klotz <bucky () speakeasy org>]

The halting problem essentially says you can't write a general program which
will verify whether ALL programs will halt or not (when using a computer with
infinite memory by the way).  While not an expert on this,
I suspect you could also use it to formally prove you can't write a general
algorithm that determines if ANY two programs behave the same on ALL input.

However, I don't believe it prohibits you from writing an algorithm which takes
two simple pieces of code, some static set of input, and seeing if the code
behaves the same on that input.  If it did, I don't think we could do any
automated code analysis, no?


--
-bucky () speakeasy org

On Wed, 22 Jun 2005, dvorak wrote:

> On Wed, Jun 22, 2005 at 02:44:24PM +0200, Jonatan B wrote:
> > > To score, I'd run a quick algo across each block, and if it does what
> > > "primary" (original) block does (according to the emulator), then it
> > > would have a higher score.
> >
> > If I understood what you wrote correctly, then verifying that these two
> > blocks of code yields the same result when given the same input means
> > solving the halting problem.
>
> First of all i might be talking out of my uhm bottom, but i never understand
> the references to the halting problem that are throw around very often.
> As i understand the halting problem basicly states:
_______________________________________________
Dailydave mailing list
Dailydave () lists immunitysec com
https://lists.immunitysec.com/mailman/listinfo/dailydave