home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / c / 16268 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  1.7 KB
  1. Xref: sparky comp.lang.c:16268 comp.lang.c++:16015 comp.lang.pascal:6453 comp.lang.misc:3566
  2. Newsgroups: comp.lang.c,comp.lang.c++,comp.lang.pascal,comp.lang.misc
  3. Path: sparky!uunet!mcsun!sun4nl!sci.kun.nl!cs.kun.nl!hansm
  4. From: hansm@cs.kun.nl (Hans Mulder)
  5. Subject: Re: Godel's Proof (was Re: Software design =/= Programming)
  6. Message-ID: <BxHz2v.EK4@sci.kun.nl>
  7. Sender: news@sci.kun.nl (NUnet News Owner)
  8. Organization: University of Nijmegen, The Netherlands
  9. References: <josef.720690811@uranium>     <1992Nov04.073218.11970@cadlab.sublink.org>     <1dcuutINNi8t@agate.berkeley.edu> <1992Nov8.031423.16207@ucc.su.OZ.AU>     <1992Nov9.144550.28811@us-es.sel.de> <LOEGEL.92Nov9134531@fegatello.ssc.gov>
  10. Date: Tue, 10 Nov 1992 11:11:18 GMT
  11. Lines: 26
  12.  
  13. In <LOEGEL.92Nov9134531@fegatello.ssc.gov> loegel@fegatello.ssc.gov (George J. Loegel) writes:
  14. >From the McGraw-Hill Dictionary of Science and Technology:
  15. >Godel's Proof: Any formal arithmetical system is incomplete in the
  16. >sense that, given any consistent set of arithmetical axioms, there are
  17. >true statements in the resulting arithmetical system that cannot be
  18. >derived from these axioms.
  19. >--- end of def ---
  20.  
  21. This is inaccurate.  Counterexample:
  22.  
  23. Axioms: all closed first-order arithmetical formulae that are true when
  24.         interpreted w.r.t. the natural numbers.
  25. Rules of inference: none needed.
  26.  
  27. This formal system is consistent, since there no formulae F s.t. both F
  28. and ~F are true.  It is complete, since there are no _closed_ formulae F
  29. s.t. neither F nor ~F is true.
  30.  
  31. It doesn't fall for G\:odel's Theorem because it is not semi-decidable,
  32. i.e. for a given formula F one cannot (in general) decide whether it is
  33. an axiom in this system.
  34.  
  35. --
  36. Hope this helps,
  37.  
  38. Hans Mulder                hansm@cs.kun.nl
  39.