Dailydave mailing list archives
Re: Ants, trees, etc.
From: David Klotz <bucky () speakeasy org>
Date: Wed, 22 Jun 2005 12:50:28 -0700 (PDT)
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
Current thread:
- Ants, trees, etc. Dave Aitel (Jun 21)
- Re: Ants, trees, etc. Jonatan B (Jun 22)
- Re: Ants, trees, etc. Dave Aitel (Jun 22)
- Re: Ants, trees, etc. dvorak (Jun 22)
- Re: Ants, trees, etc. David Klotz (Jun 22)
- Re: Ants, trees, etc. Jonatan B (Jun 23)
- Re: Ants, trees, etc. plonky (Jun 23)
- Re: Ants, trees, etc. plonky (Jun 23)
- Re: Ants, trees, etc. Jonatan B (Jun 22)