No, and ...

Posted Jun 5, 2009 6:30 UTC (Fri) by chad.netzer (subscriber, #4257)
In reply to: No, and ... by bojan
Parent article: Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented (Groklaw)

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] (5 responses)

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 (subscriber, #4257) [Link] (4 responses)

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] (3 responses)

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 (subscriber, #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 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 ...

Posted Jun 7, 2009 14:19 UTC (Sun) by malor (guest, #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 (guest, #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.