Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
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.'"
Posted Jun 4, 2009 16:26 UTC (Thu)
by tao (subscriber, #17563)
[Link] (6 responses)
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.
Posted Jun 4, 2009 21:17 UTC (Thu)
by coriordan (guest, #7544)
[Link]
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".
Posted Jun 5, 2009 10:29 UTC (Fri)
by Wol (subscriber, #4433)
[Link] (4 responses)
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,
Posted Jun 5, 2009 12:10 UTC (Fri)
by tao (subscriber, #17563)
[Link] (3 responses)
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).
Posted Jun 5, 2009 22:59 UTC (Fri)
by coriordan (guest, #7544)
[Link] (2 responses)
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.
Posted Jun 7, 2009 19:38 UTC (Sun)
by Wol (subscriber, #4433)
[Link] (1 responses)
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,
Posted Jun 18, 2009 10:41 UTC (Thu)
by lysse (guest, #3190)
[Link]
But I'm also glad I don't have to do that for a living. :)
Posted Jun 4, 2009 16:48 UTC (Thu)
by danielpf (guest, #4723)
[Link] (46 responses)
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.
Posted Jun 4, 2009 17:22 UTC (Thu)
by perlwolf (guest, #46060)
[Link]
Posted Jun 4, 2009 20:06 UTC (Thu)
by kirkengaard (guest, #15022)
[Link] (40 responses)
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.
Posted Jun 4, 2009 20:16 UTC (Thu)
by kirkengaard (guest, #15022)
[Link]
Posted Jun 4, 2009 23:06 UTC (Thu)
by sepreece (guest, #19270)
[Link] (38 responses)
- 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.
Posted Jun 4, 2009 23:31 UTC (Thu)
by bojan (subscriber, #14302)
[Link] (31 responses)
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).
Posted Jun 5, 2009 0:23 UTC (Fri)
by welinder (guest, #4699)
[Link] (13 responses)
I am not the poster you asked, but it's not hard to come up with
int main() { while (1); }
There you go.
Posted Jun 5, 2009 1:14 UTC (Fri)
by bojan (subscriber, #14302)
[Link] (11 responses)
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.
Posted Jun 5, 2009 2:47 UTC (Fri)
by sepreece (guest, #19270)
[Link] (1 responses)
A program can implement an algorithm, but it is not itself the algorithm. Nor is every program an algorithm.
Posted Jun 5, 2009 3:05 UTC (Fri)
by bojan (subscriber, #14302)
[Link]
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.
Posted Jun 5, 2009 4:35 UTC (Fri)
by chad.netzer (subscriber, #4257)
[Link] (8 responses)
Posted Jun 5, 2009 5:20 UTC (Fri)
by bojan (subscriber, #14302)
[Link] (7 responses)
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.
Posted Jun 5, 2009 6:30 UTC (Fri)
by chad.netzer (subscriber, #4257)
[Link] (6 responses)
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.
Posted Jun 5, 2009 7:03 UTC (Fri)
by bojan (subscriber, #14302)
[Link] (5 responses)
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.
Posted Jun 5, 2009 9:18 UTC (Fri)
by chad.netzer (subscriber, #4257)
[Link] (4 responses)
Posted Jun 5, 2009 10:37 UTC (Fri)
by bojan (subscriber, #14302)
[Link] (3 responses)
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.
Posted Jun 5, 2009 18:45 UTC (Fri)
by chad.netzer (subscriber, #4257)
[Link]
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.
Posted Jun 7, 2009 14:19 UTC (Sun)
by malor (guest, #2973)
[Link]
You're arguing about physical implementations OF algorithms, not algorithms themselves. In the context of this discussion, it's unimportant wankery.
Posted Jun 11, 2009 11:27 UTC (Thu)
by malor (guest, #2973)
[Link]
Posted Jun 19, 2009 16:41 UTC (Fri)
by mcortese (guest, #52099)
[Link]
Posted Jun 5, 2009 3:12 UTC (Fri)
by sepreece (guest, #19270)
[Link] (16 responses)
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...
Posted Jun 5, 2009 3:36 UTC (Fri)
by bojan (subscriber, #14302)
[Link]
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.
Posted Jun 5, 2009 6:16 UTC (Fri)
by man_ls (guest, #15091)
[Link] (12 responses)
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:
Posted Jun 5, 2009 7:14 UTC (Fri)
by drag (guest, #31333)
[Link] (1 responses)
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.
Posted Jun 5, 2009 8:36 UTC (Fri)
by k3ninho (subscriber, #50375)
[Link]
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.
Posted Jun 5, 2009 7:16 UTC (Fri)
by bojan (subscriber, #14302)
[Link] (4 responses)
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 ;-)
Posted Jun 5, 2009 10:47 UTC (Fri)
by Wol (subscriber, #4433)
[Link] (1 responses)
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,
Posted Jun 6, 2009 10:22 UTC (Sat)
by man_ls (guest, #15091)
[Link]
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.
Posted Jun 5, 2009 14:58 UTC (Fri)
by sepreece (guest, #19270)
[Link]
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.
Posted Jun 6, 2009 11:08 UTC (Sat)
by man_ls (guest, #15091)
[Link]
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.
Posted Jun 5, 2009 8:13 UTC (Fri)
by luya (subscriber, #50741)
[Link] (1 responses)
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.
Posted Jun 6, 2009 11:18 UTC (Sat)
by man_ls (guest, #15091)
[Link]
Posted Jun 5, 2009 11:34 UTC (Fri)
by Zack (guest, #37335)
[Link] (2 responses)
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.
Posted Jun 5, 2009 15:13 UTC (Fri)
by man_ls (guest, #15091)
[Link]
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.
Posted Jun 5, 2009 15:59 UTC (Fri)
by sepreece (guest, #19270)
[Link]
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.
Posted Jun 5, 2009 10:39 UTC (Fri)
by Wol (subscriber, #4433)
[Link] (1 responses)
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,
Posted Jun 5, 2009 15:52 UTC (Fri)
by papik (guest, #15175)
[Link]
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
Posted Jun 5, 2009 2:53 UTC (Fri)
by flewellyn (subscriber, #5047)
[Link] (3 responses)
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.
Posted Jun 5, 2009 15:10 UTC (Fri)
by sepreece (guest, #19270)
[Link] (2 responses)
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?
Posted Jun 5, 2009 16:56 UTC (Fri)
by flewellyn (subscriber, #5047)
[Link] (1 responses)
Perhaps I spoke hastily with the "should not be allowed to teach".
Posted Jun 6, 2009 2:03 UTC (Sat)
by chad.netzer (subscriber, #4257)
[Link]
http://en.wikipedia.org/wiki/Algorithm#Termination
Posted Jun 10, 2009 1:14 UTC (Wed)
by jlokier (guest, #52227)
[Link] (1 responses)
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.
Posted Jun 11, 2009 14:01 UTC (Thu)
by sepreece (guest, #19270)
[Link]
Posted Jun 4, 2009 20:41 UTC (Thu)
by southey (guest, #9466)
[Link] (2 responses)
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:
Posted Jun 5, 2009 8:17 UTC (Fri)
by luya (subscriber, #50741)
[Link] (1 responses)
Posted Jun 8, 2009 10:20 UTC (Mon)
by Seegras (guest, #20463)
[Link]
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.
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.
Posted Jun 5, 2009 11:25 UTC (Fri)
by nlucas (guest, #33793)
[Link] (3 responses)
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.
Posted Jun 5, 2009 12:18 UTC (Fri)
by MathFox (guest, #6104)
[Link] (2 responses)
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".
Posted Jun 5, 2009 13:19 UTC (Fri)
by nlucas (guest, #33793)
[Link] (1 responses)
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?
Posted Jun 5, 2009 15:37 UTC (Fri)
by sepreece (guest, #19270)
[Link]
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...
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
yup, examples are needed
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Wol
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Wol
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Yes but
algorithms can be pointless too
No, and ...
Besides which,
No, and ...
No, and ...
No, and ...
>Could you give us an example of a program that doesn't fit the above
examples of that. An algorithm must terminate, a program need not.
No, and ...
No, and ...
No, and ...
No, and ...
No, and ...
No, and ...
No, and ...
No, and ...
No, and ...
No, and ...
* The following is *not* an executing program, it is a
* text representation of an endless loop. It represents
* a computation that doesn't halt, and could be turned
* into a program that is bounded by the computational
* constraints of the universe.
*
* Is it an "algorithm?" bojan says yes, because it can be
* converted into an execution that *must* 'halt' by the
* constraints of physics.
* I say an algorithm is a CONCEPT, and that conceptually,
* this represents a non-halting computation. It's not
* just a "program" executing on a specific computing device.
*/
int main() {for(;;);}
No, and ...
No, and ...
No, and ...
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
int main() { while (1); }
while(1); at its end?
No, and ...
No, and ...
Non-mathematical patents
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".
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 be
IMHO 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
Non-mathematical patents
Non-mathematical patents
Non-mathematical patents
Wol
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.
Non-mathematical patents
Non-mathematical patents
"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).
Non-mathematical patents
Non-mathematical patents
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
Non-mathematical patents
Now use the trashcan, put some files in it and throw them away.
Now take another snapshot of the state your computer is in. Call that string B.
The answer to that question is (obviously) yes.
Since such a Turing machine exists, the transformation was an algorithmic one, i.e. describable through an algorithm.
That is precisely the reductionistim view that in my view is not useful when fighting software patents.
Non-mathematical patents
Non-mathematical patents
No, and ...
Wol
No, and ...
around hardware limitation, like e.g. 16bit arithmetic on 8bit CPU or swapping
memory to disk.
names)?
No, and ...
No, and ...
No, and ...
No, and ...
http://en.wikipedia.org/wiki/Algorithm#By_complexity
Algorithms
Algorithms
Genetic patents
http://en.wikipedia.org/wiki/Gene_patent
http://www.pubpat.org/brcafiled.htm
Genetic patents
Genetic patents
Yes but
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
They are all algorithms, with the only difference being the the one who will execute it.
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)
Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)