home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2510 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  1.0 KB
  1. Xref: sparky comp.theory:2510 comp.lang.functional:1390
  2. Newsgroups: comp.theory,comp.lang.functional
  3. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!darwin.sura.net!Sirius.dfn.de!hpux.rz.uni-jena.de!mwj
  4. From: mwj@rz.uni-jena.de (Johannes Waldmann)
  5. Subject: complexity measures for the lambda calculus?
  6. Message-ID: <1992Nov23.082459.24583@rz.uni-jena.de>
  7. Organization: Friedrich-Schiller-University Jena, Germany
  8. Date: Mon, 23 Nov 1992 08:24:59 GMT
  9. Lines: 12
  10.  
  11. How can I measure the complexity of computations in the lambda
  12. calculus? Of course I could chose an evaluation strategy,
  13. simulate everything on a Turing machine and apply housekeeping
  14. there. But that's not what I want. I thought of counting the
  15. minimal number of beta reductions (that a given expression needs 
  16. to reach normal form). One could allow parallel reductions (of redexes
  17. not contained in each other)... Has there been work on this field,
  18. is it considered useful? Any hints, pointers to the literature
  19. etc would be appreciated. 
  20.  
  21. I will summarize if I get enough email responses. --- Johannes.
  22.  
  23.