Weekly Edition
Return to the Press page
| |||||||||||||
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Groklaw
reports that Donald Knuth is petitioning the EPO to disallow software
patents.
"Donald Knuth, distinguished computer scientist, recipient of the Turing Award, creator of the TeX computer typesetting system, and author of The Art of Computer Programming, which some call the Bible of computer programming, has submitted a letter to the European Patent Office for submission to the EPO's Enlarged Board of Appeal considering the question of software patents and whether they should be allowed in Europe. Here's his view:
'Basically I remain convinced that the patent policy most fair and most suitable for the world will regard mathematical ideas (such as algorithms) to be not subject to proprietary patent rights.'"
(Log in to post comments)
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 4, 2009 16:26 UTC (Thu) by tao (subscriber, #17563) [Link]
Ahhh, but the software patent proponents have somehow managed to trick the EPO into believing that there's such a thing as "Computer-Implemented Inventions", and that such are not the same as software patents at all.
This despite the fact that no-one has ever been able to describe what use a software patent would be without a computer, nor for that matter what computers don't run software.
Yes, I know of firmware, I know of the possibility to design an IC that has a specific programming in hardware, but CIIs are wider than that. If CIIs were strictly limited to a single implementation, in either firmware or IC and without coverage for variations, then they would pose little or no threat to the free software movement (and for that matter the software industry as a whole).
But the sad reality is, that CIIs are, in every aspect that is relevant to the threat they impose, equivalent to software patents.
And as long as the EPO does not realise this, lobbying against software patents will do little, since they'll just keep accepting patents for "Computer-Implemented Inventions" instead.
yup, examples are needed Posted Jun 4, 2009 21:17 UTC (Thu) by coriordan (guest, #7544) [Link]
I've also come to the conclusion that "no software patents" is too blunt a message for the detailed discussions with the EPO and the European Commission.
We shouldn't abandon the term "software patents" - there's too much momentum behind it - but for some discussion we need to talk about specific example patents instead of resting on the term "software patents".
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 5, 2009 10:29 UTC (Fri) by Wol (guest, #4433) [Link]
If we do have CIIs, it needs to be made clear that (a) if you're not supplying a computer then you can't be using a patent, and (b) if what you supply is run on a general purpose computer then it can't be implementing a patent, either.
That then leaves the Patent Office free to grant patents on CIIs, but it also makes it clear that general programming can't be patented.
Cheers,
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 5, 2009 12:10 UTC (Fri) by tao (subscriber, #17563) [Link]
Still not enough. What's a general purpose computer? How about a Netbook? Kind of specialised. A tablet PC? I'd say that's specialised. How about a Supercomputer? Definitely specialised. How about a cellphone? Certainly specialised.
And yet there exists open platforms for all of these. I bet that eventually we'll see massmarket programmable "industrial" robots available. I don't want a situation where I cannot program that robot in whatever manner I want to because someone has patented some needed algorithm (and appended " with a computer" at the end of the description).
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 5, 2009 22:59 UTC (Fri) by coriordan (guest, #7544) [Link] In the 2005 proposed amendments in the EU we came up with this: A computer is a realisation of an abstract machine, consisting of entities such as processing units, storage space and interfaces for information exchange with external systems and human users. Data processing is calculation with abstract component entities of computers. A computer program is a data processing solution which can, once it has been correctly described, be executed by computers. Whether that definition is perfect or not, we have to define "computer". Suggestions sought.
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 7, 2009 19:38 UTC (Sun) by Wol (guest, #4433) [Link]
Let's go back to the old (pre-electronic-computer) definition!
A computer is anything/anyone which (mechanically?) follows a sequence of instructions. We have to be careful about the word "mechanical" because a computer used to mean "a person who carries out computations". Maybe use the word "blindly" or "slavishly" instead?
Cheers,
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 18, 2009 10:41 UTC (Thu) by lysse (guest, #3190) [Link]
"precisely" or "exactly" would be my suggestions. I'd also suggest "an arbitrary sequence of instructions" to define a general-purpose computer.
But I'm also glad I don't have to do that for a living. :)
Yes but Posted Jun 4, 2009 16:48 UTC (Thu) by danielpf (subscriber, #4723) [Link]
I agree with Knuth that patenting math or algorithms should not be granted, mainly because such patents are ineffective in promoting the progress of science and technology in the society.
But I disagree that software is equivalent to algorithms. Nature "invented" RNA and DNA, kinds of sequences of encoded infomation leading to deterministic actions, without mathematicians, by a mere long and tortuous selection process on uncountable many trials in a prebiotic soup. One could as well mimick nature by generating in a computer zillions of random bit sequences until one works as a functional program. Even functional, such a program would be generally dull and garbage, not worth calling it an algorithm. Indeed, an algorithm has the property to transform an input into an output, it must be a directed action, which makes all the difference with most of the possible programs.
In summary, not any string of bits, although representing a number, is a program, and not any program deserves to be qualified as math. Algorithmic and non-algorithmic programs are already well protected with copyright laws, and algorithms should not be patentable because non-beneficial for the society.
algorithms can be pointless too Posted Jun 4, 2009 17:22 UTC (Thu) by perlwolf (guest, #46060) [Link]
It's easy to write useless silly algorithms, that are essentially little more than a bunch of random symbols on a page. This does not distinguish mathematical algorithms from computer programs at all. While you may tend to think of such things as "not really algorithms", you can equally classify programs as useless, useful, and.or original (and think of the useless ones as being "not really programs" if you like). In both cases, there is a complete continuum between the extremes - with the middle occupied by algorithms/programs that are a mixture of utility and flaws.
No, and ... Posted Jun 4, 2009 20:06 UTC (Thu) by kirkengaard (subscriber, #15022) [Link]
The algorithm in that case would be the means by which you generated the string of bits, not the string of bits itself. Remember what an algorithm is, and you'll understand the difference between the natural selection process by which RNA and DNA evolved as answers to environmental problems, and the so-called mimicry you propose. It is not sequence, but instructions for problem solving, that makes an algorithm.
You seem to have forgotten what a program is.
To abstract out the mathematics, algorithms should not be patentable because they are methods of problem solving, just as business methods should not be patentable. Implementations of algorithms are protected by copyright, as software code. So, certainly, software is not precisely equivalent to algorithms, but the software methods that are so often patented are not the code of a program, but the problem solving method itself. These are, in actuality, algorithm patents unless they specify the implementation to such an extent that the patent only covers that implementation. Actual software, actual programs, should certainly be protectable as implementations, but the algorithms should never be subject to the same exclusivity.
Besides which, Posted Jun 4, 2009 20:16 UTC (Thu) by kirkengaard (subscriber, #15022) [Link]
I might argue that DNA and RNA are storage and retrieval elements of a larger system, and not algorithms. While they are nominally sets of instructions, they are not sequenced for use in solving a problem. By analogy, they are the libc of the organism. Damn convenient repository for solving a multitude of problems, but not a solution in and of itself.
No, and ... Posted Jun 4, 2009 23:06 UTC (Thu) by sepreece (subscriber, #19270) [Link]
A few questions:
- Would you say that all computer programs are algorithms? I was taught that algorithms were finite, deterministic, and halted, which rules out a lot of programs. I can't tell whether Knuth means all software processing should be non-patentable (which grossly expands the definition of algorithm) or leaves a lot of it patentable because it is not implementing algorithms.
- Knuth says it would be awful if someone could patent a number. I agree, but I'm pretty sure you CAN patent a specific USE of a number - for instance the use of a particular temperature in a particular chemical process.
- Groklaw asks whether instructions can be patented - "Can you patent a manual? Is it an invention?". My understanding is that instructions for carrying out physical processes (at least those that produce useful results) are absolutely patentable.
No, and ... Posted Jun 4, 2009 23:31 UTC (Thu) by bojan (subscriber, #14302) [Link]
> which rules out a lot of programs
http://en.wikipedia.org/wiki/Algorithm
Could you give us an example of a program that doesn't fit the above (and also your) definition? Can you write a small program for us that is not an algorithm?
> My understanding is that instructions for carrying out physical processes (at least those that produce useful results) are absolutely patentable.
The process is patented. The words on the page describing the process are not. They can only be copyrighted.
Otherwise, you could patent your patent submission, not just the subject matter of the submission. (Before you ask, IBMs patent on patent submissions is a patent on the method/process once again).
No, and ... Posted Jun 5, 2009 0:23 UTC (Fri) by welinder (guest, #4699) [Link]
>http://en.wikipedia.org/wiki/Algorithm
>Could you give us an example of a program that doesn't fit the above
I am not the poster you asked, but it's not hard to come up with
int main() { while (1); }
There you go.
No, and ... Posted Jun 5, 2009 1:14 UTC (Fri) by bojan (subscriber, #14302) [Link]
This (like any other) program terminates. One would require some kind of perpetual motion machine to execute it forever.
The end state of it will depend of how exactly we reached the end of processing: signal, crash, reboot, electricity switched off, hardware failure, end of civilisation etc. But for each of these events, we will have some end-state of that program.
More specifically, consider a Linux program compiled from your code. If you send it a SIGKILL, it will stop. Obviously, has a well defined end-state.
No, and ... Posted Jun 5, 2009 2:47 UTC (Fri) by sepreece (subscriber, #19270) [Link]
Uh, no. If you send the process a SIGKILL, the end state is not well-defined, because you don't know what state the program will be in when it gets the signal. Nor is the finiteness of the universe sufficient - an algorithm has to define its halting condition (e.g., difference from desired result less than sigma). Make the program slightly more complicated - have it increment a non-initalized variable on each iteration. Now it's non-deterministic (because the initial state is undefined) and its end state is also undefined. Not an algorithm.
A program can implement an algorithm, but it is not itself the algorithm. Nor is every program an algorithm.
No, and ... Posted Jun 5, 2009 3:05 UTC (Fri) by bojan (subscriber, #14302) [Link]
> If you send the process a SIGKILL, the end state is not well-defined, because you don't know what state the program will be in when it gets the signal.
Of course it will be well defined. It will be one of its possible states. In fact, you can even find out what that state was, although that's not even necessary to have a well defined state (reality doesn't care what you can and cannot see).
> Now it's non-deterministic
Just because you didn't set the variable, doesn't mean it was not set to a particular value. Which then gives the program another possible state.
Try this. Have an undefined variable in your program. The run it under GDB. Of course, you'll get "random" garbage in the variable, which is still a value, which gives your program a well defined state. For example, if this was a 32-bit integer variable, the initial state will be any value that this variable can hold.
Maybe your flowchart didn't take that into account. Irrelevant for the purposes of having a state.
No, and ... Posted Jun 5, 2009 4:35 UTC (Fri) by chad.netzer (✭ supporter ✭, #4257) [Link]
bojan, don't invent new terminology. From a computational theory standpoint, an infinite loop doesn't halt (ie. terminate). We aren't discussing the heat death of the universe, we are discussing algorithms.
No, and ... Posted Jun 5, 2009 5:20 UTC (Fri) by bojan (subscriber, #14302) [Link]
I'm not saying that an infinite loop terminates. I'm saying that every program terminates. When it does, it will have a state which will be determined by whatever happened until that point.
Similarly, when you push the reset button on you computer, that program (kernel + userspace) will terminate and have an end-state. (In the olden days of Atari, you could even save your ramdisk across resets, if I remember correctly).
We may think that a computer program is what we wrote in that piece of source code only. But the fact is that there is so much more to it when it actually becomes a program that runs on the computer. Just remember the ext4 v. POSIX episode. The crashes of the kernel were causing an end-state that we didn't particularly like. So, the algorithm was changed to have a different end-state in case of a crash.
It is easy to pretend that these events are not the input for the logic of the algorithm that is running on our computers. (Un)Fortunately, the reality is different.
No, and ... Posted Jun 5, 2009 6:30 UTC (Fri) by chad.netzer (✭ supporter ✭, #4257) [Link]
If you suggest that all programs must necessarily halt, then what is your definition of computation? And does your definition form an argument for or against the patentability of algorithms?
Just as an example, the "Halting Problem" doesn't exist by your definition of computational theory, and yet it is one of the most fundamental results in everyone else's version.
No, and ... Posted Jun 5, 2009 7:03 UTC (Fri) by bojan (subscriber, #14302) [Link]
A computer program executes on a computer. Hence, it eventually terminates. Hence, it will have an end-state. These are all very trivial facts.
Halting problem:
http://en.wikipedia.org/wiki/Halting_problem
Deals with an idealistic scenario, much like it is depicted in that forever loop. It is, of course, useful for finding theoretical solutions to theoretical problems.
However, for such scenarios to be realised in practice, one needs to have a computer that runs forever. Such computers do not exist. Programs do not run on non-existing computers.
No, and ... Posted Jun 5, 2009 9:18 UTC (Fri) by chad.netzer (✭ supporter ✭, #4257) [Link]
Sigh. This is unrewarding. Have it your way: computers are not used for computation, just for running programs. Because computations may either halt, or not.
No, and ... Posted Jun 5, 2009 10:37 UTC (Fri) by bojan (subscriber, #14302) [Link]
I understand your point. The theory says what it says, there is no question about that.
The original notion put forward was that computer programs are not algorithms, because they do not halt, are not deterministic and are not finite. Sure, when you write your source, it may seem that way (and in theory it is). Once you put that program on a computer with finite resources and execute it, memory gives initial state (whether set by you or not), which then brings your code through a set of well defined states (whether written in your source or not), which then eventually ends in some final state (whether your program ended execution itself or not). The fact that the source may not be sufficient to describe all these states doesn't diminish the fact that all these states indeed happened in a well defined way.
As for your question of whether such beasts should be patentable or not, I am of the opinion that they should not be patentable. Computer programs deal exclusively with information processing and are in that respect very similar to maths. Whether number three is printed on the screen or three sticks are spat out of the machine at the end of processing, the purpose of the computer program was to determine that number, which is a just piece of information.
No, and ... Posted Jun 5, 2009 18:45 UTC (Fri) by chad.netzer (✭ supporter ✭, #4257) [Link]
"The original notion put forward was that computer programs are not algorithms"
No it was not! It was suggested that you *could* create a program that would not halt, and that such a program was not an algorithm, if you go by that definition. It was clearly discussing a notion of computational *theory*. You completely sidetracked that discussion for your own banal point, for what purpose I don't know.
/*
The legal/patent aspect of all this is that the law cares about definitions (whether they intersect with reality or not), and so an unfortunate definition could have bad consequences, particularly in the patent realm that can intertwine with the realm of concepts, and well as physical realities.
No, and ... Posted Jun 7, 2009 14:19 UTC (Sun) by malor (subscriber, #2973) [Link]
When thinking about algorithms and programs, the hardware is irrelevant. It's treated as an abstraction. A while(1) loop runs on both ARM and x86, on mainframes and on pocket calculators. In theory, it could probably run on some computational substrate of the Universe itself, a machine that couldn't fail, even in theory.
You're arguing about physical implementations OF algorithms, not algorithms themselves. In the context of this discussion, it's unimportant wankery.
No, and ... Posted Jun 11, 2009 11:27 UTC (Thu) by malor (subscriber, #2973) [Link]
Another way of putting it: your claim that hardware realities mean that all algorithms will exit is true, but it's not usefully true. If the hardware fails and crashes, that means it didn't run the algorithm properly, not that the algorithm actually exits.
No, and ... Posted Jun 19, 2009 16:41 UTC (Fri) by mcortese (guest, #52099) [Link] An algorithm must terminate, a program need not.Quite interesting. Does it mean that I can convert a no matter how complex algorithm to a non-algorithm just appending a while(1); at its end?
No, and ... Posted Jun 5, 2009 3:12 UTC (Fri) by sepreece (subscriber, #19270) [Link]
"The process is patented. The words on the page describing the process are not. They can only be copyrighted."
Yes and no. The words are covered by copyright, but the process (the instructions) are not. The process is covered by patents. But, the words define the process just the way a program defines the process carried out by the computer. So, by analogy, if the code is covered by copyright, should not the process defined by the code be patentable? [Oversimplified analogy, of course.]
Note that I would be perfectly content if software patents were barred, for some satisfactory definition of "software patent" that I am myself unable to construct. I would be VERY happy to see the term of patents limited by how "hard" the patented invention was to create, but I can't imagine how to define that, either. In any case, it's critically important that examiners effectively test that inventions are novel and non-obvious, for ALL kinds of patents.
But a lot of the discussion, including Knuth's note, misses the fact that defining what "software patent" means is very difficult and is getting more so as equivalencies increase. Should a hardware implementation of an computational algorithm be patentable?
Note that I also think the fuss around "mathematical" is misleading. Clearly, you can't patent laws of mathematics (the relationship described by Pythagoras is such a law), but that can't be the basis, on its own, for saying algorithms shouldn't be patentable. Algorithms may be described in mathematical language, but so can physical processes. In either case, they are creations of human ingenuity, not "laws of nature".
So far, I haven't heard any arguments against software patents that don't apply equally to all patents. I keep reading the arguments and I keep finding them not very convincing. However, at the same time, I do think they are failing to live up to the Constitutional goal of promoting progress in software...
No, and ... Posted Jun 5, 2009 3:36 UTC (Fri) by bojan (subscriber, #14302) [Link]
> So, by analogy, if the code is covered by copyright, should not the process defined by the code be patentable?
Which process would that be? What is being processed here?
The point is that nothing objective (meaning: having physical presence) is being processed here, but an abstract human concept: information. Just like in mathematics.
Non-mathematical patents Posted Jun 5, 2009 6:16 UTC (Fri) by man_ls (subscriber, #15091) [Link] Note that I also think the fuss around "mathematical" is misleading.I agree. Many software patents have nothing to do with maths at all. When Apple patented the trash can on the desktop they were patenting a pure idea, not a mathematical concept or algorithm or whatever. At the same time it is a despicable patent which offers nothing to the world. The same goes for Microsoft patenting "a computer on a car dashboard" that made TomTom settle recently, for the Bilski patent (a method of hedging risks in commodities trading) and even, I would contend, for the FAT patents: generating a short name from a long one requires counting, but I don't think that means "requiring maths". Of course some algorithms are pure maths: the FFT and the LZW algorithm in GIF compression would surely qualify. But if courts were to forbid only mathematical patents then lots of harmful patents would survive. Knuth takes the view that: I am told that the courts are trying to make a distinction between mathematical algorithms and nonmathematical algorithms. To a computer scientist, this makes no sense, because every algorithm is as mathematical as anything could beIMHO that is too limited in scope. A trash can on a desktop is not mathematical, nor is a computer on a dashboard or the FAT patents for that matter, because they are not algorithms and the related algorithms are not mathematical. "Position the cursor on a file, move the file to the trash, then recover the file or empty the trash"; "switch the dashboard computer on, speak a location, follow the directions spoken by the computer"; "shorten the name to 6, then add ~ and a number". In each case there is some maths but they are not the main selling point of the patent; you could as well say that a recipe for making cookies is mathematical because it contains quantities. At the same time they are software patents (or "computer-implemented inventions" as another poster reminds us above) and serve no useful purpose to society.
Non-mathematical patents Posted Jun 5, 2009 7:14 UTC (Fri) by drag (subscriber, #31333) [Link]
Well then let the stupid patents lay.
Sure Apple patented "trash can on desktop".. but who cares? Its not like it is something that won't be trivial to work around. So what?
What I personally give a shit about is people using patents to control file formats. I care about patents for compression methods. Or the guys that were able to patent using "Xor" on a image. I care about encryption methods, protocols, file systems, etc etc.
All programs are fundamentally mathematical in nature. There is no way around it. No matter how many layers of BS, layers of abstraction, or "human language-like" your able to make it seem... No matter what you can do there is no changing the fundamental nature that if you write a program your programming in math. If you don't understand this or you don't see it then it just means your going to make shitty programs and shitty algorithms. Everything gets broken down to Os and 1s and everything boils down to a series of boolean operations.
Not all patents having to do with computers or user interfaces are math. Computer hardware is not math.
But all software is math. I mean that is the definition of program. It is in the name, its _programming_. It IS what software IS. It's MATH, bits, bytes, adding, subtracting, etc etc
-------------------------
Oh. And if I understand things correctly (since I ain't no lawyer)
What you put in a patent is public domain. There is no copyrightable anything in patents.
In fact it seems to me that the entire concept of patent and copyrights are diametrically opposed. The idea that you can have a program that is BOTH protected by copyrights AND patents is absurd, its just broken.
I don't care if its illegal or legal or makes sense according to the rules, it is just a dumb as brick idea.
If people want software patents then they should have to choose between copyright protections OR patent protections. If they choose patents then the entire program, that is anything in their code that touches the patented algorythm has to be published into the public domain.
I can pretty much guarantee you that would kill all but the most effective patents.
If mean for FFS....
THE PEOPLE THAT MAKE MONEY ON SOFTWARE PATENTS (for the most part) ARE PEOPLE THAT DON'T MAKE ANY SOFTWARE. (aka patent trolls) So what benefit is there to society to even have any of this?!
Its just broken on so many levels.
Non-mathematical patents Posted Jun 5, 2009 8:36 UTC (Fri) by k3ninho (subscriber, #50375) [Link]
>What you put in a patent is public domain. There is no copyrightable anything in patents.
I'm sorry to say that patents, copyrights, trade marks and design rights are not exclusive forms of protection. Take the case of an Apple computer. It contains widgets whose operation is patented, parts of the shape and configuration are protected by design patents or design rights, the Apple logo is trademarked and the ownership of the copyrightable portions of the device (firmware, OS, music, movies, written text) all have their own protection.
In particular, the text and drawings of a patent specification still get covered by copyright, but they don't get protection from disclosing industrial secrets. And most sane governments write an exception clause into their copyright laws so that it is not an infringement of the copyright in a patent specification to copy that document when working on the subject material of the patent.
Non-mathematical patents Posted Jun 5, 2009 7:16 UTC (Fri) by bojan (subscriber, #14302) [Link]
> you could as well say that a recipe for making cookies is mathematical because it contains quantities
Last batch of cookies I made all had ingredients like flour, sugar, butter, salt, etc. in them. It was very important to use exactly these objects. For instance, a cookie made with meat instead of flour would taste, shall we say, funny.
On the other hand, software patents deal with an abstract concept: information. For a software patent to be realised, it is irrelevant if you have punch cards, silicon chips, magnetic media or mechanical devices. It doesn't matter if you screen is LCD or CRT. As long as the information is processed according to the algorithm, you are OK. Much like in maths.
Not so with cookies ;-)
Non-mathematical patents Posted Jun 5, 2009 10:47 UTC (Fri) by Wol (guest, #4433) [Link]
Thing is, if you follow the recipe AS EXACTLY AS POSSIBLE twice, you are likely to get TWO DIFFERENT RESULTS.
A patent is meant to protect your tricks for following the recipe, such as you guarantee the same result both times. The recipe tells you what to do, the patent describes how you follow the recipe - how *you* *personally* follow the instruction that says "cream the sugar and butter together".
Thing with Maths, there's only one way to follow the instruction, therefore you always get the same result, and anybody else following the same recipe (algorithm) will get the same result.
Even something as simple as "bake on a low heat for 10 minutes" will have twenty people doing it forty different ways!
Cheers,
Non-mathematical patents Posted Jun 6, 2009 10:22 UTC (Sat) by man_ls (subscriber, #15091) [Link] I don't see your point. If the trashcan patent is implemented on two separate desktops, they will contain different code, look different, and probably work differently in subtle ways too.It works for most patents and algorithms: no two implementations of the RSA algorithm will be identical; computer language, variable names and so on will change. But even when using the same language independent coders will generate programs with wildly varying performance, accuracy, options, failure modes... Not to speak about the "computer on dashboard" patent -- independent implementations will be vastly different. That is why patents are not just math; they can be expressed mathematically, sometimes and for some aspects, but quite often what is not math is the meat of the matter.
Non-mathematical patents Posted Jun 5, 2009 14:58 UTC (Fri) by sepreece (subscriber, #19270) [Link]
Well, suppose you implement the program in physical operations - for instance, where the code says "store register x into location 123", you make a physical copy of whatever is in the box (say, on your desk) labeled "x" and put it into the box labeled "123". Would that make it patentable in your eyes? If they compute the same end value (expressed in one case as a binary number and in the other as the size of a collection of marbles), are they equivalent?
In any case, there IS a physical aspect to computers and the execution of programs - actual electrons are running around doing physical things. It's not abstract in any sense.
The *description* of the program is abstract and can be reasoned about using abstract methods, the program itself and the execution of the program are not abstract.
Non-mathematical patents Posted Jun 6, 2009 11:08 UTC (Sat) by man_ls (subscriber, #15091) [Link] "Flour" is an abstract concept, just as "1" or "0x7F" or "if (x == y)". When implementing the recipe I can use wheat flour of many different types and brands, but I can also use corn, rye or other flours. As to the recipe I can use different substitutes for ingredients (not maybe for flour, but for eggs, sugar or butter). I can omit things like salt or sugar, and put some of my own (ginger, almonds).There is no such thing as a "concrete concepts"; concepts are by definition abstract. True, there are some which are more abstract than others; "happiness" is undoubtedly more abstract than "flour". The application of this reasoning to software patents is straightforward. Software patents (or algorithms for that matter) rely on some concrete aspects, and some abstract ones. Also, some algorithms are more abstract than others. But usually (not always) algorithms are not patented; applications of algorithms to problems are. The RSA patent is for a "Cryptographic communications system and method", not a generic algorithm for composing numbers that cannot be factored. In contrast, the LZW algorithm was patented not only for GIF images but for any application.
Non-mathematical patents Posted Jun 5, 2009 8:13 UTC (Fri) by luya (subscriber, #50741) [Link]
"Many software patents have nothing to do with maths at all. When Apple patented the trash can on the desktop they were patenting a pure idea, not a mathematical concept or algorithm or whatever."
It is still mathematical because of the method to achieve that process. Trash can on desktop can be physically represented. On computer world, a desktop is a series of mathematics, so is trash can. That example only shows how silly is to patent a mathematical (that can also be an algorithm) representation. The whole software patent industry is a sham.
Non-mathematical patents Posted Jun 6, 2009 11:18 UTC (Sat) by man_ls (subscriber, #15091) [Link] Are you sure the trashcan is mathematical? Or, more to the point, are you sure that the mathematical side is the most relevant part of the algorithm? Can you express mathematically (in numbers, equations, first-order logic or any other math form you desire) the transformations performed by the trashcan on your desktop? Sure, you can use a flowchart and pretend that is mathematical, but if so then most industrial processes are algorithmic (and therefore mathematical) too and should not be patented.
Non-mathematical patents Posted Jun 5, 2009 11:34 UTC (Fri) by Zack (guest, #37335) [Link]
>A trash can on a desktop is not mathematical,
I agree that having an icon with a particular action attached may not *seem* mathematical, but *anything* that happens on your desktop (or a computer in general), is inherently algorithmic and as such mathematical, which I believe is the point of contention that lies at the root of a distinction between "mathematical algorithms" and "non-mathematical algorithms"
Take every bit that your computer currently holds and write these all down on a long string of 1s and 0s. Call that string A.
You now have two very very long strings of 1s and 0s. Now ask the question, does there exist a Turing machine that will take string A as its input and will arive at string B?
I realize it doesn't appeal to intuition or a practical view of the use of computers. But by the above example, everything you could ever do on a computer no matter how sophisticated or trivial is an example of a mathematical operation. So everything that happens on your computer is done by though an algorithm and there are no non-mathematical algorithms in computer-software.
Non-mathematical patents Posted Jun 5, 2009 15:13 UTC (Fri) by man_ls (subscriber, #15091) [Link] That is precisely the reductionistim view that in my view is not useful when fighting software patents.By the same token you might say that everything done in a factory is physics: a bunch of atoms come in, a bunch of atoms in different states come out. Physics is not patentable, therefore nothing done in a factory is patentable. Or, all pharma products are just chemistry, and chemistry is not patentable -- therefore medicines are not patentable. Hey, I went too far, chemistry is patentable. But chemistry is, after all, just physics -- atoms changing states, and physics is not patentable as we well know. Again, some form of physics must be patentable. But if I remember my physics correctly, it was all numbers, magnitudes and equations, or mathematics. So, how can mathematics be patentable again? Anything that happens in our physical Universe can be described mathematically, as far as we know. Therefore just saying that something "is just mathematics" does not help when judging patentability. Let us instead focus on utility and social benefit.
Non-mathematical patents Posted Jun 5, 2009 15:59 UTC (Fri) by sepreece (subscriber, #19270) [Link]
"the transformation was an algorithmic one, i.e. describable through an algorithm"
And there's the problem - the algorithm is an abstract (but specific) description of the process carried out, but it is not itself that process. The process is carried out by electronic devices in a computer.
Similarly, a patent for a chemical process is an abstract (but specific) description of a process carried out by physical devices.
The usual argument (which, I believe, led to extending patent protection to software in the US) is that while the algorithm itself is abstract and can be carried out completely abstractly by a human reader to get the answer, the combination of that algorithm with hardware executing it is patentable, because the patent is then describing a way of carrying out that computation in hardware (the computer), just as a chemical-process patent describes a way of carrying out a process in a chemical plant.
Note that while I do not find the idea of software patents any more or less offensive than the idea of patents in general, I DO find the specifics of the implementation of software patents offensive - the terms are far too long for the domain and the examination process is wildly too permissive. Those could be corrected without throwing out software patents entirely.
No, and ... Posted Jun 5, 2009 10:39 UTC (Fri) by Wol (guest, #4433) [Link]
Patents were *meant* to protect *implementations*.
Making cables of "perfect steel" I could probably suspend the Severn Suspension Bridge (the longest in the world when it was built) on a couple of strands of 1cm thick cable.
THAT design is maths - "if everything works as per theory, this is how we could do it". The reality is, steel isn't perfect, and patents are *meant* to protect the techniques we use to get as close to perfection as possible.
So maths *shouldn't* be patentable, and that's why software shouldn't be patentable - it's a list of instructions, that if followed, will produce a "perfect" result every time (bugs excluded :-)
So you can't patent it because it's not a technique for minimising imperfections.
Cheers,
No, and ... Posted Jun 5, 2009 15:52 UTC (Fri) by papik (guest, #15175) [Link]
> So you can't patent it because it's not a technique for minimising imperfections.
Then I think that there is software that is patentable. That is software to work
And maybe this software should be patentable.
But then... what about software to work around software limitation (FAT long
No, and ... Posted Jun 5, 2009 2:53 UTC (Fri) by flewellyn (subscriber, #5047) [Link]
>> I was taught that algorithms were finite, deterministic, and halted, which rules out a lot of programs.
You were taught very wrongly! There absolutely are non-deterministic, non-halting, infinite algorithms. In fact, those make up a large portion of computer science and AI research. Who on Earth taught you that algorithms must be finite and deterministic? That person should not be allowed to teach.
No, and ... Posted Jun 5, 2009 15:10 UTC (Fri) by sepreece (subscriber, #19270) [Link]
"Who on Earth taught you that algorithms must be finite and deterministic?"
Well, curiously enough, that was Knuth (or, rather, another brilliant CS professor teaching from Knuth's book).
The Art of Programming, Volume 1: Fundamental Algorithms, pp4-6 (first edition). "... an algorithm has five important features: 1) Finiteness. An algorithm must always terminate after a finite number of steps. ... A procedure that has all the characteristics of an algorihm except that it possibly lacks finiteness may be called a 'computational method' ... 2) Definiteness. Each step of an algorithm must be precisely defined. ... 3) Input ... 4) Output ... 5) Effectiveness ..." [in each case the "..." represents a body of explanatory text).
You think Knuth should not be allowed to teach?
No, and ... Posted Jun 5, 2009 16:56 UTC (Fri) by flewellyn (subscriber, #5047) [Link]
Knuth seems to be going by a restricted definition of "algorithm", then. From what I've read, "computational method" and "algorithm" fade into each other depending on whose definitions you use.
Perhaps I spoke hastily with the "should not be allowed to teach".
No, and ... Posted Jun 6, 2009 2:03 UTC (Sat) by chad.netzer (✭ supporter ✭, #4257) [Link]
Yes, you did. :) The fact is, the definition of "algorithm" in CS is not unlike the definition of "species" in biology; no one can quite agree on a rigorous definition.
http://en.wikipedia.org/wiki/Algorithm#Termination
Algorithms Posted Jun 10, 2009 1:14 UTC (Wed) by jlokier (guest, #52227) [Link]
Algorithms don't have to terminate. Consider a program which prints out the digits of Pi one after another. It does not terminate, but it's implementing an algorithm to calculate those digits.
Algorithms don't have to be deterministic. Consider optimisation algorithms which use randomness like genetic algorithms and simulated annealing. They can use pseudo-randomness, but that's not part of the algorithm (usually), it's part of the implementation, and true external randomness is allowed too. Some algorithms only work if they have a source of randomness, and thus are non-deterministic. If the randomness is not truly random, they fail to terminate for some inputs.
Consider also parallel algorithms; a lot of them have non-deterministic behaviour because the global executation order is inherently not determined.
Perhaps there is some definition of "algorithm" which requires termination and determinism, and perhaps it was always like that in the distant origins of the word (before computers...), but it's not a definition I'm familiar with.
Algorithms Posted Jun 11, 2009 14:01 UTC (Thu) by sepreece (subscriber, #19270) [Link]
The definition of "algorithm" I used in my original comment was Knuth's definition, from Volume 1 of The Art of Programming. I posted a synopsis of the definition in another response.
Genetic patents Posted Jun 4, 2009 20:41 UTC (Thu) by southey (subscriber, #9466) [Link]
Just wanted to point out that so far genetic information has been patented. See for example:
http://en.wikipedia.org/wiki/Gene_patent
Although the USPO says "[a] patent on a gene covers the isolated and purified gene but does not cover the gene as it occurs in nature". However, there is a current challenge that may further reduce the scope, for example:
Genetic patents Posted Jun 5, 2009 8:17 UTC (Fri) by luya (subscriber, #50741) [Link]
That only show how broken and corrupt the whole patent system is in the USA.
Genetic patents Posted Jun 8, 2009 10:20 UTC (Mon) by Seegras (subscriber, #20463) [Link]
The patent-system is actually broken everywhere.
There is a case argueing that it works in the field of pharmacy; but everywhere else the legal costs are higher than the income from licenses. Which shows that its only a tool for corporate warfare and not only does not "promote the progress of science and useful arts", but clearly damages the progress of science and useful arts.
Yes but Posted Jun 5, 2009 14:04 UTC (Fri) by forthy (guest, #1525) [Link] If you are about "promoting the progress of science and technology in society", abandon all patents. They don't serve their purpose, they serve a different purpose: Rent seeking. The same is true for copyright, as well. We know better, we have abandoned copyright in favor of copyleft or similar schemes (note that copyleft is carefully crafted to be promoting progress of science and technology in society; it should be the law, not riding on the back of copyright). If you think that rent-seeking monopolysts benefit society, then maybe that is worth called "opinion". But the main problem we have in this discussion is that politicians don't think about benefit for the society as a whole, but to satisfy those special interest groups who appear to be loudest, and closest to their pay-check. So after all the EPO is right: There is no fundamental difference between software and other patents. They are all the same bogus rent-seeking monopoly grants that harm society and benefit those who get them granted. Thus when there is no fundamental difference, there is no reason to include or exclude one or the other from being patented. The EPO grants patents on DNA sequences, which clearly are not even an invention - they are just print-outs of sequenced DNA that nature delivered. It is clearly against the letters of the european patent convention to patent discoveries from nature. However, as making monopolies to [AGCT]* strings is just as bad as any other monopoly, it is identical in nature, and therefore can have a patent.
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 5, 2009 11:25 UTC (Fri) by nlucas (subscriber, #33793) [Link]
I don't really see the difference between a software algorithm and cooking recipes or sheet music.
They are all algorithms, with the only difference being the the one who will execute it.
I think it would make more sense to start associating patents on software algorithms to patents on sheet music or patents on cooking recipes.
With sheet music the law is already set to not allow it (leaving it to copyright) and although not sure about cooking recipes (but I think I remember Coca-Cola couldn't patent it's recipe) I believe it will make more sense to the powers that be on the absurd of having different laws for the same things.
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 5, 2009 12:18 UTC (Fri) by MathFox (guest, #6104) [Link]
Instructions on how to cook Latex (raw rubber) to get vulcanized (tire) rubber have lead to a patent on the process. So yes, it is possible to obtain patents on (industrial) processes. However, you still can distribute the recipe (which should be disclosed in the patent), but there were times were actually cooking rubber in your kitchen was breaching a patent.
How this situation translates to software patents is unclear. There's lack of jurisprudence, patent offices have granted patents that should have been rejected in a strict reading of the law. It also is quite unclear when infringement of a patent starts; Lame did (does?) provide only source code because their lawyer was unsure whether distributing object code would be "contributory patent infringement".
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 5, 2009 13:19 UTC (Fri) by nlucas (subscriber, #33793) [Link]
Yeah, I wasn't too sure on recipes, but maybe that only means those cases are as wrong as software patents?
If you take the sheet music case, the law is already set on that one, so one could show the politics there are already strong copyright laws for the algorithm cases and patents on software algorithms (or recipes, or any other kind of algorithms) are dumb and don't really add anything.
One advantage is that it breaks the alleged point on patents being good because they allow the knowledge be shared. Doesn't the music allow the same and make music publishers rich?
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw) Posted Jun 5, 2009 15:37 UTC (Fri) by sepreece (subscriber, #19270) [Link]
Patents make patent holders rich in exactly the same way musical copyrights do - the patent holder (and licensees) hold the sole right to practice what the patent defines, just as a copyright gives the author the sole right to sell or perform the work.
It doesn't matter that the description of the invention is public domain, because nobody is allowed to DO what the patent describes except with the permission of the patent holder.
Patents are generally much stronger protection, because they cover an abstract description of a thing or process, rather than an expression, where copyright covers only a specific expression.
The justification for patents is (1) that the patent holder is obliged to expose her secrets and explain how the process or device works, which allows others to study that information and look for ways to do better or to improve the original (the improvement could then be patents and licensed back to the original patent holder), and (2) that the patent runs for a limited duration, so secret processes don't get locked up in one company's or family's control indefinitely.
I don't think software patents have been a great success on this score, and wouldn't mind seeing the law changed to not allow them, but I fear the process of deciding exactly what "software patent" means would probably not halt...
|
|||||||||||||