Time is a very good indicator of failure.
If things did not time out the whole internet would be deadlocked in a day.
HKF
----- Original Message -----
From: "Guy Smith" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Friday, May 11, 2001 3:31 PM
Subject: RE: [freenet-tech] Off-Topic: Ideas for a FreeNet Process
> Right on. It is absolutely true that you cannot solve the halting problem
> under ALL possible cases; but there are PLENTY of cases in which it can be
> solved. In fact, every time a program is run the halting problem is
> implicitly being tested. If you have to hit Ctrl-C, you don't learn
> anything; but if you DON'T hit Ctrl-C, and the program DOES terminate, you
> have just empirically answered the halting problem for your particular
case.
>
> The problem is that some people are looking at this from a pure,
> mathematical point of view, while others are looking at it from a
practical
> point of view. However, even from a pure mathematical point of view, you
> can identify categories of programs that will terminate. For example:
>
> for (i = constant_1; i < constant_2; ++i)
> {
> do_some_function_that_is_already_known_to_run_in_constant_time();
> }
>
> terminates for all constant_1 and constant_2 where constant2 - constant1
!=
> infinity.
>
> You can see that this can nest and be used to show that ANY program
> consisting of nested for-loops defined with constants will terminate.
>
> This is NOT a general solution to the halting problem, but can apply to a
> large enough class of programs to have PRACTICAL value.
>
> So like I said, if you decide to limit yourself to only run programs that
> you can prove can halt, you don't have a problem. You've left out a large
> class of programs that you can't prove (like the clever is_perfect example
> described earlier), but you've gained the security of a provably safe
> program (from one particular definition of the word "safe"). When someone
> gives you a program that can't be proven to halt or is undecidable, you
> reject the program.
>
> --Guy
>
> -----Original Message-----
> From: JF [mailto:[EMAIL PROTECTED]]
> Sent: Friday, May 11, 2001 3:19 PM
> To: [EMAIL PROTECTED]
> Subject: Re: [freenet-tech] Ideas for a FreeNet Process
>
>
> I beleve the word impossible was used.
> There is nothing ridiculous about it.
> Every second of the day other prorams are determining whether or not other
> programs are functioning correctly.
> I recently wrote a program to monitor another program that ran in a public
> place. If a thread froze the monitor knew it and restarted the process.
>
> By issuing the impossible challenge, I simply have to come up with one
case
> to dispell the impossible and therefore make it possible.
>
> The fact is that if a node is not behaving in the required specs then
other
> nodes can agree not to use itor disregard it entirely. Its very simple.
>
> HKF
> ----- Original Message -----
> From: "Stefan Reich" <[EMAIL PROTECTED]>
> To: <[EMAIL PROTECTED]>
> Sent: Friday, May 11, 2001 3:13 PM
> Subject: Re: [freenet-tech] Ideas for a FreeNet Process
>
>
> > Come on... this is getting slightly ridiculous. It's a proven fact that
> you
> > can't write an algorithm that determines if _any_ given program
> terminates.
> >
> > Giving me two concrete programs doesn't prove anything. Your P2 has to
> give
> > the correct answer for every possible P1.
> >
> > There's no "myth" to be dispelled; it's a theorem that's been proven
> > mathematically.
> >
> > -Stefan
> >
> > ----- Original Message -----
> > From: "JF" <[EMAIL PROTECTED]>
> > To: <[EMAIL PROTECTED]>
> > Sent: Friday, May 11, 2001 9:05 PM
> > Subject: Re: [freenet-tech] Ideas for a FreeNet Process
> >
> >
> > > No prob.
> > > Dispelling myths is part of hacking.
> > > I gave Steven 2 programs.
> > > one that would run in an infinite loop and one that would determine if
> the
> > > first on would run in an infinite loop.
> > >
> > > Its the examination of these rules that will make things secure do
> > > tongue-in-cheek at will.
> > >
> > > HackerKungFu
> > >
> > > ----- Original Message -----
> > > From: "Guy Smith" <[EMAIL PROTECTED]>
> > > To: <[EMAIL PROTECTED]>
> > > Sent: Friday, May 11, 2001 2:56 PM
> > > Subject: RE: [freenet-tech] Ideas for a FreeNet Process
> > >
> > >
> > > > Actually, the halting problem is undecidable in the *general* case.
> > There
> > > > are plenty of special cases in which it can be decided. If you
limit
> > > > yourself to only accepting code that falls within these special
cases,
> > > > you're fine. Sure, you restrict yourself to only a subset of all
> > possible
> > > > software, but you gain a rigorous proof that the software will halt
> (or
> > > > not).
> > > >
> > > > Not that this really applies to what was a tongue-in-cheek comment.
> > > >
> > > > --Guy
> > > >
> > > > -----Original Message-----
> > > > From: Stefan Reich [mailto:[EMAIL PROTECTED]]
> > > > Sent: Friday, May 11, 2001 2:34 PM
> > > > To: [EMAIL PROTECTED]
> > > > Subject: Re: [freenet-tech] Ideas for a FreeNet Process
> > > >
> > > >
> > > > > > Not a problem; just write a function that can scan any arbitrary
> > piece
> > > > of
> > > > > > code and determine whether it will eventually halt or not.
> > > > >
> > > > > Right in other words, the freenet could determine cancer nodes and
> > deal
> > > > with
> > > > > them.
> > > >
> > > > Ahm... I think you missed out on the irony in that statement... it
is
> > > > IMPOSSIBLE to write an algorithm that decides if a given piece of
code
> > > will
> > > > halt eventually (i think Turing proved that).
> > > >
> > > > I think you still don't understand the problem with the execution of
> > > > untrusted code (is it so unobvious?).
> > > >
> > > > -Stefan
> > > >
> > > >
> > > > _______________________________________________
> > > > freenet-tech mailing list
> > > > [EMAIL PROTECTED]
> > > > http://lists.freenetproject.org/mailman/listinfo/tech
> > > >
> > > > _______________________________________________
> > > > freenet-tech mailing list
> > > > [EMAIL PROTECTED]
> > > > http://lists.freenetproject.org/mailman/listinfo/tech
> > > >
> > >
> > > _______________________________________________
> > > freenet-tech mailing list
> > > [EMAIL PROTECTED]
> > > http://lists.freenetproject.org/mailman/listinfo/tech
> >
> >
> > _______________________________________________
> > freenet-tech mailing list
> > [EMAIL PROTECTED]
> > http://lists.freenetproject.org/mailman/listinfo/tech
> >
>
> _______________________________________________
> freenet-tech mailing list
> [EMAIL PROTECTED]
> http://lists.freenetproject.org/mailman/listinfo/tech
>
> _______________________________________________
> freenet-tech mailing list
> [EMAIL PROTECTED]
> http://lists.freenetproject.org/mailman/listinfo/tech
>
_______________________________________________
freenet-tech mailing list
[EMAIL PROTECTED]
http://lists.freenetproject.org/mailman/listinfo/tech
