Determinism, Algorithms and Wikipedia
Orcmid asked me recently, is a nondeterministic process algorithmic?
My answer: yes.
To answer more satisfactorily I needed a definition of algorithmic. There doesn’t seem to be a good one lying around. I looked at the definition of an algorithm on Wikipedia, and as is often the case I found it inadequate. Wikipedia states: ”an algorithm is a finite list of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state.”
Is is widely acknowledged that not all algorithms halt. So clearly termination is not a requirement of an algorithm.
The article goes on to address this: “Some writers restrict the definition of algorithm to procedures that eventually finish”, but then it boldly contradicts itself by saying “The analysis of algorithms for their likelihood of termination is called Termination analysis.”
That is logical nonsense. If an algorithm terminates by definition, then you don’t need to analyze them to see if they halt, because they do. The algorithm is the trival case: return true. Some may argue that I am picking at semantic details, but the question then becomes, what are you analyzing to see if it halts, since it clearly is not an algorithm. Really they should be saying analyzing computational processes to see if they are algorithms, if they are to be self consistent.
Anyway, this all goes to support my thesis that the modern idiomatic usage of the term algorithm includes computational processes that do not halt, and I have no qualms with that.
In fact almost all describable computational processes are referred to as algorithms, which as far as I am concerned is an adequate defintion. A formal definition of algorithm is apparently still up for grabs according to http://research.microsoft.com/~gurevich/Opera/164.pdf.
That paper also describes both “deterministic algorithms” and “nondeterministic algorithms”. If one is to trust the scholarship of the paper, which in my opinion seems sound, then you may be satisfied that nondeterminstic algorithms is not a contradiction.
OK, well Blass and Gurevich make practically everything into an algorithm and I don’t think that is useful. If they’d said computation instead, I wouldn’t quarrel.
I think I’ll stick with Knuth’s account of algorithms in his Art of Computer Programming vol. 1, Fundamental Algorithms. Here, algorithms are (1) finite — terminating in a finite (but not predetermined) number of steps, (2) definite — with each step precisely defined, (3) having zero or more inputs — all available in advance (and finite), (4) producing one or more outputs, and (5) effective — where the steps are simple and easy to carry out in fixed time, even with pencil and paper. These fit what Church was concerned with and Turing as well. (Turing allowed for computations that actually would not end but that would produce better approximations to an answer the longer they ran.) I suppose that Knuth thought it obvious that an expression of an algorithm must also be finite and certainly a computer code that realizes an algorithm must be.
I think nondeterministic computations — as defined for computation theoretical purposes — are not effective and are arguably not definite, now that I look at Knuth’s list. That does not make them uninteresting.
There is no harm in what Blass and Gurevich are doing, since they do not propose to reject or refute Church’s thesis. However, there are those who informally extend the notion of algorithm in such ways (e.g., to allow interaction, for example) in order to claim that CT is refuted. One way to avoid that danger is to be careful in how one broadens the notion of “algorithm.” It is agreed that algorithm is an informal notion, even an abstract one, but this is not generally considered a defect.
I’m one of those who does not consider programs to be algorithms although programs can realize algorithms.
Comment by orcmid — April 27, 2007 @ 6:58 am
“effective - where the steps are simple and easy to carry out in fixed time, even with pencil and paper”
I find that is extremely unsatisfactory. It doesn’t have any precise meaning.
“I suppose that Knuth thought it obvious that an expression of an algorithm must also be finite and certainly a computer code that realizes an algorithm must be.”
I agree that the expression of an algorithm must be finite, but I disagree with any definition that requires is to take finite steps in all cases.
I am not convinced that Knuth’s definition is particularly useful.
So what about those computational processes that are parallel, probabilistic, random, self-modifying, and not neccessarily halting given specific inputs? Many computations in these categories would be called “algorithms” by a large number of computer scientists but would violate the Knuthian definition.
Comment by cdiggins — April 27, 2007 @ 5:03 pm
Knuth’s definition follows that used by the founders of computation theory. Proving the that a procedure terminates is part of establishing its algorithmhood, and the whole analysis of algorithms field is based on the ways that termination (and resource consumption, such as space) are bounded. This doesn’t work for non-terminating procedures.
All of those other computational procedures are fine as they are. Some of them are actually algorithmic (that is, they do terminate, although accomplished by parallel processes), and even terminating non-deterministic procedures have equivalent (deterministic) algorithms (which may have a higher-order of complexity in terms of space/time). There are important questions in computation theory that this division helps keep sharp.
Computer scientists can be just as sloppy as sloppy programmers. Does that surprise you?
It is the case that algorithm is an informal notion, as is its counterpart in mathematical logic, “effective procedure.”
Here’s the tie-in. A specific computational model that captures the essence of effective procedure is the Turing Machine. An important feature of that model is that it is found to be equivalent in what can be represented to what the Church’s lambda-calculus can represent, what the recursive functions can represent, and so on. A Turing machine represents an algorithm in the Knuth sense precisely when it terminates on all (finite) inputs. It is handy, and sharp, to have this be a clear connection.
In particular, notions of computability, the halting problem, and a host of other problems are all relative to this notion and the conditions on it. All of those theoretical results are about finite procedures.
That’s what is useful about it. I think that is valuable to preserve.
My question for you is, why is it important to extend the term algorithm in an arbitrary way for what appears to be a loss of precision with no useful gain? What status do you attach to “algorithm?”
Comment by orcmid — April 27, 2007 @ 11:11 pm
‘The article goes on to address this: “Some writers restrict the definition of algorithm to procedures that eventually finish”, but then it boldly contradicts itself by saying “The analysis of algorithms for their likelihood of termination is called Termination analysis.”’
[I missed this in my first reading.] The author on Wikipedia made a mistake. The reason for testing a computational procedure for whether it halts on all (or a well-defined set of) inputs is to determine whether or not it is indeed the implementation of an algorithm.
The key issue here is that there is no algorithm for determining whether procedures halt if the language of the procedures is sufficiently powerful to express all algorithms on the class of inputs. (The standard case is able to describe all Deterministic Turing Machines.)
So the writer on Wikipedia was tripped up by the casual use of “algorithm” that has crept into our language.
Comment by orcmid — April 28, 2007 @ 5:18 pm
Notice that I used “algorithm” very carefully in the third paragraph of the previous comment.
I just found a great link page, thanks to Richard Zack:
http://www.ucalgary.ca/~rzach/logblog/2007/04/videos-of-lectures.html
If you go to the page of online videos on philosophical topics
http://broodsphilosophy.wordpress.com/2006/06/15/online-videos-of-philosophical-lectures/
you’ll find a number of interesting topics and lectures. Scroll down to the title “The Origins and Nature of Computation” and you’ll find three interesting videos. They require Windows Media Player 10 to view. I started looking at the Martin Davis one just to make sure it played. There may be some useful material here in the Davis and Kripke lectures.
Comment by orcmid — April 28, 2007 @ 5:26 pm
I want to point out another example of a definition of an algorithm that supports my interpretation. Cormen, Leiserson and Rivest informally define algorithm in “Introduction to Algorithms” as “any well-defined computational procedure that takes soem value, or set of values, as input and produces some value, or set of values as output”. Of course on the next page they go on to say: “An algorithm is said to be correct if, for every input instance, it halts with the correct output” and then “incorrect algorithms can sometimes be useful”.
As someone who is interesting in program transformation and optimization, non-halting computational processes or “incorrect algorithms” is a big part of what I am concerned with.
I’ll summarize my position that common usage of the term algorithm to refer to any computational process is simply too far reaching and too convenient for me to not use it as such.
I do appreciate the discussion but you’ll forgive me if I don’t it any further, I’m really getting behind in my other work :-)
Comment by cdiggins — April 28, 2007 @ 6:44 pm
I still don’t understand why “computational process” (or “computational procedure”) isn’t far reaching enough for any computational process? Why appropriate algorithm and force us to come up with a new name for the traditional limitations on algorithms that computation theory is founded on?
I’ll put this on my own blog. We both have work to do, yet this is a very strange situation worth putting a marker on, from my perspective.
[PS: I’d be surprised if you’d be happy having released a non-terminating transformation heuristic, and I am not quarreling with the value of non-terminating computational processes one bit.]
Comment by orcmid — April 29, 2007 @ 5:49 pm