Re: Cryptography and P=NP

Article View: sci.crypt

Article #1962

#1962

From: Jamie Andrews
Date: Fri, 20 Nov 1992 17:45

20 lines
1370 bytes

In article <722206613@pike.cs.duke.edu> srt@duke.cs.duke.edu (Stephen R. Tate) writes:
>Huh?  I can think of very, very few algorithms (programs) that can not
>be counted on to halt.  The only simply stated one has the halting problem:
>given a program, decide whether or not it will ever halt.

     What about: any interpreter for a non-trivial programming
language?  This includes "sh", "csh", "perl", Emacs, and any
Lisp, Prolog, Smalltalk, or Basic interpreter...

> To re-iterate:  programs that cannot
>be counted on to halt are very, very, very rare.  Most people will never
>see one.

     Well, I work with them every day, and I would bet that you
do too.  I even write such programs sometimes, which is more
rare but certainly not uncommon.

--Jamie.
  jamie@cs.sfu.ca
"The Tao's net encompasses the whole universe."  - tao te ching

Technical Details

Message-ID: <1992Nov20.174549.25343@cs.sfu.ca>

Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!destroyer!cs.ubc.ca!fornax!jamie

References: <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com> <722206613@pike.cs.duke.edu>

Show Full Headers

Complete Article Headers

Newsgroups: sci.crypt,sci.math,comp.theory
Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!destroyer!cs.ubc.ca!fornax!jamie
From: jamie@cs.sfu.ca (Jamie Andrews)
Subject: Re: Cryptography and P=NP
Message-ID: <1992Nov20.174549.25343@cs.sfu.ca>
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
References: <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com> <722206613@pike.cs.duke.edu>
Date: Fri, 20 Nov 1992 17:45:49 GMT
Lines: 20

Reply to Parent Message