home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5079 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  1.4 KB
  1. Xref: sparky sci.crypt:5079 sci.math:15301 comp.theory:2486
  2. Newsgroups: sci.crypt,sci.math,comp.theory
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!destroyer!cs.ubc.ca!fornax!jamie
  4. From: jamie@cs.sfu.ca (Jamie Andrews)
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1992Nov20.174549.25343@cs.sfu.ca>
  7. Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
  8. References: <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com> <722206613@pike.cs.duke.edu>
  9. Date: Fri, 20 Nov 1992 17:45:49 GMT
  10. Lines: 20
  11.  
  12. In article <722206613@pike.cs.duke.edu> srt@duke.cs.duke.edu (Stephen R. Tate) writes:
  13. >Huh?  I can think of very, very few algorithms (programs) that can not
  14. >be counted on to halt.  The only simply stated one has the halting problem:
  15. >given a program, decide whether or not it will ever halt.
  16.  
  17.      What about: any interpreter for a non-trivial programming
  18. language?  This includes "sh", "csh", "perl", Emacs, and any
  19. Lisp, Prolog, Smalltalk, or Basic interpreter...
  20.  
  21. > To re-iterate:  programs that cannot
  22. >be counted on to halt are very, very, very rare.  Most people will never
  23. >see one.
  24.  
  25.      Well, I work with them every day, and I would bet that you
  26. do too.  I even write such programs sometimes, which is more
  27. rare but certainly not uncommon.
  28.  
  29. --Jamie.
  30.   jamie@cs.sfu.ca
  31. "The Tao's net encompasses the whole universe."  - tao te ching
  32.