Re: Super Lint (was: Unexecutable Stack / Buffer Overflow Exploits...)

[Martin Dalecki <dalecki at cs dot net dot pl>]

Oliver Xymoron wrote:
> 
> On Mon, 3 Jan 2000, Martin Dalecki wrote:
> 
> [I wrote:]
> > > Yes, but most of the well defined sets aren't interesting. Godel's theorem
> > > tells us this. The sets are all too simple to encompass the rules of
> > > arithmetic or recursion. See also the busy beaver problem for examples of
> >
> > Goedel tells you about axiomatic systems which encompass both ARITHMETIC
> > and RECURSION.
> 
> Actually, recursion is sufficient to model arithmetic. There's a nice set
> theory representation of integers that looks something like this: {} {{}}
> {{{}}{}} {{{{}}{}}{}}. As for needing infinite space or storage to be
> theoretically intractible, there are far more possible machine states in
> even the most modest computer than you can ever hope to build a state
> transition table for.

You are talking about the classical set-theory construction of natural
numbers from Kuratowski (found in "Teoria Mnogości" from him. There is
an english translation called "The Set Theory")... You still need
boolean algebra of set's additinally in the 
construction <------ and this is arithmetic!

As it goes about infinity: In this universe any discrete machine will
only apprioximate it, since there is only a finite number of atoms
out there as an upper limit on memmory.... so real computers (JvN kind
of)
are really not quite Turing machines...

> > And in practical cases in CAN BE PROVEN THAT PROGRAMMS DON'T CONTAIN
> > POSSIBLE OVERFLOWS. Like in the following example:
> >
> > int main(int argc, char *argv[] )
> > {
> >       return 0;
> > }
> 
> Yes, but that is clearly in the set of uninteresting programs. Programs
> that are interesting do things like parse email addresses or HTML. They
> tend not to be very simple (or correct).
> 
> Consider the difficulty a C compiler has dealing with detecting pointer
> possible aliasing and you'll see that static analysis of code paths is a
> pain at best.

Yeah of course they are comlex, but still Goedels theorem is just
an utterly wrong argument for impossiblity at this place.

--
	Marcin Dalecki