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
