home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9386 < prev    next >
Encoding:
Text File  |  1992-07-21  |  2.0 KB  |  44 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!snorkelwacker.mit.edu!galois!nevanlinna!jbaez
  3. From: jbaez@nevanlinna.mit.edu (John C. Baez)
  4. Subject: Re: What more do you want?
  5. Message-ID: <1992Jul21.214221.18252@galois.mit.edu>
  6. Sender: news@galois.mit.edu
  7. Nntp-Posting-Host: nevanlinna
  8. Organization: MIT Department of Mathematics, Cambridge, MA
  9. References: <1992Jul21.190243.16846@galois.mit.edu>
  10. Date: Tue, 21 Jul 92 21:42:21 GMT
  11. Lines: 31
  12.  
  13. In article <1992Jul21.190243.16846@galois.mit.edu> tycchow@riesz.mit.edu (Timothy Y. Chow) writes:
  14.  
  15. >A [rushing in excitedly]: I've done it!  I've proved that Goldbach's
  16. >   conjecture holds for all sufficiently large even numbers!
  17. >B: Congratulations!  So now you can write a computer program to check
  18. >   all the remaining even numbers and Goldbach's conjecture will be
  19. >   completely settled, right?
  20. >A: Well, not quite...I proved that there exists a constant C beyond
  21. >   which Goldbach's conjecture holds, but I don't have any idea how
  22. >   big C is.  On the other hand, that's not a big problem, because
  23. >   C is computable.
  24. >B: You mean there's an algorithm that will give you the value of C
  25. >   explicitly?
  26. >A: Exactly.
  27. >B: So what are we waiting for?  Let's run the algorithm and compute C!
  28. >A: Well, there's a slight problem here...I just managed to prove that
  29. >   such an algorithm exists, and I don't have any idea what the algorithm
  30. >   is like.
  31. >B: Hmmm...well, maybe it's not worth running the algorithm anyway.  Do
  32. >   you have any idea how long it would take to compute C?
  33. >A: Not really, but the running time T of the algorithm is computable...
  34.  
  35. Yes, this is another great example of the slipperiness of certain
  36. notions.   We should add the following:
  37.  
  38. C: While you guys were arguing away, I just showed that there is an
  39. effective procedure for deciding whether Goldbach's conjecture is true.
  40. In fact, I have just written a program that does the job.  Actually, I
  41. wrote two programs.  Program A prints out the word "True".  Program B
  42. prints out the word "False."  One of these programs is the one that does
  43. the job.  
  44.