On Fri, 20 Dec 1996 Sean Hastings <whysean@earthlink.net> Wrote:
>There have been computers turned loose on problems that were
>thought to be non-deterministic, like proving Fermat's
>theorem. And Viola! after the N zillionth step they stopped
>with a solution.
After three hundred years of effort Fermat's Last Theorem was proved the old
fashioned way, with pencil and paper, but it's true that the equally famous
4 color map problem was proved by a computer
>Someone probably has one running right no to prove that no
>even number greater than 4 is not the sum of two primes.
It's more likely that a computer will find a counterexample, that is,
by trial and error find an even number that is not the sum of 2 primes.
You can't prove there is no such number by trial and error, there are too
many even numbers for that. To prove there is no such number you need a proof.
Even if we are someday able to solve this problem, we know for sure there are
other problems we can not solve, and to make things even worse, we have no
way of knowing what those problems are.
On Sat, 21 Dec 1996 James Rogers <jamesr@best.com> Wrote:
>As I stated previously, our real problem isn't in our
>understanding of computers, but in our ability to determine
>whether or not a problem has a deterministic solution before
>trying it on a computer.
In other words, in general there is no way to understand if a computer can
solve the problem we give it or not.
>The length required to complete a computation is not a
>problem of the computer design, but of our unwillingness to
>wait for the computation to complete.
But we might be waiting, not for a long time, but quite literally forever.
Unlike a something like factoring a number, where it's easy to find an upper
bound on the amount of computer time needed to find a solution, with some
problems the only upper bound we can find is infinity. It could be that it's
futile to keep waiting for an answer, but there is no way we can ever know
it's futile, so we end up running the program forever.
John K Clark johnkc@well.com
-----BEGIN PGP SIGNATURE-----
Version: 2.6.i
iQCzAgUBMr12rX03wfSpid95AQFFjQTw6K0hwnmeKdYlCcXYW0U433rA1+CHf6nq
933t1cXJMcVnMv9Us63EWPu5HkYUUqAAqyVqXS2y89MJdSYm7K2osVFbPlm7dd6f
Qs1jTFaCMaCMJlHVUdkFRB3qGJOib9KmBzALnfNmWdfaqZ2yMPcab8x1NwW6mvw/
6qjHBFdidSm6w2IzosI+/pon5HbWeQUN6eUCvl1gAXH+wzBmzqc=
=HmKE
-----END PGP SIGNATURE-----