Please don't be offended by this, but you're being myopic. The example I
gave with bounded for loops was off the top of my head, and was simply to
illustrate a SINGLE CLASS of software that can be solved. There are all
sorts of other categories that can be solved; the fact that I did not
enumerate them does not mean they do not exist. So don't cite that one
example as being the sum total of all possible software that can be proven.
All it means is that I haven't spent enough time on the subject to list
other possibilities; but this thread is only two hours old, so what do you
want? I'll invent the entire field of mathematics in my next post.
Here's a question: you're handed a function along with a proof that the
upper bound on the running time is n^2 and the average running time is n log
n. Has the halting problem been solved for this function? YES! And here's
the shocker: that proof (for Quicksort) can be verified by a machine! Are
you going to claim that Quicksort is not a useful function?
Another question: have you EVER written a program for which you did not know
the running time? Because any person who tries to ship a program (and we're
assuming here that the software WILL be shipped to a great many users)
without knowing if there are (undesired) infinite loops in the code is
simply irresponsible. The point being that programmers are solving the
halting problem for their algorithms ALL THE TIME. That's why we care so
much about big-oh -- it not only tells us what the answer to the halting
problem is, but it also tells us how long we can expect to wait!
If we want to be really strict, we should simply require that for every
program written, the programmer should also write a proof describing the
running time of the code, memory utilization, etc. Which programmers should
do anyway, so this would just enforce good practice. But that's probably
asking too much. After all, I shouldn't talk; I don't write proofs for my
code. At least, not *rigorous* proofs. But I CAN give you upper bounds,
which is all I need to be able to say that I've solved the halting problem.
Undecidablity proofs are interesting in that they tell us the LIMITS of what
can be done. They don't tell us about what NORMALLY can be done.
As for the automatic downloading of software; god help us when our computers
start downloading code without our permission. But if we want them to do
that, then we sure better put restrictions on what can run; and I, for one,
would be very happy to ban web servers and other infinite loops from my
machine, even if it means that I lose out on the occasional "useful"
program.
--Guy
-----Original Message-----
From: Mike Schiraldi [mailto:[EMAIL PROTECTED]]
Sent: Friday, May 11, 2001 4:46 PM
To: [EMAIL PROTECTED]
Subject: Re: [freenet-tech] Off-Topic: Ideas for a FreeNet Process
> One would assume that the software was not downloaded automatically. A
> person, somewhere, decided that he/she wanted the software to begin with.
I thought that the whole point of this proposal was that the software
actually was downloaded automatically, without any action or notification of
the owner of the machine -- an extension of the Freenet "nobody knows
exactly what's stored on their node" philosophy to "nobody knows exactly
what's running on their node".
Stefan brought up the difficulty of preventing endless loops or other
resource hogs, and JF's proposed solution was to scan code before running
it. But as the record player stories in "Godel, Escher, Bach" brilliantly
illustrate, that approach cannot succeed.
Your scanner can always be tricked, it's a mathematical fact, unless you
restrict code to the kind of bounded loops you brought up. But if you only
run bounded-loop code, you're shutting out virtually all useful
programs. Anything that acts like a server. Anything that looks like an
application -- imagine if Microsoft Word said, "Sorry, i'm only allowed to
loop one more time before i have to terminate. Oops, there it goes. Bye!"
However, just because the scanner approach can't work, all is not lost.
A task scheduler might work. Let a subprocess run for a set amount of time,
then swap it out. And like Freenet's "cache data closer and closer to the
requesters" policy, such a network could move the process closer and closer
to the person who's running it -- that way, someone who tries to DOS the
network with hundreds of little dumb programs will find those little dumb
programs moving closer and closer, until only the nearest node is dragged to
a halt.
--
Mike Schiraldi
Verisign Applied Research
_______________________________________________
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
