Re: Ben Franklin on patents

Article View: gnu.misc.discuss

Article #73464

#73464

From: Joe Wells
Date: Thu, 12 Sep 1991 00:16

21 lines
1551 bytes

In article <1991Aug30.195229.4202@craycos.com> jrbd@craycos.com (James Davies) writes:

   In article <3035@m1.cs.man.ac.uk> LeBlanc@uk.ac.mcc (A. V. Le Blanc) writes:
   >It would take an
   >incredible program to analyse any given program text in any
   >programming language, highlight a few lines, and print in
   >the message buffer, "This portion of the program implements
   >the LZW compression algorithm".

   Especially since it's undecidable (the proposed task being equivalent
   to the halting problem)....

No, this problem is even tougher than the halting problem.  The set of
programs that would violate the patent on LZW compression is not even r.e.
by Rice's Theorem (extended version).  I believe that such a set is called
"productive", but I don't have the references nearby to check.

-- 
Enjoy,

Joe Wells <jbw@cs.bu.edu>

Technical Details

Message-ID: <JBW.91Sep11201635@bigbird.bu.edu>

Path:

arc1-ca.pugleaf.net!gmdzi!unido!unidui!math.fu-berlin.de!ira.uka.de!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!uunet!bu.edu!nntp-read!jbw

References: <3035@m1.cs.man.ac.uk> <1991Aug30.195229.4202@craycos.com>

Show Full Headers

Complete Article Headers

X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 1025b4,9434f7b17f215464
X-Google-Attributes: gid1025b4,public
X-Google-ArrivalTime: 1991-09-12 05:35:15 PST
Path: arc1-ca.pugleaf.net!gmdzi!unido!unidui!math.fu-berlin.de!ira.uka.de!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!uunet!bu.edu!nntp-read!jbw
From: jbw@bigbird.bu.edu (Joe Wells)
Newsgroups: gnu.misc.discuss
Subject: Re: Ben Franklin on patents
Message-ID: <JBW.91Sep11201635@bigbird.bu.edu>
Date: 12 Sep 91 00:16:35 GMT
References: <3035@m1.cs.man.ac.uk> <1991Aug30.195229.4202@craycos.com>
Sender: news@bu.edu
Organization: /home/jbw/.organization
Lines: 21
In-reply-to: jrbd@craycos.com's message of 30 Aug 91 19:52:29 GMT

Reply to Parent Message