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