Talk:Algorithm

To-do list for Algorithm:

edit · history · watch · refresh

Cleanup the article. -- moved to section in talk page -- Rewrite the history section Ancient algorithms (Babylonians, Euclid, Sieve) Formalization -- done -- (Godel's and Herbrand's λ-calculus (cf footnote in Church's paper, p. 90 in Undecidable ), Church's theorem (1936) (p. 88ff in Undecidable), Post's "process" (1936) (p. 289ff in Undecidable), Turing's machine (1936-1937) (p. 116ff in Undecidable), J.B. Rosser's definition of "effective method" in terms of "a machine" (1939)(on p. 225-226 in Undecidable), Kleene proposing the "Church-Turing thesis" based on the papers of Church and Turing cited here (1943) (p. 273-274 in Undecidable)

Revised history section -- background information

Please observe that "the archives" above contain extensive "history" background information for any writer willing to take on the task of reworking the history. The move to "archive" has rendered this work invisible. If no writers or editors can get to this I will eventually.

Frankly I don't think this "cleanup" is a good idea unless a way exists to move an index of the archive to this discussion page. wvbaileyWvbailey 03:59, 11 July 2006 (UTC)

Archiving is standard procedure for a long talk page. You can still get to it with the link. --Ideogram 04:03, 11 July 2006 (UTC)

"Isomorphic?"

G'day, I've got basic maths and computing skills and I don't know exactly what is meant by "isomorphic" in this context...for the lay people a clarification would be great! ben 16:08, 11 July 2006 (UTC)

Additional content

Somebody should add a section about the fact that algorithm is not a well defined term. Everybody knows what it means to say that two computer programs are the same, or are different, as programs. But there is no accepted formal definition of when two computer programs (possibly in different langauges) implement the same algorithm. CMummert 20:35, 14 July 2006 (UTC)

I agree. And there's more: Some argue that the interpreting mind (or machine) is part of the algorithm. I had a dialog with Yuri Gurevich (he's at Microsoft as a senior fellow) re this issue: the definition of "algorithm". See the archived discussion section for my dialog re recent Uspensky-Gurevich papers. I believe that Gurevich leans toward the view that I lean toward -- that an algorithm must be expressed as a machine in operation (e.g. a Turing machine -- both table and tape -- or a mind), not just a list of instructions (i.e. a list of cookbook instructions, or the "Turing Table"), or even as a state machine (i.e. "Turing Table") in operation. But I'm not sure about exactly what Gurevich is saying; I'm still reading on this. I'd welcome your input if you're so inclined. wvbaileyWvbailey 00:46, 15 July 2006 (UTC)

Sorry, wrong references -- the first paper is Andreas Blass and Yuri Gurevich, Algorithms: A Quest for Absolute Definitions, Bulletin of European Association for Theoretical Computer Science 81, 2003; and Yuri Gurevich, Sequential Abstract State machines Capture Sequential Algorithms, ACM Transactions on Computational Logic vol. 1, no 1, July 2000, pp. 71-111. Both papers can be found via Google at Gurevich's site at Microsoft where he can be reached at guerevich@microsoft.com. And here is another paper: Yuri Gurevich, On Kolmogorov Machines and Related Issues, July 2000. The early work on this was by Kolmogorov and Uspensky. Sorry, I'm on vacation and am a bit discombobulated. wvbaileyWvbailey 05:10, 15 July 2006 (UTC)

merger from Church-Turing thesis

Oppose merge. I agree with Cornflake pirate that there is some duplication. I have started a discussion at Turing machine about how to clean up that page. That cleanup will require links to Algorithm and Church-Turing thesis. I don't think it makes sense to merge Algorithm and Church-Turing thesis, because that merges two out of three important ideas, viz:

The Church-Turing thesis says that any algorithm can be implemented on a Turing machine.

Each of those bold terms has enough content to justify an article. In particular, the history of Church's thesis and its various forms are not relevant to the Algorithm article. The first section of the current Church-Turing thesis article could be moved into Algorithm and drastically shortened in place. CMummert 14:12, 16 July 2006 (UTC)

Yes that's what I intended, not the entire article. :S --Cornflake pirate 01:09, 17 July 2006 (UTC)

• Indeed there is some duplication but I don't think there's any potential for an actual merger. The Church-Turing thesis article just needs to be rewritten to take full advantage of the existing articles for algorithm and Turing machine. Pascal.Tesson 14:19, 16 July 2006 (UTC)

• Oppose Merge. The topic clearly deserves its own article. No trees are harmed in repeating some content in two different contexts. Jon Awbrey 15:25, 16 July 2006 (UTC)

• Strongly oppose merge. Algorithm is much different than Church-Turing Thesis. See the history section in the archived discussion for why this is true, plus my brief discussion of work of Komogorov-Uspensky and Andreas Blass-Yuri Gurevich immediately above. The Church-Turing Thesis is a historical fact, the result of Kleene's formulation of the work of Church-Turing-Emil Post; the definition of algorithm is in flux. wvbaileyWvbailey 16:03, 16 July 2006 (UTC)

• Oppose merge per other opposing comments. --Allan McInnes (talk) 16:58, 16 July 2006 (UTC)
  • Support merge. I withdraw my opposition now that the merge proposal has been more clearly defined, i.e. that it covers just the Church-Turing thesis#Algorithms section. --Allan McInnes (talk) 01:20, 17 July 2006 (UTC)

• Oppose merge. This article should not have the detail needed in the other. -R. S. Shaw 21:18, 16 July 2006 (UTC)

• Oppose merge. I too agree with the above. Cedars 00:17, 17 July 2006 (UTC)

I left a comment for the user who suggested the merge. Nobody, no even that user, has spoken in favor of the merge, so for now let's agree it isn't happening soon. CMummert 00:28, 17 July 2006 (UTC)

• Comment It's not a merge of the entire article, just the "Algothms" section of the Church-Turing page, which clearly does not belong in that article, however the information there does not seem to be present in this article. --Cornflake pirate 01:03, 17 July 2006 (UTC)

Proposal to merge just "algorithms" section of Church-Turing page

• Opposed until certain editors of the algorithm page allow the "algorithms" section of the Church-Turing thesis page to appear here in substantially the same form as it appears on that page. Certain person(s) reverted my work here because it had "too much quotation from an original source" and they feared copyright problems. (They are clearly confused). To avoid a reversion war I moved it there because it is necessary for an understanding of the Church-Turing thesis. After I have time to rework the history section (etc.) on the algorithm page with some of the material, then I agree it can be removed. But not until the algorithm page is reworked. wvbaileyWvbailey 01:30, 17 July 2006 (UTC)
• Comment I've been bold and done the merge myself. I'll do a bit of work on it and if there's a reversion war then we can deal with that if it happens. :) --Cornflake pirate 01:35, 17 July 2006 (UTC)
  • Actually I did revert it. It feels like you've just copied a section across and made little effort to integrate it with the article. Much of what was copied seemed to be repeated later in the article section "Formalization of algorithms". This was a good article before the merge, though it can be improved, it will take some effort to improve it and add new content. Maybe a subsection "Knuth's definintion" in the "Formalization of algorithms" would work or even a sub-article? Cedars 04:50, 17 July 2006 (UTC)

The WP:MM page says that just dumping the information, and leaving it for others to clean up, is fine. I don't think that reverting it helped anything. I moved the content to a separate section, which is where it should have been all along. I also edited it down some. The stuff by Kleene (commented out now) belongs back on the Church-Turing thesis page. I am not sure that I favor the large number of footnotes; I think a single reference is enough for a contiguous series of quotes. Another subsection should be added emphasizing that there is not a formal defintion of algorithm, and that moreover it is a subjective question as to whether pairs of programs implement the same algorithm. (This replaces my previous comment). CMummert 12:57, 17 July 2006 (UTC)

I agree that we could get away with less footnotes. I added them in the first place because they reflected the existing in-text references in the merged text, with the intent of trimming them down later if User:Wvbailey was amenable to doing so (he had previously stated that the section should be in "substantially the same form"). --Allan McInnes (talk) 13:59, 17 July 2006 (UTC)

The new section re Knuth and edits look good to me. Since the reference to Knuth's work is already on the page only an in-text reference such as (Knuth 1973 p. 1-9) is required; a footnote isn't necessary. Also, the Knuth reference is annotated to precisely direct the reader to those pages. But CMummert's observation re "no formal definition of algorithm" is quite important and needs to be added perhaps just below. (The "history" section -- actually the history of modern attempts to define "algorithm" -- is so large it may have to go on a separate page. Title suggestions, anyone? But Knuth's is the most "famous" and well-known and should stay here.) wvbaileyWvbailey 16:08, 17 July 2006 (UTC)

Result

In this edit, the section Church–Turing thesis#Algorithms disappeared. Anthony Appleyard 09:30, 28 January 2007 (UTC)

Formal characterization of Knuth

I moved this from the main article

He goes on to provide a "brief indication by which the concept of algorithm can be firmly grounded in terms of mathematical set theory." (Knuth p. 7). He defines a computational method as a quadruple (Q, I, Ω, f). "The four quantities Q, I, Ω, f are intended to represent respectively the states of the computation, the input, the output, and the computational rule." Q contains subsets I and Ω; f is a function of Q onto itself. (He places further restrictions on his variables and functions; in a following paragraph he addresses the issue of effectiveness. For details see Knuth p.7-9 and his reference to Markov).

I don't doubt that Knuth said it, but it doesn't fit with the general consensus that there is no mathematically rigorous definition of algorithm. That is, his proposed mathematical definition is not accepted as a correct formal characterization. It doesn't serve the article to pretend that such a definition has been given. If anything, the brief characterization here makes it look like Knuth has just redefined a Turing machine. CMummert 12:24, 25 July 2006 (UTC)

I wondered when this would disappear from the main article and who would 'disappear' it -- I figured it would be gone by morning. As I wrote it I was thinking that really, the article is not too good. "Algorithm" is "locked up/swirls around" with "lambda-calculus/recursion" and "Turing machines" and "Post calculations" and "Kolmogorov machines" etc. etc. (i.e. "foundations[?]"), with "logicism versus intuitionism versus formalism" i.e. the problem of "constructability/demonstrability" of a number via an "algorithm", and with my question: is "an algorithm" just a set of cookbook-like instructions (cf Knuth's discussion page 4) or is it a Turing-equivalent-machine/man-as-machine-doing-recursion in operation (cf my dialog with gurevich@microsoft.com -- he says there aren't any good texts on the issue of what an algorithm really is -- I'm still pursuing this). All this ambiguity -- and some of the current opinions -- needs to be emphasized in the article (with in-text citations to the authors of the opinions). Am working on this slowly. Advice is welcome.wvbaileyWvbailey 17:26, 25 July 2006 (UTC)

I agree there is no censensus on how to formalize the natural language meaning of the word algorithm. It is easy to tell whether two programs are the same - you just compare them. It is not easy to tell whether two programs implement the same algorithm; the equivalence relation of same algorithm is coarser than the relation of same program. But the relation same partial computable function is coarser still, because for example there are many different sorting algorithms. So a formal definition of algorithm cannot identify it with its result (the computable function) or with the specific program that implements it. Knuth's characterization illustrates properties that an algorithm must have without giving a definition of what an algorithm is. CMummert 17:42, 25 July 2006 (UTC)

It's interesting to note that you and I are waltzing back and forth between the "algorithm" and "Post-Turing machine/Turing machine" pages. Not too long ago I was working on the "intuitionism" page. Clearly the first two are tightly woven, and the "intuitionism" page sensitized me to the idea of a 'constructive demonstration', i.e. "an algorithm". wvbailey

I've probably asked you the following before, if so, sorry 'bout that ... Do you have an opinion re whether or not an algorithm is "a machine/man" in operation, or whether it is just a list of instructions? Do you know of any good writing on this? wvbailey

Knuth seems to waffle, as does everyone else I've encountered. He says: "Besides merely being a finite set of rules which gives a sequence of operations for solving a specific type of problem," (p. 4) the algorithm has the five features: finiteness, definiteness, input, output, effectiveness. But he always slips into a use of active verbs, such as [my boldface] "the algorithm ... terminate[s]" (p. 4), "... before the algorithm begins" (p. 5), "the reader is supposed to understand exactly what it means to divide m by n and what the remainder is" (p. 5 -- i.e. if "reader" is to hand-execute Knuth example algorithm, "reader" must be able to read the instructions and "do the math" -- your point some days ago), etc. wvbailey

Thus we are led to believe that "an algorithm" isn't just a list of instructions -- that is merely the finite state table giving the "transformation rules". The algorithm is also "the tape" with an instance of input on it, and blank tape for "the output". And we know that "tape" is required to do e.g. arbitrary multiplication -- a "very finite" (Knuth, p. 6), so finite-state machine won't do the job. wvbailey

Everyone I've run into (Post, Turing, Kleene, Rosser, Knuth, Kolmogorov, Gurevich, Minsky) suggests that an algorithm implies the existence of an "interpreter" aka "device or man" capable of, and actually in the act of, converting "the list of instructions" into physical movement (and I mean actual real-world physics here -- motions of parts, mechanical or human -- leading to "an output" in material form). Without this "the algorithm" is just paper -- mulch for the garden. The algorithm is my black boxes -- in goes the tape with "the input", out comes the answer. Inside the box is "the algorithm", aka "Turing machine under power" or aka "little man with fast fingers eagerly anticipating the next calculation". There must be some modern thinking re the definition. But Gurevich says not too much. Ideas? wvbaileyWvbailey 19:26, 25 July 2006 (UTC)

My way of thinking is that the word algorithm is an important natural language term that is not particularly amenable to formalization. Nevertheless, there are several people (including Gurevich) who are doing interesting work that makes some progress towards the goal of a formal theory of algorithms. CMummert 02:42, 26 July 2006 (UTC)

Formalisation of algorithms - proposed change

At the moment the "Formalisation of algorithms" section is broken down into:

1. Knuth's characterization
2. Expressing algorithms
3. Implementation

This fails to show the different formalisations of an algorithm and focuses heavily on Knuth's characterisation. I think this section should focus on the different bodies of mathematics that formalise what an algorithm is. Something like:

1. Turing machines (and the Knuth material)
2. Recursive function theory
3. Logic

They are not just types of programming language. Both lambda calculus and formal logic can be used to define what a computable function (and therefore algorithm) is.

Is there anyone for/against this approach?Pgr94 11:39, 26 July 2006 (UTC)

I am against it. An algorithm is not the same thing as a computable function (because there are many different sorting algorithms that all do the same thing) and is not the same as a Turing machine program (because a particular algorithm, such as quicksort, is the same algorithm even when implemented in different programs). There is no formalization of algorithm (but there is a formalization of computable functions). The point of the Church-Turing thesis is that any algorithm (in the informal sense) can be programmed into a Turing machine (the formal sense). As a separate point, recursive function theory probably means computability theory which overlaps with Turing machines. CMummert 13:29, 26 July 2006 (UTC)

I am against it, at least until we have better references and attribution practices. I believe I have added all but one of the references, and there are more I haven't had time to investigate (Markov, Kolmogorov, any others?). The Knuth entry is NOT ambiguous as to who said it; although I agree that the fact that it is an opinion may not be so clear (CMummert's complaint back a few weeks ago), it's just fine for the time being. When I first encountered this page someone had cribbed the Stanford Encyclopedia without attribution and then someone else observed this and it was removed (it was Knuth's description in disguise). I do agree that more authors' opinions could be added, and I suggest that more should be added. For example: I could quote Gurevich (and why not? It's in the literature! It may not be the truth the whole truth and nothing but the truth (e.g. CMummert seems to disagree with the following) but the quotes are facts-- as in "attributable statements"):

"...Turing's informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine" (Gurevich 2000 p.1)

"...according to Savage [1987], an algorithm is a computational process defined by a Turing machine."(Gurevich 2000 p.3)

"...every sequential algorithm can be step-for-step simulated by an appropriate sequential ASM [Abstract State Machine]"(Gurevich 2000 p. 2)

Pretty bold stuff: ANY algorithm! Godel came to the same conclusion (see my history stuff in the archived discussion). To CMummert's point immediately above, for a discussion of the distinctions between the Church-Turing thesis versus the Church Thesis versus the Turing Thesis -- in the context of "algorithm" -- I recommend Gurevich 2003.wvbaileyWvbailey 17:07, 26 July 2006 (UTC)

I have some knowledge of the work of Gurevich and Blass on abstract state machines. This work is interesting because it may lead to a commonly accepted definition of what an algorithm. But I do not think that it has reached that status yet. Gurevich's claim that any sequential algorithm can be simulated step by step by an ASM follows from his definition of sequential algorithm, which corresponds very closely to the definition of an ASM (so it is not so surprising). I am agnostic about the name for Church's thesis. CMummert 23:15, 26 July 2006 (UTC)

I agree with you (... no reflection on Gurevich's work in particular but I don't believe folks working on this have bitten "the really Big Bullet" (really Big Bullet -- TBD). But his "modern" viewpoint might be a nice addition to the article.wvbaileyWvbailey 00:47, 27 July 2006 (UTC)

For CMummert (and anyone else so inclined): I'd appreciate your help with the Gurevich part. I am confused as to exactly what is new in the point of view he represents (which I can't follow excepting he's got the advantage of more models (Kolmogorov machines, pointer machines -- B.T.W. i created a new page for that one but its just a skeleton)).Lemme know. Thanks. wvbaileyWvbailey 20:57, 28 July 2006 (UTC)

complaints about algorithm article

Copied from "to do"

• • move most of the information added in history to a page like "history of computing" and keep absolutely related history to algorithm here.
  • give references to other pages and do not write more than simple paragraph about all those different formalisations here.

This article was used to be so nice to explain what algorithm is, and its brief history and list various algorithms and fundamentals. It was good reference for people looking for information on algorithm or for that matter for non computer scientists. Honestly it is boring and prosiac now and scares away any quicktime readers.

---

Problem is:

1) nobody knows, and therefore cannot agree to, what an algorithm is ... so,

2) any definition is difficult... and must be cited as an opinion... not fact

3) people have their opinions about the "best definition", they have their favorites

One person didn't like so much emphasis on Knuth, so we add more authors' opinions...and now the reader complains there's too much definition,

4) Knuth's definition was put here because it is the most common, and it was moved from another page to where it belongs,

5) another wants more history -- and so we add what we believe is germane -- algorithm has to do symbols and rules and mechanical devices , and then a reader bitches its too much and yada yada yada whaa whaa whaa...

Eventually what we can do is reduce the page by the use of sub-articles, i.e. "Definitions of algorithm", "history of algorithm", whatever. If there were a common definition for "algorithm", then the article could be simplified. But all we will see will be more complaint. About the only summary text that can be written is sthe following, the rest is innuendo [aka opinion]:

"There is no agreed-to definition of algorithm. Over the last 200 years the definition has become more complicated and detailed as researchers have tried to pin down the term. Indeed there may be more than one type of "algorithm". But most agree that algorithm has something to do with defining processes for the creation of ["output"] integers from other "input" integers -- "input parameters" arbitrary and infinite in extent, or limited in extent but still variable -- by the manipulation of distinguishable symbols [numbers] with finite collections of rules that a man can do with paper and pencil. The most common schemes for manipulation are: (1) the λ-calculus, (2) recursion, or the (3) Turing machine or its Turing equivalents -- i.e. the computer. The hypothesized equivalence of these formulations is called the Church-Turing thesis. See History of algorithm for what led up to, and steps in, the effort to better understand and define the notion of "algorithm", and Definitions of algorithm for various, more-precise formulations [aka opinions].

wvbaileyWvbailey 14:24, 24 August 2006 (UTC)

---

Yes, please let us do the subarticles as mentioned by you.

1. IMO, the algorithm is more computer science related term, and kunth's definition makes more sense. Other formalisations did not use the term algorithm initially, and tried to propose a computing model or mathametical theorem. Now we all know all of these formalisations are same as or similar to concept of algorithm. But that does not justify their lengthy details and history in this article. This article should not be about researching the right defintion of algorithm or proving that all computing models are same as algorithm, but shoud be about the concept of algorithm, properties of algorithm and the breif background.

I agree that the article is too long and too diffuse. I have created a new page Algorithm characterizations. Other suggested names are welcome.

Thanks a lot for doing this! It is cleaner. The charecterizations article is looking very nice in its own. mlpkr Mlpkr 10:41, 9 September 2006 (UTC)

Many researchers - Markov for instance -- actually titled their work "defintion of algorithms" or whatever. This is serious stuff, this definition of algorithm. The reader should be shown just how serious this is for mathematical foundations. See the long discussions on the Turing machine page and this page. It also impacts on Intuitionism, Finitism, Hilbert's Problems, Constructivism, and problems in Philosophy of Mind. wvabailey Wvbailey 19:10, 8 September 2006 (UTC)

Why do you think there is no agreed defention of algorithm? You may say different people define algorithm with different terminology, but all of them mean it as a step by step mechanical procedure to get outputs from given inputs. The wordings are different, but meaning is same.

This is your (very) informal definition and I don't disagree. But as you look into this deeper the problem gets difficult. The reader needs to know that this is a difficult topic: that there are serious issues having to do with the notions of "quality -- goodness, best", with the capabilities and knowledge of the machine/person, with whether or not the algorithm should come with its own "embedded" instructions for use. But in what language should the instructions be written? What symbols should be used?

Think about passing parameters to a subroutine. In what form will the parameters appear (string, constant, matrix, decimal, binary, unary??) Where (in what register, memory, whatever) will they be passed? In what form will they be returned? Where will they be returned? This looks easy when you're doing C programming -- C programmers are so spoiled ... they've forgotten that low-level calls may be passing through registers and both caller and subroutine have to agree to the location and the format of the parameters in both directions etc. etc. This becomes very very important when you drop down to the Turing machine or register-machine level (or the assembly-language level). And here is where the defintion-problems start.

You may touch this lightly in one paragraph somewhere, expression algorithm is varied based on the situation and application. It may also be expressed just as mathamatical technique, or cab be coded in pseduo code, expressed in flow charts, or running as software, or implemented in hardware chip. Its inputs and outputs can be integers, strings or any other data types, or even bits or bytes depend on the conext where algorithm is being applied or used. mlpkr Mlpkr 10:41, 9 September 2006 (UTC)

I have given some consideration to giving such an example to make the point, but haven't decided whether or not its original research. It is an interesting topic. One author talks about three levels of definition: a natural language, a semi-formal, and a pure formal definition. But in what language? You have to specify the machine and its language/syntax, parameters etc. down to the tiniest of details.

Just the fact that Blass and Gurevich are working on "the definition of algorithm" at Microsoft (I've been in touch with Gurevich) and there are other researchers as well indicates that this is a non-trivial topic. wvbailey Wvbailey 19:10, 8 September 2006 (UTC)

This is completely wrong. The poster that you are replying to is entirely correct. In thousands of research papers an algorithm is considered to be such a basic part of the field of computing that it is either mentioned in passing, or defined in a couple of sentences. There is no great controversy about what an algorithm is anywhere but on this wikipedia page, which seems to have confused the notion of a program with that of an algorithm. An algorithm is a mechanical procedure for computing an output from a given input. There are no issues of termination (and that entire section should be deleted) as algorithms are not programs. They are specifications of programs. There are no issues about the language that algorithms are specified in (as psuedo code is normally used), again this is a confusion with programs. The fact that Kleene may have used the term algorithm in the 50s is not a good indication that the programs that he was describing are what we think of as algorithms in the field. I've quickly looked up Blass's research and it not indicative of the common usage of Algorithm.

As someone with a PhD in this field I think the article is a terrible mess. It has tried to be complete and accurate, rather than readable and interesting. In the process it has failed to be any of these adjectives. To restore this article to it former quality it is necessary to stop the endless circling around whether or not we know what an algorithm is. We do. It does not require a citation, because as I've pointed out the definition is unchanged across hundreds of textbooks and thousands of papers. It is a common foundation in the field, and these attempts to find a definite citation to back up a single wording of the definition have destroyed this article. Wikipedia is supposed to be an encyclopedia, not a CS textbook. If something is in common usage then it should be stated as such and defined broadly. Amoss 13:31, 11 July 2007 (UTC)

Of course you are entitled to your opinion, but that opinion is not necessarily correct. But please speak only for yourself: not " we do, rather I Amoss do know what an algorithm is". And perhaps you do: If you've published something in this regard please present where it can be found and then someone can look at it; perhaps it should go on the algorithm characterizations page. If I can find it in the library then it is as legit as the next guy's opinion. Please read algorithm characterizations; you will see a series of different views from Kleene forward. What this article does is trying to do is survey the field. If you have something positive and constructive to add please do so but please do so with in-line citations and complete references -- citations are mandatory and without them reversion is certain. In particular if you can speak to the Gurevich point of view in an expert manner, that point of view needs expert assitance. As does verious sections of the article (patents, etc). The references quoted there algorithm characterizations are quite explicit as to various points of view (and contrary to what you've written above there is a lot of debate). Your point of view has merit, but it is a point of view; it is not fact. wvbaileyWvbailey 03:00, 12 July 2007 (UTC)

No, you have not addressed my comments. The concept of an algorithm is a well understood part of Computer Science. In peer-reviewed papers it is not necessary to define what an Algorithm is because there is a commonly understood definition. In trying to find citations for the definition of a basic term you are trying to hold Wikipedia to a higher standard than the original research that it is reporting upon. As this page covers the historical progression of the term, as well as its current meaning then it makes sense to refer to work from the 50s before complexity theory and other developments, when the term had a more general meaning. It does not make sense to try and generalise the term to include its earliest meanings. (Almost) all of the definitions that you list on the characterizations page have a common core. The final entry about Blass is straying into original research. Their paper is an attempt to redefine the term algorithm, for their own agenda, and has no place in an encyclopedia entry on the subject. The distinction between an algorithmic process and a reactive process has been settled since the mid 80s when Pnuelli wrote his classic survey paper on the subject. Having read the chacterizations page I am worried that the compiler of the information does not understand the difference between a program and an algorithm. Furthermore, the juxtaposition of quotes confuses the issue because terminology has changed over time. At one time (the 50s) the terms algorithm and program and computation were interchangable. This is no longer the case, and to treat it as such by taking older work out of context is to overcomplicate the subject.

So that we don't spend time running in circles. What kind of citation do you feel is relevant to show that the term Algorithm is a basic term? The previous layout of the page used Knuth as a basis. Given that Knuth wrote that material in the 80s, normally a citation to Knuth is considered enough to show that the term has a common usage. Second question, why is there a terrible section on termination? Apart from the early quotes on the characterizations page (which refer to programs) all of the definitions agree that Algorithms are finite in execution. Amoss 12:03, 12 July 2007 (UTC)

2. It is not bitching. I would suggest to read the article from common reader point of view, or ask opionion of common readers. I am not discouraging your efforts, but requesting you to make this as an article instead of a text book.

Your point is good. I've worried about this, and I don't disagree. Wvbailey 19:10, 8 September 2006 (UTC)

3. Symbols and mechanical devices, telephony etc. are more related to a broader concept of computing/computer. Their lengthy details here makes this article disconnected and do not create a smooth flow of information. Suppose I am searching for algorithm on a search engine and this page comes up(as it is now), I have to read about mechanical devices, various mathematical models and and old computers. I realise that this is roundabout and lengthy prose after a while and go to next search results. This is subjective opinion anyway and I feel the case is same with many people.

Another good point. I moved the stuff to the end. Whether or not it should go to its own page... I disagree at this time. See the improvements requested for the page. The point of the history, which might need a summary paragraph, is that the informal definition of "algorithm" at the beginning of the article has evolved over many thousands of years, starting with the idea of discrete, distinguishable, one-to-one mapping of symbols with things like sheep and money; then the Greeks' generalized instructions for geometry constructions and "number constructions", then the absorption into Western culture of the Arabic numerals and the Persion notion of "algebra" to construct numbers with generalized processes as symbolized by discrete "variables", through the invention of the clock with its discrete tick-tock leading to "automata" (mechanical music box figurines, for instance) and finally the engineering, philosophic and mathematical advances of the past 200 or so years that led us to "recursion" and "λ-calculus" and "Turing machines" and "Halting problems" and computers and undecidablility and intractability. Only a fool would believe that we are at the end of this development. Hence the evolving definition of algorithm. Wvbailey 19:10, 8 September 2006 (UTC)

Writing a paragraph of history here and moving to another page like "algorithm evolution" is okay in my opinion, but I also do not object your present format of moving the detailed history to the end, as this gives the enthusiastic reader more material. Thanks again for doing that. Mlpkr 10:41, 9 September 2006 (UTC)

No problem. Your tactful criticism has improved the article. We're just here to make a really great article. (As more and more folks add more and more stuff, eventually the history may have to go to its own page).

I would appreciate your opinion here: I can't tell if this would be "original research" or not. I would like to provide a vivid example of some of the issues (like parameter passing problems). A good example is the the "multiply algorithm" (it executes Peano's definition of multiplication with two recursive loops in the simplest form) using a Register machine or Post-Turing machine. I can do either; the register-machine is easier to understand. So far, there is plenty of historical precedent behind the two models of machines so there is no "original research" going on if I just stick to a "standard model" (Shepherdson-Sturgis register- machine model seems the most promising)... [but as I write this, maybe the Melzak-Lambek model would be better (the Melzak model allows full addition, the Lambek model just increments and decrements)] anyway ...

This is definitely not orginal research.

But the best example would be a hybrid of both machines (a P-T machine equipped with one register functioning like an accumulator) because the register machine uses "numbers" and the P-T machine uses unary coding -- so we can see vividly that "the user" must be instructed both how and where to put the "input strings" (of ones, i.e. "multiply"(a,b)) and where to read the output (as a decimal in the register, or as a string of ones on the tape...). If we further simplify the multiply by equipping the register with an "adder" (i.e. "contents of memory n" + "contents of A" --> A) and we use it in an algorithm to calculate powers (e.g. a^b), we see a startling result -- that a trivial change in how we design the algorithm makes all the difference between a really poky machine (N^2) time and a fast machine (linear time). This gets to the "quality/goodness" issues -- the-time-to-execute issues.

In my opinion, this is evolved over years of research, and not our original research. Many computer theory books like Sipser use such high level abstraction for solving many problems. Also in computer organisation or computer architecture books, when they talk about designing circuits for multiplication, power etc. using low level blocks like adders and registers, they are actually talking about algorithms in a sense that a hardware circuit is an implementation of algorithm.

This example might go into the characterizations page or even on its own article-page. Your thoughts? Thanks. Wvbailey 20:07, 9 September 2006 (UTC)

If you are going to give as described here, it may go to Characterizations page for now. I think putting this in separate article-page like "Algorithm dependency on machine model" is also okay, but we can do it later. It can be extended to explain more about algorithm goodness depends on its implementation. I am giving some more text for that article in the raw form. Please rephrase and digest yourself before adding. "A solution(logic for solving a problem) when expressed(in a theoritical model) or implemented(in a practical model) becomes an algorithm. As the expressing means or implementation means change, they could become different(possibly efficient) algorithms, although they all of those algorithms for the same problem may have originated or evolved from the same solution. Efficient implementations allow bigger inputs in old model to be treated as basic inputs. The machine models limit the efficiency of any possible algorithm. The present Von Newman models are slightly superior(more efficient) to turing machine in the sense that they will treat integers as basic units and allow complex operations on them to be done in unit computing time, like doing it on bits of the number. Yet, they have no more power than the turing machines, as they can not solve new problems that turning machine can not solve. This is one of the reasons why the concepts like the solvability and tractability of the problems are still studied with abstract models like turing machines, but algorithms for solvable problems are discussed with high level implementations and formalised in high level languges close to current technology". mlpkr 2:48, 18 December 2006 (UTC)

I've kind of lost the thread of this discussion .... Since 9 September I just went ahead and created some examples in a new Algorithm examples article (done in October). I will look at what you wrote above and digest it. I have sprinked examples in other articles, for example on the partial function page there is an example of (im-) proper subtraction and how the algorithm can be redesigned to make it "proper".

There seems to be confusion with respect to total versus partial functions (algorithms) -- for example in Kleene (1952) where he suggests that any partial function (algorithm) be put into an infinite loop (and therefore non halting) given that we can detect the error (e.g. in an output with an incorrect format). (In the partial function article I raise the horrible possibility that the algorithm does terminate correctly, but with the wrong answer! So we need an independent proof of the algorithm. Minsky (1967) discusses this, sort of.) Davis (1958?) compounds Kleene's confusion with his example of (im-) proper subtraction executed on a Turing machine. (I checked his example -- simulated it -- his example is correct, and it does go into an infinite loop -- but he has to detect the error to get it into the loop). But why would someone do this intentionally? Why not just fix the algorithm so it isn't "improper"? Sort of an evolutionary response -- just make the algorithm better. I don't understand. wvbaileyWvbailey 16:32, 18 December 2006 (UTC)

Definition of finite

Is an algorithm a set of instructions with which an instance will terminate over ALL conditions, or that will terminate over ANY conditions?

e.g.

1.) "Go outside"

2.) IF "raining=TRUE" THEN goto to 1 (is this correct?) ELSE "if raining = FALSE" THEN

3.) "go inside & take a nap"

4.) STOP

69.28.40.34 20:59, 26 October 2006 (UTC)

Since October I did some research, and added examples at partial function. And added some more to the algorithm article. This is not a trivial issue. More often than not algorithm will have a restricted "domain" of input over which it "functions correctly"; if the input is outside that 'domain' the algorithm should say "woops" and halt with an error message (e.g. "0", reserved). This makes the algorithm a "total function." If there happens to be an unexpected vile input, then the algorithm is likely to never halt. Or produce the wrong answer! In my mind we never want an algorithm to be a partial function -- rather, they should always be "total". Then the algorithm will terminate with an answer, even an error message, that we can trust. wvbaileyWvbailey 17:49, 18 December 2006 (UTC)

Good question: I took the liberty of rewriting the above to get to its core/jist. Suppose the little man lives on that desert down in Chile? Peru? where it never ever rains (mostly never ever, which I think will be an important point...). If the unconditional goto is back to 1, then we visualize a little man running outside, checking and seeing no rain, going inside, running outside, checking, ad infinitum. Eventually, the little man (before going back out, he can go pee and eat when he needs to, we allow him this) either "produces an object" or not.

We have to agree ahead of time, in the specification of the algorithm, what 'the object' is. Say, the output will be: on a tape, the little man prints a 0 or a 1 and moves the tape right, as follows:

1.) INPUT (outside_is_raining)

2.) IF "outside_is_raining"= FALSE THEN goto 6.) ELSE:

3.) Print 0

4.) Move tape Right

5.) Go to 1.)

6.) Print 1

7.) Move tape Right

8.) "go inside & take a nap"

9.) STOP

So now the algorithm is producing an object (0's and 1's) no matter what the input conditions are. E.g.

000000......000001[stop]

This I would believe, is a valid algorithm. Okay, lets agree that it is a valid algorithm and take away the tape and the printing. We can probably agree that the "printing", in a sense, goes on in the mind of the little man, but only if and only if he can remember every time he tests for rain. Suppose he cannot remember more than the last 6 or 7 times, does this mean the algorithm fails?

Oops. We are into philosophy of mind now. I don't know. Maybe other readers will have opinions. This is why the definition of algorithm is non-trivial. wvbailyWvbailey 16:48, 27 October 2006 (UTC)

I believe finiteness means "it terminates in finite steps on all inputs". This is one of the halting problem variants. mlpkrmlpkr 3:06, 18 December 2006 (UTC)

But I can easily write a viable algorithm that goes on ad infinitum. The Kleene (1952) approach (p. 328) is to have an "undecided" algorithm (a "partial recursive function") produce something while it is undecided. Here's an example with regards to the Collatz conjecture. I designed a simple "Minsky machine" (counter machine) that has a "Collatz" machine inside a "Supervisor" machine; the Supervisor feeds the Collatz machine numbers to test. When the Collatz machine "reduces" the test number to 1, it returns control to supervisor, and the supervisor feeds it the next number to test. To reassure us, the Supervisor could write an output after every success e.g. (i.e. ...(17, 1), (18, 1), (19, 1), (20, 1).... ) and we could watch as this pair does their work. This will go on ad infinitum, or until the Collatz machine doesn't halt because it cannot reduce the number to 1 -- at this point we want the supervisor to write "(0, really_big_number)", and then halt (meaning: "Yeay! We just disproved the Conjecture!"). When the work is hard and taking a long time, to reassure us we want another output, "u" ("undecided") intermittently. This requires a third machine, an "Interrupter" to periodically interrupt the two machines, then return control after writing "u". So the question becomes: will the composite Interruptor+Supervisor+Collatz machine ever halt? It will produce 1's and numbers and u's, e.g. ... (47568, 1), u, u, u, u, u, u, (475679, 1), u, u, u, ... . So far no one knows whether this composite machine will halt or not. wvbaileyWvbailey 17:49, 18 December 2006 (UTC)

I think it is a way that different authors and text define the terms. What I was convinced in my education is, an algorithm terminates on all inputs, but a procedure(or a function) may not terminate. Some procedures are decidable and some procedures are undecidable. Even all decidable procedures are not algorithms. E.g. Operating system never terminates, but its actions based on current input are decidable. They are called computatable procedures. Mlpkr 08:01, 23 December 2006 (UTC)

---

I thought about this more: While the example has a humorous side, there is an interesting epistomological/ontological issue around this: just where/what is "the output" and "for whom" does the output exist?

Suppose "the man" is "a robot" -- when I wrote the following it seemed to turn spooky (less funny) -- and we write a routine for the robot-man, then in fact the algorithm always produces an output, under all conditions. The problem comes in what it means to "display an object" in the sense of "an algorithm' -- for whom does the bell toll? -- does it toll for thee (exterior viewer) or for me (the interior viewer aka the robot's mind)?

Algorithm specification:

computational device: human nervous system + mind

OUTPUT format, INPUT format:

function(arm_L, hand_L, arm_R, hand_R, leg_L, leg_R, balance, eyes)

Available functions:

• OUTPUT( , , ....., , )
• INPUT( , , ...., , , )
• GOAL(name_of_goal)
• CASE( , , , .... , , , )
• GOTO(instruction #)
• HALT(time)

Program:

start:

• GOAL(is_raining?)
• CASE( ....., is_raining?, .....):

is_raining?:

• GOAL(doorway)
• OUTPUT ( , , , , leg_L:walk_forward, leg_R:walk_forward, balance:upright, eyes:forward)
• INPUT ( , , , , , , leg_L, leg_R, balance, eyes)
• CASE ( ...., NOT_is_doorway, is_doorway, .... )

NOT_is_doorway:

• GOTO is_raining?
• GOAL(feel_rain)
• OUTPUT ( , , arm_R:outstretch, hand_R:hand_open, , , balance:upright, eyes:upward)
• INPUT ( , , arm_R, hand_R, leg_L, leg_R, balance, eyes)
• CASE( ...., right_hand_is_dry, right_hand_is_wet, .....):

right_hand_is_dry:

• GOAL(pee)
• OUTPUT ( , , , , leg_L:turn 180, leg_R:turn 190, balance:turn 180, eyes:forward)
• INPUT ( , , , , leg_L, leg_R, balance, eyes)
• etc. etc.
• GOTO start

right_hand_is_wet:

• GOAL(bed)
• INPUT( , , , , leg_L, leg_R, balance, eyes)
• OUTPUT( , , , , leg_L:walk, leg_R:walk, balance:upright, eyes:forward)
• CASE( ...., NOT_is_bed, is_bed, ....)

NOT_is_bed:

• GOTO right_hand_is_wet

is_bed:

• OUTPUT( , , , , leg_L:collapse, leg_R:collapse, balance:supine, eyes:closed)
• STOP( )

For those who want to see more about the problem of "algorithm" from the philosophic point of view see:

John Searle 2002, Consciousness and Language, Cambridge University Press, Cambridge, UK.

Searle is of "Chinese Room" fame. He is asking the question: where is the information? Is the robot just a mindless syntactic/rule-following mechanism and the information is in us the viewers of this little play? Or is there information -- meaning-- to be found in the machine itself? He does ask the question: "With regards to a computation by mechanism, where are "the numbers" really? cf p. 17. I may add this to algorithm characterizations:

"Computation does not name an intrinsic feature of reality but is observer-relative, and this is because computation is defined in terms of symbol manipulation, but the notion of a 'symbol' is not a notion of physics or chemistry. Something is a symbol only if it is used, treated or regarded as a symbol. The Chinese room argument showed that semantics [meaning -- sound and fury signifying something] is not intrinsic to syntax. But what this argument shows is that syntax is not intrinsic to physics. There are no purely physical properties that zeros and ones or symbols in general have that determine that they are symbols. Something is a symbol only relative to some observer, user or agent who assigns a symbolic interpretation to it. ... computation exists only relative to some agent or observer who imposes a computation interpretation on some phenomenon. This is an obvious point. I should ahve seen it ten years ago but I did not." (p. 17)

wvbaileyWvbailey 16:43, 28 October 2006 (UTC)

Googl's edit

Googl changed the beginning text from a "set of instructions" to a "sequence of instructions". A sequence is not necessary, however. A state machine need not have its instructions in a sequence -- for example each instruction for the state table of a Turing machine carries its own pointer(s) to its next instruction(s). Does anyone else object to this change in the wording? "Set" or "collection" is more general and I prefer it. Comments out there? thanks, wvbaileyWvbailey 17:15, 4 February 2007 (UTC)

Well, you are right. The instructions needn't be in a sequence.

I reverted myself, but I'd prefer if there would be a mention about instruction order in an algorithm. Elements of a set are not ordered, and I personally think of an instruction as in "let A be 2+2" (and go to next step by default) not as in "let A be 2+2 and go to step B". I'd change it to something like...

"an algorithm is a procedure (a finite set of well-defined instructions with defined flow)"

Thanks, googl t 20:22, 4 February 2007 (UTC)

Actually what you wrote is what Turing (1936-7) originally defined in his paper: the case "let A be 2+2 and go to step B" as the "motions" of his machines. Simultaneously, Emil Post atomized the operations of "the computer" (a human in his day) into simpler "motions", and a bit later (ambiguous at first) Post's instructions were default-sequential along the lines of the second of your two.

It is unclear to me who defined the first 'state machine' and where exactly it was defined (as a formality, in print). Turing is probably the first, although mechanisms for computation had been around for about 200 years.

If you do simulations you'll find that the most primitive machine (minus its "list of instructions", e.g. fewest logic NAND gates necessary to build it) is the Turing version; whereas the "sequential" form implies the "successor function" of the Peano axioms (e.g. "addition"). However, if you count the extra "memory" required if the "next address(s)" is/are in the list of instructions, the "most primitive" is not so obvious.

Perhaps what you want to see someting more along a formal specification such as this:

"A list of 'instructions', each unique and distinguishable by 'the mechanism' (human or machine), and with a location known by "the mechanism" such that "the mechanism" can locate an identified instruction (as specified in/on its 'state register'/'scratch pad') AND "the mechanism" has the capability of turning said instruction into action per a pre-defined specification."

Simpler said: each instruction consists of two parts (A) and (B): (A) a unique "address" (identifier), and (B) a call to action. "The mechanism" has the capability of (i) locating, (ii) distingushing, (iii) recognizing, (iv) interpreting the instruction into a pre-defined action.

This is why a single definition of "algorithm" is still unsettled. Problem is: where in the literature is such a discussion/opinions as the above? I dunno. Until we can locate it, we can't put it into Wikipedia. wvbaileyWvbailey 19:02, 5 February 2007 (UTC)

Evolution as an algorithmic process

I believe that topic should not be here, but may go to "evolution" topic. mlpkr 16:27, 7 February 2007 (UTC)

Am unclear as to what in the article you are objecting. There are indeed, for use in machine learning, "evolutionary" algorithms that use lots of "parents", randomness and "survival of the fittest" (i.e. the best performing parents at the task are "chosen to breed") as part of the process of the algorithm. "Genetic" algorithms are of this sort (i.e. the "genes" get scrambled by random processes; then new baby machines are built per their now-shuffled genes, and tested against the challenge, etc. etc.). wvbaileyWvbailey 00:14, 8 February 2007 (UTC)

I am objecting to the section http://en.wikipedia.org/wiki/Algorithm#Evolution_as_an_algorithmic_process mlpkr 23:15, 10 February 2007 (UTC)

The section is actually much more about algorithms than about evolution. The bulk of it gives a definition of an algorithm. It relates that Dennett says that evolution fits the definition, but it doesn't describe what evolution is like or how it fits. Perhaps the section should be retitled "Dennett's definition". -R. S. Shaw 03:20, 11 February 2007 (UTC)

This new section is misplaced -- placed as it is early in the article it has too much prominence especially given the fact that it's just one philosopher's opinion. It should go either into algorithm characterizations, or (much) deeper into the article; it is just one of many "characterizations", albeit an interesting one. Any other opinions? If not in a few days I'll move it there and retitle it similar to the above suggestion. wvbaileyWvbailey 21:49, 11 February 2007 (UTC)

I support your opinion on making it part of algorithm characterizations. mlpkr 17:20, 25 February 2007 (UTC)

Done as of 5 March 2007. wvbaileyWvbailey 17:52, 6 March 2007 (UTC)

Dennett´s definition of Substrate Neutrality

an algorithm relies on its logical as opposed to its formal structure. Thus, the particular form in which an algorithm is manifested is not important (Dennett's example is long division: it works equally well on paper, on parchment, on a computer screen, or using neon lights or in skywriting).

Using different media (different materials, surfaces) is possible through "symbolic abstraction". That´s one thing - and it´s not a special feature of algorithms or logic. Speaking about "formal structures" is another topic. There are for example different languages available to express an algorithm. Computer scientists will sometimes even consider using a "natural language" (in opposition to the so called "formal languages"), which have of course their own kind of form, as every linguist can tell you. And at the end of the day, you could even ask an art-historian, what an "informal structure" could be, and we would possibly end up in the old abstract/figurative dichotomy, which reminds us again, how differently the term "abstraction" can be used.

In a nutshell: The terms "formal" and "structure" put in opposition to the term "logical" do more harm than good if you want to understand what "algorithm" means. --Armin B. Wagner 13:04, 19 February 2007 (UTC)

Now that you point this out, I agree with you. The medium of a Turing machine -- the tape built of hopscotch squares, of paper ruled off into squares, of magnetized tape, of CMOS shift-registers, of CMOS RAMs plus an up-down counter -- all of these yield a Turing machine tape if properly applied. However, it is quite easy to show an "improper division" algorithm on said Turing machine (however constructed) that performs incorrectly when confronted by division by 0 ... and how we represent "0" to our Turing machine is a whole matter in itself. There are probably as many properly-constructed "division algorithms" as there are people who can dream them up, and more than likely the "data" as presented to one machine+algorithm will not work when presented to another machine+algorithm (hence the "language problem"). Over the years Dennett has demonstrated an inability to comprehend this stuff -- syntax versus semantics -- and Dennett's nemesis John Searle has taken him to task for it a number of times. As an antidote to Dennett, I'd recommend a recent book: John R. Searle, Consciousness and Language, Cambridge U. Press, 2002. See pages 34-35 where he reiterates his point re syntax versus semantics and his coming to awareness that that which the receiver calls "information" is in the "mind" of the receiver, almost verbatim as Searle states it in his book. wvbaileyWvbailey 19:16, 25 February 2007 (UTC)

Complete But Not Clear

I think this article could use some revamping so that it's size isn't so intimidating. I think if it were made into a more general treatment of algorithms and some of the more technical sections were split into seperate articles it would be easier for a ley-person to understand. A good example of what this article could be is Physics which uses the main page more as a first step and history that as a complete treatment of the subject.Adam McCormick 00:44, 4 March 2007 (UTC)

I hear you. I've already spun off two subsidiary pages -- Algorithm characterizations and Algorithm examples. I hesitate to spin off the history section because many times that is what a newbie reader wants -- some historical perspective. I dunno. Let's see if anyone else has input. wvbaileyWvbailey 21:18, 5 March 2007 (UTC)

I don't think the article is too long, but I think it would benefit from reorganization and copyediting. There is not a lot of "structure" writing, which makes the parts of the article seem disconnected. Moving the "example" and "history" sections higher to just after the informal characterization might help. I also feel that the number of inset direct quotes should be reduced. CMummert · talk 22:02, 6 March 2007 (UTC)

I agree that it is not too long. Plus it's missing important content re "copyright and patents" -- we would need something (at least some references) re US and EU patent law here; I know something about patenting objects and processes but nothing about patenting algorithms. Originally the "history" was higher up, but when I added to it, it seemed to obscure the article's major content, so I moved it down; I had left the matter open as to whether or not it should be split off eventually. I don't particularly like the article's "example".

The problem is: the field is so broad ... while at the college bookstore a few days ago I found two huge computer-science tomes (meant to be used as texts for classes) re algorithms for computation; we only have to think of the 3-volume (soon to be rewritten plus a 4th if he gets his act together) Knuth series. If it were left up to me I'd split off the types of algorithms (searching and sorting and greedy and that sort of specific stuff) with the intent of letting this new sub-article contain pointers to yet more sub-articles with details about specific algorithms. wvbaileyWvbailey 17:33, 8 March 2007 (UTC)

improving intro

Upon reading the intro, the second sentence caught me as way too esoteric and tangential for an intro: "The computational complexity and efficient implementation of the algorithm are important in computing, and this depends on suitable data structures." Moreover, this is pretty much a "topic sentence", but it is actually the last sentence of a paragraph that says nothing about complexity, implementation, or data. I strongly thing it should be removed. It's simply a stumbling block for the reader that adds nothing.

I can say the sentence is there trying to give important context and concepts to relate algorithms with computing. For the specifics you'll naturally have to follow the links, but I don't understand what's esoteric or tangential here. Not that I'd want to stop you from improving the article, just to give another view. --TuukkaH 12:48, 8 April 2007 (UTC)

Also, the second paragraph, using an analogy is not encyclopedic form. And it is redundant with the first paragraph, which is more precise.

I propose the following change to the intro:

In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. The computational complexity and efficient implementation of the algorithm are important in computing, and this depends on suitable data structures.

Informally, the concept of an algorithm is often illustrated by the example of a recipe, although many algorithms are much more complex. Basically, an algorithm is a method, like a recipe, in that by following the steps of an algorithm you are guaranteed to find the solution or the answer, if there is one. Algorithms often have steps that repeat (iterate) or require decisions (such as logic or comparison). Algorithms can be composed to create more complex algorithms.

The concept of an algorithm originated as a means of recording procedures for solving mathematical problems such as finding the common divisor of two numbers or multiplying two numbers. The concept was formalized in 1936 through Alan Turing's Turing machines and Alonzo Church's lambda calculus, which in turn formed the foundation of computer science.

Most algorithms can be directly implemented by computer programs; any other algorithms can at least, and all algorithms can, in theory, be simulated by computer programs. In many programming languages, algorithms are implemented as functions or procedures.

Actually, i think the last paragraph should be excised all together. The last sentence of the para before it contextualizes algorithms just fine, and leads into the body of the article where detail like "In many programming languages, algorithms are implemented as functions or procedures." is addressed. Kevin Baas^talk 20:31, 7 April 2007 (UTC)

That seems reasonable to me. Why not go ahead and make the changes? CMummert · talk 12:53, 8 April 2007 (UTC)

I suggest that you strike "a procedure" in the first sentence i.e.

" ...an algorithm is a procedure (a finite set of well-defined instructions)for accomplishing some task ...

I also agree that the last paragraph should be struck; I'm not convinced that it is (deep-philosophically) correct: in particular

"...and all algorithms can, in theory, be simulated by computer programs..."

The above is a hypothesis, a conjecture, not a truth, unless "algorithm" is so defined, and that is still an open topic. wvbaileyWvbailey 16:10, 9 April 2007 (UTC)

Citations and style

Hi. I did notice that this article is indeed well-cited, but it doesn't seem to be in one of the three styles found on Wikipedia:Citing sources. I think we should switch the style of the inline citations to Harvard. It would take the minimum of effort to switch them to that style, compared to the others. Meowist 07:28, 27 June 2007 (UTC)

I agree. I added the bulk of the citations -- but without any particular style in mind. (I just wanted to get the information down in print. . . Whatever "style" you see is probably 40 years old). As you said all the information's there, it's just a matter of formatting it. If you or someone else doesn't get to it first I'll do it, I just can't say when. Also, as I recall, the references are mixed in style, some done with templates and some without. I find the templates frustrating (i.e. they take more time than they appear to be worth) and not knowing/understanding what utility they have I have been inclined to ignore them. wvbaileyWvbailey 01:48, 28 June 2007 (UTC)

Lack of pictures hinders FA status odds

Does anybody have any ideas for what pictures to add to this article other than flowcharts? Pictures that help the article, while not being of specific algorithms discussed in depth in other pages? I was thinking of adding another example algorithm, this time of a simple non-deterministic algorithm and then adding a graph of steps used versus problem size to illustrate the concepts in asymptotics of algorithms, in this case probably asymptotically optimal. Or perhaps an animated GIF to illustrate the current example algorithm? Or both ideas? What do people think? It's certain, in my mind, that this article needs more pictures to stand a chance at getting FA. Meowist 23:49, 27 June 2007 (UTC)

Your example (non-deterministic algorithm) sounds too complicated and too “abstract”. The picture at the top of the article is too simple. (I am no fan of the "pseudo-code" example in the article). And one thing we have is to avoid is "original research" . . . And it would be good if the example were instructive of some other interesting notion(s) presented in other wikipedia articles . . . And it would be good to use symbols and terminology derived from some prevalent, accessible text (e.g. Boolos-Burgess-Jeffrey).

I see that the problem of choosing an example comes (in part) from subtle constraints implied in the notion of “algorithm”. As the article discusses, an “algorithm” is more than a fool-proof recipe for some process; rather, it also includes/implies (or should include, to be complete) a specification for the machine or person who executes it; in particular that machine/person must have the capabilities of performing the steps, and there are a host of input and output restrictions that have to be met if the “algorithm” is to be a success.

That the reader be aware of the “seriousness” of these issues is a key point of this article. But because of our wide assortment of readers, of varying experience levels, these fussy constraints narrow our possible choices of examples. For instance, if the example comes from mathematics, it should use really simple arithmetic -- no more than +, -, x and maybe division—and really simple concepts. If the example involves a machine the recipe should be in some absolutely simple language that the humans understand, and the machine specified.

If a person were to “animate” an example, one with a conditional go-to would be far more interesting and educative. The “conditional go-to” also touches on issues in recursion theory and philosophy of mathematics (i.e. see Church-Turing thesis and effective calculability (in particular see the history in Turing machine )). Such things as partial function come to light, as well.

Here's one human-algorithm example that is fascinating because it’s so damned easy to describe and yet it's an unsolved problem: Ulam's problem (Collatz Conjecture). You are given a number N (but not zero, otherwise you need to test for zero at the outset). Is it “1”? If so you’re done, otherwise: Is it EVEN or ODD? If it's odd you triple it and add 1 (3*N+1), otherwise you divide it by 2 (N/2). Recycle the new number and repeat until the number is 1 and then HALT. Question of interest: For any starting number N, will the number always converge to 1? Prove it! Now, suppose you change the algorithm to “IF N is ODD THEN 5*N+3 ELSE divide by 2”? Then what happens?

We can simplify the algorithm (in a sense) when we realize that (3*N+1) is always EVEN, so (3*N+1) will end up being divided on the next repeat. So we can just skip this predictable step and say: “IF N is ODD then (3*N+1)/2 else N/2”.

If we convert this to a machine-algorithm, we can get away with a counter machine (using DECREMENT register, INCREMENT register, and JUMP IF register is ZERO, and maybe ADD and COPY to make things easier). A very efficient Ulam-machine aka “algorithm” is as follows: First test to see if the number N is 1; if so then done. If not, halve N by successive decrements of N until 0 while at the same time incrementing “H” every other decrement (e.g. If N = 11, N/2 = 5 + ODD determination). Keep this half (H = N/2 = 5). If the process of halving resulted in the ODD determination (it did), triple the half H by 3 repeated additions of H to N plus two increments (i.e. N = 3*H+2 = 3*5+2 = 17). Otherwise you just keep the half H and copy it to N. Recycle this new number N (i.e. recycle 17) and Repeat until the number is 1.

Here’s another machine-based suggestion: we start with a counter machine designed around the Peano axioms (as opposed to the INCREMENT-DECREMENT version). “X” is any “register” in the machine, “xxx” is some instruction number:

(1) CLEAR contents of register X and go to next instruction: CLEAR X

(2) INCREMENT (add one to) contents of register X: INCREMENT X and go to next instruction

(3) IF contents of register X = contents of register Y THEN JUMP TO INSTRUCTION xxx ELSE go to next instruction: IF X = Y THEN xxx

(4) HALT

Suppose we want to write a routine that DECREMENTS (decreases by 1) the value in register A. How do we do this? It turns out we need two more registers, call them C for “copy” and D for “difference”. The example actually shows how to create both a "DECREMENT" subroutine as well as a "COPY" subroutine:

’’start’’:

CLEAR C  ; 0 --> C

CLEAR D  ; 0 --> D

IF N=C THEN ’’copy’’  ; C=0, so we’re testing for N=0

INCREMENT C ;here is where we get the “extra 1”

’’loop_1’’:

IF N=C THEN ’’copy’’ ;is the copy equal to our number N

INCREMENT C  ; [C]+1 --> C

INCREMENT D  ; [D]+1 --> C

IF N=N THEN ’’loop_1’’  ; a trick to create an unconditional jump

’’copy’’: ;D now has the difference in it, but we have to move it to N

CLEAR N  ; 0 --> N

‘’loop_2’’:

IF N=D THEN ’’done’’

INCREMENT N  ; [N]+1 --> N

IF N=N THEN ‘’loop_2’’

’’done’’:

HALT

If we stick with a counter machine with instructions (INCREMENT, DECREMENT, CLEAR and COPY) the multiply routine and division routine are of comparable difficulty. Here is "Division by repeated decrement": At the start, N = starting number to be divided; at the end, N = 0, Q = quotient, R = remainder (residue), D = divisor. This does not check to see if divisor D is 0.

N = D*Q + R

start:

CLEAR Q

outer_loop:

CLEAR R

COPY D to DVSR ;DVSR = loop counter

inner_loop:

JUMP IF N IS ZERO TO N_is_empty

DECREMENT N

INCREMENT R

DECREMENT DVSR ;DVSR = loop counter

JUMP IF DVSR IS NOT ZERO TO inner_loop

INCREMENT Q

JUMP TO outer_loop

N_is_empty: etc . . .

I dunno, just some thoughts. wvbaileyWvbailey 17:43, 28 June 2007 (UTC)

The following are even more primitive. They are shorter but at the expense of having to specify "the next move". The steps are numbered, and we assume that the person/machine can recognize thier identifying "numbers" (aka symbols) etc. The first one is the "DECREMENT" version above.

’’start’’:

1 CLEAR C, go to step 2,  ; 0 --> C

2 CLEAR D, go to step 3,  ; 0 --> D

3 IF N=C THEN go to step 5 ’’move’’ ELSE go to step 4  ; C=0, so we’re testing for N=0

4 INCREMENT C, go to step 5 ;here is where we get the “extra 1”

’’loop_1’’:

5 IF N=C THEN go to step 8 ’’move’’ ELSE go to step 6 ;is the copy equal to our number N

6 INCREMENT C, go to step 7  ; [C]+1 --> C

7 INCREMENT D, go to step 8  ; [D]+1 --> C

’’move’’: ;D now has the difference in it, but we have to move it to N

8 CLEAR N, go to step 9  ; 0 --> N

‘’loop_2’’:

9 IF N=D THEN go to step 11 ’’done’’ ELSE step 10

10 INCREMENT N, go to step 9  ; [N]+1 --> N

’’done’’:

11 HALT

Addition program: A+B --> S. The computational model is the same Peano counter machine (or a person with some paper divided into 4 "locations" (squares) labelled A, B, S, T.) Begin with two "numbers" in locations A and B. (Tally marks are much more peculiar and interesting/revealing with respect to the equality test; their use points out that "numbers" (symbols like 1, 2, 3 . . .) have implied meanings for humans, for instance "symbol 4 is the successor of symbol 3", etc.)) The "summation" will appear in the square called "S". For a person "CLEAR" will mean "ERASE"; "INCREMENT" will mean "put another tally mark (or "number-symbol") in the specified square, overwriting not allowed".

[A]+[B] --> S

1 CLEAR S, go to step 2,

2 CLEAR T, go to step 3,

3 IF A=S THEN go to step 5 ELSE go to step 4,

4 INCREMENT S, go to step 3,

5 CLEAR T, go to step 6,

6 IF T=B THEN go to step 9 else go to step 7,

7 INCREMENT S, go to step 8,

8 INCREMENT T, go to step 6,

9 HALT

In this one I eliminated the "clues" as to what the thing is doing: it is now so primitive it seems (to me anyway) absolutely mind-numbing. Which is the point: To add any two integers written in locations "A" and "B", just pretend to be a robot, follow the rules and the sum will appear at "S" as specified. wvbaileyWvbailey 22:21, 28 June 2007 (UTC)