home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / cplus / 16502 < prev    next >
Encoding:
Text File  |  1992-11-18  |  2.2 KB  |  52 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!mcsun!news.funet.fi!network.jyu.fi!sakkinen
  3. From: sakkinen@jyu.fi (Markku Sakkinen)
  4. Subject: Re: self-reproducing C++ program
  5. Message-ID: <1992Nov18.113006.12935@jyu.fi>
  6. Organization: University of Jyvaskyla, Finland
  7. References: <1919@alcbel.be> <DECHC00.92Nov17210448@tohi.DMI.USherb.Ca> <c164-aa.722076580@po.berkeley.edu>
  8. Date: Wed, 18 Nov 1992 11:30:06 GMT
  9. Lines: 41
  10.  
  11. In article <c164-aa.722076580@po.berkeley.edu> c164-aa@po.berkeley.edu (Paul DuBois) writes:
  12. >dechc00@tohi.DMI.USherb.Ca (CHRISTIAN DECHAMPLAIN) writes:
  13. >
  14. >>Is that an undecidable problem.  The type of problem you waiste your life
  15. >>trying to solve only to finaly discover it is undecidable.
  16. >
  17. >I think not -- assuming a self-reproducing program of finite size exists,
  18. >one can surely generate all possible inputs to a compiler of equal
  19. >or lesser size.  If an input compiles (!), testing for self-reproduction
  20. >is easy (diff).
  21. >
  22. >An example has been given, therefore the assumption is valid.  QED.
  23.  
  24. There is one possible problem, though.
  25. When you start generating all possible legal C++ programs
  26. in the order of ascending length, before the first self-reproducing
  27. one you might run into an item about which you can prove _neither_
  28. of the following alternatives:
  29.  
  30. 1. It terminates (i.e., in finite time you can see whether it
  31.    is self-reproducing or not).
  32.  
  33. 2. It does not terminate (BTW, if it will certainly perform
  34.    no further output after reproducing itself, it should qualify).
  35.  
  36. 3. Its output is different from its source, whether it terminates or not.
  37.  
  38. This situation does not seem likely, especially since the halting
  39. theorem does not apply directly:  it says that a _fixed program_
  40. cannot decide about all possible programs whether they are terminating
  41. or not.  Here we are allowed to use any ways and means of reasoning.
  42.  
  43. ----------------------------------------------------------------------
  44. Markku Sakkinen (sakkinen@jytko.jyu.fi)
  45.        SAKKINEN@FINJYU.bitnet (alternative network address)
  46. Department of Computer Science and Information Systems
  47. University of Jyvaskyla (a's with umlauts)
  48. PL 35
  49. SF-40351 Jyvaskyla (umlauts again)
  50. Finland
  51. ----------------------------------------------------------------------
  52.