home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5059 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  1.4 KB
  1. Xref: sparky sci.crypt:5059 sci.math:15285 comp.theory:2484
  2. Newsgroups: sci.crypt,sci.math,comp.theory
  3. Path: sparky!uunet!mcsun!sun4nl!ruuinf!piet
  4. From: piet@cs.ruu.nl (Piet van Oostrum)
  5. Subject: Re: Cryptography and P=NP
  6. Sender: network-news@cs.ruu.nl
  7. Message-ID: <1992Nov20.090548.5840@cs.ruu.nl>
  8. In-Reply-To: lwloen@rchland.vnet.ibm.com (Larry Loen)
  9. Date: Fri, 20 Nov 1992 09:05:48 GMT
  10. Reply-To: piet@cs.ruu.nl (Piet van Oostrum)
  11. References: <1992Nov16.084503.10141@vax.oxford.ac.uk> <BxvEF3.Kqw.2@cs.cmu.edu> <1992Nov18.193900.20199@rchland.ibm.com> <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com>
  12. Organization: Dept of Computer Science, Utrecht University, The Netherlands
  13. Followup-To: sci.crypt
  14. Lines: 18
  15.  
  16. >>>>> lwloen@rchland.vnet.ibm.com (Larry Loen) (LL) writes:
  17.  
  18. LL> Surely, it can't be this easy.  I get squeamish whenever I see clocks and
  19. LL> numbers on arguments of this kind.  Is the cardinality of the set of
  20. LL> P algorithms == number of natural numbers? 
  21.  
  22. The set of all programs is countable. Each program is just a (finite)
  23. string in a programming language (e.g. Turing machines), and the set of
  24. finite strings over a finite alphabet is countable (order the strings
  25. lexicographically).
  26.  
  27. LL>  Why doesn't Cantor's diagonal
  28. LL> argument crop up somewhere and spoil everything?  (I don't necessarily mean
  29. LL> the original, but an appropriate analog of it).
  30.  
  31. Why should it?
  32. -- 
  33. Piet van Oostrum <piet@cs.ruu.nl>
  34.