home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3371 < prev    next >
Encoding:
Text File  |  1992-12-29  |  2.1 KB  |  53 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!jvnc.net!phage!boutell
  3. From: boutell@isis.cshl.org (Tom Boutell)
  4. Subject: Programming by Description of Output...
  5. Message-ID: <C01yxr.BGF@phage.cshl.org>
  6. Sender: news@phage.cshl.org
  7. Organization: Cold Spring Harbor Labs
  8. Date: Wed, 30 Dec 1992 03:27:27 GMT
  9. Lines: 42
  10.  
  11. In learning about methods of proving algorithms correct (and the
  12. various difficulties of doing same), I have come to wonder
  13. to what degree it is possible to create a language in which
  14. the programmer specifies not the steps to be accomplished
  15. but rather the goal to be achieved-in other words, whether it
  16. is possible, working from a specification of the initial state
  17. and a specification of the final state, to derive an algorithm
  18. automatically which permutes the one into the other. I suppose
  19. this is similar to other generalized AI problem-solving tasks,
  20. but a notable advantage is that the goal state is well-defined
  21. (none of the AI problems of needing to operate in non-abstract
  22. universes come into play, at least not for a decently interesting
  23. set of cases). 
  24.  
  25. Are there languages/programming systems that attempt this sort
  26. of thing? I'm sure it's impossible to guarantee a solution
  27. to every request that has a possible solution, since this would
  28. imply the ability to prove that fact, and the statement of the
  29. problem is likely to be equivalent to second-order predicate
  30. calculus, in which a proof (by resolution) cannot be guaranteed 
  31. in finite time. But if the system can recognize solved problems
  32. as subsets of the problem at hand, it can move more quickly toward
  33. assembling a solution, or deciding it's overwhelmed. 
  34.  
  35. An example of what I have in mind:
  36.  
  37. Initial state:
  38. Array A[] contains n whole numbers. 
  39. Final state:
  40. Array B[] contains n whole numbers such that each element of
  41. A[] appears in B[] and for all i such that 1<=i<n, B[i]<B[i+1].
  42.  
  43. How might the problem of calculating B[] (a sorted version of
  44. A[]) be solved in a general fashion, absent a known
  45. method of sorting?
  46.  
  47. -T
  48.  
  49. -- 
  50. Tom Boutell, boutell@cshl.org
  51.  
  52. Clausthaler is the best non - alcoholic beer in the known universe.
  53.