home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / talk / origins / 14535 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  4.7 KB
  1. Path: sparky!uunet!gatech!nscf!lakes!kalki33!system
  2. From: kalki33!system@lakes.trenton.sc.us
  3. Newsgroups: talk.origins
  4. Subject: Re: Laying a trap
  5. Keywords: Computer program, random, mutation, chess
  6. Message-ID: <c28HuB7w165w@kalki33>
  7. Date: Thu, 19 Nov 92 15:56:47 EST
  8. References: <1992Nov18.133247.8546@city.cs>
  9. Reply-To: kalki33!system@lakes.trenton.sc.us
  10. Organization: Kalki's Infoline BBS, Aiken, SC, USA
  11. Lines: 100
  12.  
  13. lionel@cs.city.ac.uk (Lionel Tun) writes:
  14.  
  15. > Lets say there is a computer program which `knows' the
  16. > legal moves of chess - lets call it ChessMover.
  17. > ChessMover plays very poor chess because its moves are
  18. > made at random. But it does play very fast. ChessMover
  19. > is small, compact and extremely efficient. But it plays
  20. > bad chess because it has not been designed with any
  21. > chess playing algorithms at all.
  22. > 
  23. > Would it be possible to subject ChessMover to random
  24. > mutations, so that eventually you evolve ChessPlayer,
  25. > a chess program which plays very well, say at master
  26. > level?
  27.  
  28. > For those of you who are not game fans, but more business
  29. > oriented:
  30. > Consider a spreadsheet program such as Lotus123 or
  31. > QuattroPro. Lets say you have a small calculator program,
  32. > like the toy ones which pop up in some windowing front
  33. > ends. Would it be possible to apply random mutations to
  34. > Calculator until it evolves into Spreadsheet?
  35.  
  36. > Please note, both Calculator and ChessMover are small (by
  37. > today's standard) programs, lets say about 2 to 4K for the
  38. > executable. Shreadsheet and ChessPlayer must obviously be
  39. > of a more substantial size (I can't remember how big Lotus
  40. > is). If you like, you can randomly modify the source code
  41. > and compiler, rather than the executables, if you think this
  42. > will make it less brittle. Random modification includes of
  43. > course random additions. You might prefer the source code
  44. > approach as the compiler will reject programs which will
  45. > not even compile, let alone run. If you wish to modify
  46. > the compiler, you can keep a copy of the old compiler to 
  47. > compile it with.
  48.  
  49. These questions are testable in the following sense:
  50.  
  51. 1) Design a universal Turing machine with a particular symbol set, say
  52. the binary set {0,1}.
  53.  
  54. 2) Write a simple program that works (i.e. the machine halts in a finite
  55. number of steps).
  56.  
  57. 3) Subject this program (i.e the program's bit-string) to a series of
  58. "random" mutations that flip bits (change a "1" to a "0" or a "0" to a
  59. "1"), or that add/delete bits at the end (or the beginning) of the
  60. string, or that add/delete substrings, etc... (there are so many
  61. possibilities!)
  62.  
  63. 4) After each mutation, try running the mutated bit string as a program
  64. in the universal Turing machine and observe the results. If the program
  65. is correct (i.e. the machine eventually halts) call this an "admissible
  66. intermediate form" and examine it further to determine just what the
  67. mutated program is doing. If the program doesn't work (i.e. the machine
  68. never halts) then count it as an "evolutionary dead end" and either
  69. allow it to mutate further or discard it and start over from the most
  70. recent admissible intermediate form.
  71.  
  72. 5) If you are not sure whether the machine will eventually halt, then
  73. attempt to dissect the code to determine if it represents a valid
  74. algorithm or not.
  75.  
  76. 6) After a number of trials (probably trillions and trillions), see if
  77. you ever come up with the complete source code for a fantastically
  78. complex purposeful application (designed for the Turing environment of
  79. course, so maybe no video!).
  80.  
  81. Many additional conditions will have to be dealt with, such as:
  82.  
  83. a) the choices of starting strings, their length and bit sequence.
  84.  
  85. b) how many unsuccessful mutations are we willing to allow before we
  86. discard a string as an evolutionary dead end?
  87.  
  88. c) how do we deal with admissible intermediate forms which, although
  89. they are valid algorithms, do not appear to compute anything "useful"?
  90.  
  91. d) should we allow the machine itself to mutate (i.e. randomly change
  92. its next-move function or its transition table)?
  93.  
  94. e) should there be a limit on the allowed size of a string?
  95.  
  96. f) what about programs which are self modifying? In this case, the new
  97. string is not the result of mutation, but it has changed.
  98.  
  99. Sincerely,
  100. Kalki Dasa
  101.  
  102.  
  103.  
  104.        -------------------------------------------------------
  105.       |  Don't forget to chant:   Hare Krishna Hare Krishna   |
  106.       |                           Krishna Krishna Hare Hare   |
  107.       |                           Hare Rama Hare Rama         |
  108.       |                           Rama Rama Hare Hare         |
  109.       |                                                       |
  110.       |   Kalki's Infoline BBS Aiken, South Carolina, USA     |
  111.       |        (kalki33!kalki@lakes.trenton.sc.us)            |
  112.        -------------------------------------------------------
  113.