home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10287 < prev    next >
Encoding:
Text File  |  1992-08-14  |  2.2 KB  |  48 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!stanford.edu!snorkelwacker.mit.edu!galois!zermelo!jbaez
  3. From: jbaez@zermelo.mit.edu (John C. Baez)
  4. Subject: Re: Puzzles
  5. Message-ID: <1992Aug14.192710.22383@galois.mit.edu>
  6. Sender: news@galois.mit.edu
  7. Nntp-Posting-Host: zermelo
  8. Organization: MIT Department of Mathematics, Cambridge, MA
  9. References: <1992Aug13.130820.313@csc.canterbury.ac.nz> <1992Aug13.172531.10744@galois.mit.edu> <israel.713746423@unixg.ubc.ca>
  10. Date: Fri, 14 Aug 92 19:27:10 GMT
  11. Lines: 35
  12.  
  13. In article <israel.713746423@unixg.ubc.ca> israel@unixg.ubc.ca (Robert B. Israel) writes:
  14. >In <1992Aug13.172531.10744@galois.mit.edu> jbaez@nevanlinna.mit.edu 
  15. >(John C. Baez)writes:
  16. >
  17. >>Some kind soul pointed out that one needn't write a program in C that
  18. >>can accept and run C programs to get the job done. Let me give away the
  19. >>answer to the problem (how to prove the "almost-paradox" A-P above).
  20. >  
  21. >>One need only write
  22. >>a program that looks through statements in ZFC to find those of the form
  23. >>"N cannot be printed by a program in C of length < E", and check
  24. >>which are provable in ZFC.  If it finds one, the program should print
  25. >>out the number N.
  26. >
  27. >Well, if you can write a program that checks whether a statement is
  28. >_provable_ (and terminates in finite time if it isn't), then by Godel's
  29. >Theorem ZFC is inconsistent!  What you want your program to do is look
  30. >through all strings until it finds a _proof_ in ZFC that ends with
  31. >a statement of the form "N cannot be printed by a program in C of length < E",
  32. >and then print N.  If this program prints out N, then it is a counterexample
  33. >to the proof.  I might point out that, in concluding that no such proof
  34. >exists, we are using the consistency of ZFC, which is not part of ZFC itself.
  35. >If ZFC were inconsistent, every statement would be provable in it.
  36.  
  37. Thanks for correcting my sloppy wording.
  38.  
  39. >Your _program_ needn't be able to run C programs, but your statement
  40. >"N cannot be printed by a program in C of length < E" is really an abbreviation
  41. >for a very long formal statement in ZFC, which must contain a description of
  42. >the C language and how programs will be run.
  43.  
  44. That's true.  
  45.  
  46. What I'd really like (as I keep hinting) are some good estimates for the
  47. magic constant E!
  48.