LWN: Comments on "Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)"

No, and ...

mcortese — Fri, 19 Jun 2009 16:41:35 +0000

An algorithm must terminate, a program need not.
int main() { while (1); }

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?

Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

lysse — Thu, 18 Jun 2009 10:41:23 +0000

"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. :)

Algorithms

sepreece — Thu, 11 Jun 2009 14:01:57 +0000

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.

No, and ...

malor — Thu, 11 Jun 2009 11:27:33 +0000

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.

Algorithms

jlokier — Wed, 10 Jun 2009 01:14:45 +0000

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.

Genetic patents

Seegras — Mon, 08 Jun 2009 10:20:09 +0000

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.

Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

Wol — Sun, 07 Jun 2009 19:38:05 +0000

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,
Wol

No, and ...

malor — Sun, 07 Jun 2009 14:19:33 +0000

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.

Non-mathematical patents

man_ls — Sat, 06 Jun 2009 11:18:44 +0000

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

man_ls — Sat, 06 Jun 2009 11:08:31 +0000

"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

man_ls — Sat, 06 Jun 2009 10:22:54 +0000

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.

No, and ...

chad.netzer — Sat, 06 Jun 2009 02:03:32 +0000

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
http://en.wikipedia.org/wiki/Algorithm#By_complexity

Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

coriordan — Fri, 05 Jun 2009 22:59:13 +0000

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.

No, and ...

chad.netzer — Fri, 05 Jun 2009 18:45:26 +0000

"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 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(;;);}

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 ...

flewellyn — Fri, 05 Jun 2009 16:56:51 +0000

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".

Non-mathematical patents

sepreece — Fri, 05 Jun 2009 15:59:55 +0000

"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 ...

papik — Fri, 05 Jun 2009 15:52:34 +0000

> 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
around hardware limitation, like e.g. 16bit arithmetic on 8bit CPU or swapping
memory to disk.

And maybe this software should be patentable.

But then... what about software to work around software limitation (FAT long
names)?

Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

sepreece — Fri, 05 Jun 2009 15:37:06 +0000

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...

Non-mathematical patents

man_ls — Fri, 05 Jun 2009 15:13:58 +0000

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.

No, and ...

sepreece — Fri, 05 Jun 2009 15:10:16 +0000

"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?

Non-mathematical patents

sepreece — Fri, 05 Jun 2009 14:58:29 +0000

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.

Yes but

forthy — Fri, 05 Jun 2009 14:04:05 +0000

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)

nlucas — Fri, 05 Jun 2009 13:19:27 +0000

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)

MathFox — Fri, 05 Jun 2009 12:18:35 +0000

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)

tao — Fri, 05 Jun 2009 12:10:00 +0000

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).

Non-mathematical patents

Zack — Fri, 05 Jun 2009 11:34:00 +0000

>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.
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.

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?
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.

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.

Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

nlucas — Fri, 05 Jun 2009 11:25:00 +0000

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.

Non-mathematical patents

Wol — Fri, 05 Jun 2009 10:47:01 +0000

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,
Wol

No, and ...

Wol — Fri, 05 Jun 2009 10:39:54 +0000

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,
Wol

No, and ...

bojan — Fri, 05 Jun 2009 10:37:07 +0000

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.

Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

Wol — Fri, 05 Jun 2009 10:29:01 +0000

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,
Wol

No, and ...

chad.netzer — Fri, 05 Jun 2009 09:18:55 +0000

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.

Non-mathematical patents

k3ninho — Fri, 05 Jun 2009 08:36:23 +0000

>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.

Genetic patents

luya — Fri, 05 Jun 2009 08:17:04 +0000

That only show how broken and corrupt the whole patent system is in the USA.

Non-mathematical patents

luya — Fri, 05 Jun 2009 08:13:30 +0000

"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

bojan — Fri, 05 Jun 2009 07:16:42 +0000

> 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

drag — Fri, 05 Jun 2009 07:14:17 +0000

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.

No, and ...

bojan — Fri, 05 Jun 2009 07:03:52 +0000

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 ...

chad.netzer — Fri, 05 Jun 2009 06:30:01 +0000

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.

Non-mathematical patents

man_ls — Fri, 05 Jun 2009 06:16:40 +0000

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 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.