home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / cplus / 16529 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  1.6 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!cs.utexas.edu!sun-barr!olivea!pagesat!spssig.spss.com!hosken
  2. From: hosken@spss.com (Bill Hosken)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: self-reproducing C++ program
  5. Message-ID: <1992Nov18.201434.9706@spss.com>
  6. Date: 18 Nov 92 20:14:34 GMT
  7. References: <1919@alcbel.be> <DECHC00.92Nov17210448@tohi.DMI.USherb.Ca> <c164-aa.722076580@po.berkeley.edu>
  8. Sender: news@spss.com (Net News Admin)
  9. Organization: SPSS, Inc.
  10. Lines: 24
  11.  
  12. In article <c164-aa.722076580@po.berkeley.edu>, c164-aa@po.berkeley.edu (Paul DuBois) writes:
  13. > dechc00@tohi.DMI.USherb.Ca (CHRISTIAN DECHAMPLAIN) writes:
  14. > 
  15. > >Is that an undecidable problem.  The type of problem you waiste your life
  16. > >trying to solve only to finaly discover it is undecidable.
  17. > 
  18. > I think not -- assuming a self-reproducing program of finite size exists,
  19. > one can surely generate all possible inputs to a compiler of equal
  20. > or lesser size.  If an input compiles (!), testing for self-reproduction
  21. > is easy (diff).
  22. > 
  23. > An example has been given, therefore the assumption is valid.  QED.
  24. > --
  25. > Paul DuBois                    Permanent: pld@soda.berkeley.edu
  26. >   If you call this a short .sig, you oppose its reality.  If you do not call
  27. >   it a short .sig, you ignore the fact.  Now what do you wish to call this?
  28.  
  29.  
  30. Right, but still, the problem of finding the 'shortest program to do x'
  31. is a very hard one for almost any task x.  The exhaustive method above is
  32. clearly impractical except where the known program is very small indeed.
  33.  
  34. I don't think there are very big prizes for finding these shortest programs
  35. either.
  36.