# Talk:Algorithm/Archive 5

This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |

Archive 1 | ← | Archive 3 | Archive 4 | Archive 5 |

## About the etymology section

usually this section precedes all others. Why then is it postponed till section 9 where it makes no sense at all? Is it maybe because we have a hard time accepting that such a crucial concept, without which we wouldn't have had computers, actually goes back to and bears the name of a brilliant Muslim, who we would prefer to see as a terrorist? Shame on you! — Preceding unsigned comment added by 87.212.38.229 (talk) 16:58, 29 December 2011 (UTC)

- I tried to do something about this but apparently user Wvbailey is convinced that the authors he mentions (is it Sonya Kleene, Stephen Kleene, who?, no idea who is meant by "Rogers") are somehow definitive. I don't get into edit warring, disputes with such users so others will have to pick up from here. Maybe the tagging is the best that can be done under these circumstances. Lycurgus (talk) 02:17, 17 January 2012 (UTC)

- Also, I would take the approach of defending Arabic or Iraqi culture in this case rather than Islam/Muslims, they're not the same. 72.228.177.92 (talk) 02:43, 17 January 2012 (UTC)

---

- The etymology has been an ongoing issue here. Clearly anonymous has a (Muslim, Arab or Persian) ax to grind and is attempting to inject their religious faith or jingoistic intent into a difficult article that needs (quite clearly as demonstrated in anonymous's rant above) extremely tight sourcing. This problem of edit warring over their favorite son Al Kwarizmi has been ongoing between Iranians and Moslems, Shiites and Sunnis: the Iranian Shiites want to claim Al Kwarizmi as an Iranian (he was a Persian), the Arabs who swept through his region of Persia and converted his family by the sword from Zoroastrianism to Islam want to claim him as a Moslem and/or Arab. What his faith was, and his nationality, is absolutely irrelevant to the definition of "algorithm". The edit that you redacted and I reverted is flat out wrong. If anonymous can produce sourcing, then we can entertain a dialog. Or better yet, anonymous can add the definition and sourcing to Algorithm characterizations. But first I suggest that anonymous actually read the article, the footnotes and consult the relevant attached sources. And by the way it's Stephen Kleene 1952, Hartley Rogers 1967, and add Donald Knuth various dates); see the sourcing references. wvbaileyWvbailey (talk) 02:48, 17 January 2012 (UTC)

- tldr; I should think Knuth or somebody would be a name to drop if that was the approach being taken. 72.228.177.92 (talk) 03:26, 17 January 2012 (UTC)

- I'd also like a bit of clarity on the issue. While the article implies that the
*word*algorithm is taken from Al Kwarizmi's name, the*concept*of an algorithm had been around for several centuries already. If that is true, then that perhaps needs to be made more explicit. Kmasters0 (talk) 08:37, 22 February 2012 (UTC)

- I'd also like a bit of clarity on the issue. While the article implies that the

- Can you source this or be more explicit (who, what, when, where, how) about someone actually
*intentionally*creating a*generalization*of the notion "step-by-step procedure for how to perform calculations" (i.e. concept)? If there's something that can be sourced and is relevant we should add it. It would be an interesting addition. (The history indicates it was a long process that culminated only in the 1930's, altho there were major strides (not mentioned in the article, I believe) in the mid-late 1880's around a formalization of the notion of recursion, in fact the more I think about it, the more "key" this seems; I bumped into this accidentally not so long ago but I can't remember who was responsible for formalizing the notion.). Bill Wvbailey (talk) 15:05, 22 February 2012 (UTC)

- Can you source this or be more explicit (who, what, when, where, how) about someone actually

- RE recursion: Bill's note to Bill: See Dedekind 1887. But what was I reading that sent me there? Cf Dedekind's definition 71 of the natural numbers, then his theorem 80
*complete induction*, of mathematical induction §124-125. Also Berlinski (unfortunately he does not give a history of recursion): "Recursion is an example of a*mechanical*process. The steps are broken down so simply that no though is involved in carrying them out. . .."/"And the importance of this?"/"It gives prceise meaning to the intuitive idea of*effective calculability*."/"Meaning?"/The dialog goes in a bit of a circle]/"It was clear to me," the cardinal finally said, "that recursion would be a subject to my taste" (pages 134-135)

- RE recursion: Bill's note to Bill: See Dedekind 1887. But what was I reading that sent me there? Cf Dedekind's definition 71 of the natural numbers, then his theorem 80

- No, I can't source it, which is why there is confusion. My argument is that the article
*implies*this. It does this by introducing Euclid’s algorithm as a matter of fact. Because it doesn't say that the process did*not*exist, this would imply that the concept of an algorithm had existed at (or even before) Euclid's time. Then the article goes on, much later, to explain that the word for the process comes from Kwarizmi's name. If that is not true, then I think it should be made more explicit. (BTW, while I don't support anonymous's rant, I also found it strange that the etymology of the word was placed so late in the article. Perhaps this can be moved, but by one who is more familiar with the wikipedia's editing principles than I.) Kmasters0 (talk) 10:01, 24 February 2012 (UTC)

- No, I can't source it, which is why there is confusion. My argument is that the article

---

- RE Euclidean "algorithm": Good point about the usage "Euclidean algorithm". I understand your concern. I think the approach to take (see the quotes below) will be to change the wording under the drawing, and perhaps in the body too. Euclid (at least in Heath 1908 translation) begins with a Proposition" which he then
*proves*. Heath in his commentary calls it a "method" and "process" (cf footnote page 67) and refers to Nichomachus' rule:

- "Here we have the exact method of finding the gratest common measure given in the text-books of algebra . . .. The process of finding the greatest common measure is simply shown thus: [demo goes here, is confusing]. ¶ Nichomachus gives us the same rule (though withut proving it) . . ." (pages 66-67 from Euclid's Elements Book VII appearing Hawking 2005).

- Knuth starts with a little history re al Kwarizmi, and then jumps right in with the Euclidean "algorithm" as his first example. Knuth notes that the word did not appear in
*Webster's New World Dictionary*until 1957. He also cites the Oxford English Dictionary about the etymology being confused with*arithmetic*. He calls it a*process*once and thereafter "algorithm":- "By 1950, thw word algorithm was most frequenty associated with "Euclid's algorithm", a process for finding [etc]" (Vol 1 Knuth 1972:2)

- Berlinski starts this way (first para in the Preface of the book):
- "More than sixty years ago, mathematical logicians, by defining precisely the concept of an algorithm, gave content to the ancient human idea of an effective calculation." (Berlinski 2000:xi)
- "The idea of algorithm had been resident in the consciousness of the world's mathematicians at least since the seventeenth century; and now, in the third decade of the twentieth century, an idea lacking precise explication was endowed with four different definitions . . . the four quite different definitions, it is worthwhile to recall, were provided by Goedel, Church, Turing, and Post." (Berlinski 2000:20)

- Definition from my Merriam-Websters Ninth New Collegiate Dictionary (1990) gives a first occurrence in ca 1894:"a procedure for solving a mathematical problem (as of finding the greatest common divisor) in a finite number of steps that frequently involves repetition of an operation;
*broadly*a step-by-step procedure for solving a problem or accomplishing some end."

- RE The etymology section: it has moved around any number of times. As I note above, it has been a "bone of contention" for a long time, almost to the point of having to place the article under a "review" process. A prominent position near the top seems to inflame the passions of those who then read no further and then engage in an edit war. Since appearing now far down in the article I've noticed the flaring of passions has been greatly reduced. Actually, even the mention of his name in the lead paragraph has been a cause of inflammation. Bill Wvbailey (talk) 16:35, 24 February 2012 (UTC)

## Search and enumeration

It's simply very badly written: First, it's unclear if 1) and 2) are meant to be examples or types. Second, it looks like other (heuristic) algorithms are mentioned in this section. 68.183.23.147 (talk) 04:47, 17 January 2013 (UTC)

## Go to 2 0r 3

I am a layman who doesn,t know much about algorithm. But I think something is wrong in the flow chart of Euclid's algorithm. see the figure. after A is assigned the value A-B why go to 2? Isnt it 3 to where the arrow should lead? see that will once again check whether B>0 ,which is not needed as we reach the step assigning A the new value after checking it? Sorry if my question is an idiotic one. --binu (talk) 07:36, 10 August 2013 (UTC)

- This version of the algorithm -- the "elegant" version (there's more about it in the article) -- is also a bit subtle. There's also a less-subtle version (Knuth's version)further down in the article, too. Knuth observed that the best way to understand an algorithm is to try it out. You can do it either by hand or by use of an Excel spreadsheet, or if you can program e.g. in Basic; see further in the article where the Basic program is listed. Bill Wvbailey (talk) 16:05, 10 August 2013 (UTC)

## Finite number of steps?

I never understood why algorithms are supposed to be limited to a *finite* number of steps. An algorithm to calculate the square root of a number requires an infinite number of steps. But "infinite" in mathematics does not mean a prohibitively large number, but only that the result can be achieved with arbitrary (although never complete) precision. Rbakels (talk) 09:18, 6 December 2011 (UTC)

- Well the algorithm on computer would be to "calculate the square root to within 1 ULP" rather than just calculate the square root. --Salix (talk): 10:40, 6 December 2011 (UTC)
- Alternatively, wouldn't it be correct to say that (e.g.) the Newton-Raphson algorithm can calculate the
*exact*square root of any number in an*infinite*number of steps, as a mathematical way of saying that the exact value can be approached (not: reached) in any level of precision if only the number of iterations is increased? (Of course, I am aware that this presumes calculations with infinite precision). Rbakels (talk) 13:05, 9 December 2013 (UTC)

- Alternatively, wouldn't it be correct to say that (e.g.) the Newton-Raphson algorithm can calculate the

## The section 'Why algorithms are necessary' doesn't seem to explain "why algorithms are necessary"

When I red the title I expected to find an explanation to why we have to use algorithms instead of just using singular expression. I understand that it would be hard to do that, but I don't really understand 'why' in a mathematical sense. Can all algorithms be translated to expressions? If not, why? Has this question been answered? Has it been asked? By whom? Etc... Have I missed a part of the article here?

- An algorithm reduces a problem to a number of simpler steps. A single step algorithm is the ultimate algorithm. Algorithms refer to
*operations*. The expression x = a + b + c boils down to two operations in a machine that can add no more than two numbers: "add a and b and save the intermediate result", and "add c to the intermediate result". "Simpler steps" is context-dependent. A very basic computer that only can add and subtract requires more elaborate algorithms if effectively multiplication an division operations are needed. Advanced subroutine libraries can cope with problems forumulated in matrix operations. Rbakels (talk) 13:15, 9 December 2013 (UTC)

## Legal aspects

Is it possible to get a patent or software patent for an algorithm? For examples the algorithm pairs the describe lossy (or lossless) compression and decompression of video or audio data. They are said to be maybe subject of patents. Even though patent holders usually take royalties only for encoding... This is why FFmpeg or Libav are not found in many software repositories. User:ScotXW^{t@lk} 23:16, 30 June 2014 (UTC)

- I am not an expert on algorithms but there definitely are many patented algorithms. Examples include data compression algorithms. Many are listed here. Wqwt (talk) 04:59, 9 August 2014 (UTC)

## External links modified

Hello fellow Wikipedians,

I have just added archive links to 2 external links on Algorithm. Please take a moment to review my edit. If necessary, add `{{cbignore}}`

after the link to keep me from modifying it. Alternatively, you can add `{{nobots|deny=InternetArchiveBot}}`

to keep me off the page altogether. I made the following changes:

- Added archive https://web.archive.org/20090412193516/http://www.kennislink.nl:80/web/show?id=116543 to http://www.kennislink.nl/web/show?id=116543
- Added archive https://web.archive.org/20090412193516/http://www.kennislink.nl:80/web/show?id=116543 to http://www.kennislink.nl/web/show?id=116543

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 17:53, 13 July 2015 (UTC)

## Etymology and True Word Origins

It is obvious the editor of this article has control issues.

It is a fact that al-Khwārizmī studied Greek source material extensively to make his unique contribution to the world of mathematics.

It is a fact that most of the word *algorithm* just as word the *logarithm* come from a Greek language origin.

To state that two syllables of a word come from a certain language (in this case Greek and NOT Arabic) and then refuse to give credit, shows true ignorance, ethnic bias and revisionism.

It is in fact important to begin to understand any concept by beginning with where the notion comes from and what it means, this is fundamental.

Since "al" is a reference to the name Khwārizmī and not part of the name or *nomen* itself, then there is no evidence that this is related to the etymology of the word *algorithm* and not irrelevant to the issue. The word 'the' or 'of' have no contextual or descriptive relationship to the entire word, al-gorithm.

It is widely accept that *logarithm* is short for the Greek *logos-arthimos* or literally translated "why-arithmetic" and most evidence supports the idea that *algorithm* is a further development of the same arithmetic concept *allo-logos-arthimos* or translated from the Greek: "another-why-arithmetic".

- "Most evidence"? Where? Yours appears to be a false etymology, even though it's a reasonable mistake to make. See this for example:

ALGORITHM. n. 1690s, from French algorithme, refashioned (under mistaken connection with Greek arithmos "number") from Old French algorisme "the Arabic numeral system" (13c.), from Medieval Latin algorismus, a mangled transliteration of Arabic al-Khwarizmi "native of Khwarazm," surname of the mathematician whose works introduced sophisticated mathematics to the West (see algebra ). The earlier form in Middle English was algorism (early 13c.), from Old French.

- Source: Online Etymology Dictionary. 200.127.158.54 (talk) 21:26, 1 October 2015 (UTC)

al-Khwārizmī developed the algorithm from reference to Greek math texts, not in a vacuum, but by study of preexisting knowledge and he innovated from that point. This has nothing to do with opinions it is "the story", historical fact. — Preceding unsigned comment added by 69.183.30.237 (talk) 06:41, 8 May 2012 (UTC)

- You are certainly full of opinions (or as Bertrand Russell would call them -- "beliefs"), but you have not backed them up with even a single source. Wikipedia requires sources, not beliefs. If you have credible sources, in particular research on the etymology of this particular word
*algorithm*, we would like to see them. Bill Wvbailey (talk) 14:40, 8 May 2012 (UTC)

There are sources in the article itself, an article which has contradictions. Some related articles that conflict are also found. The use of language fragments or combined words means that it is already proven. Arabic and Greek merging of words is common throughout history, there is a shared influence from Egypt and the Phoenician root. The close trading relationship between these cultures translated into intellectual exchange as well. The alphabet was created from a Phoenician arithmetic notation of items of trade, ie. Ox-head or alpha etc. The Greeks combined these symbols with there own glyph-ic scripts and writing was also adopted in more widely in the mid east. Arabic followed a similar genesis preceding written script.

The article itself is not consistent and was revised to remove pertinent information. I don't agree that any "belief" system enters into the debate. History at one point in time became an instrument to convey knowledge as imperfect as that can be. Politicizing something that can be clearly pointed out does not accomplish anything. It is not belief that leads me to think this, it is disdain for a new culture that has disregard for the past. — Preceding unsigned comment added by 69.182.147.217 (talk) 04:36, 11 May 2012 (UTC)

## first paragraph covering Euclid's

I improved the section covering Euclid's algorithm by mentioning that it's to determine the greatest common divisor. See the edit. A good understanding of English and language in general will tell you that even though the usual use of adjectives is that you put it before the noun that it demonstrates, when the demonstrative (is *predicate* a better word?) is more a phrase than a single word--in this case, "common to two numbers"--it makes it easier to parse to put the adjectival phrase after the noun. user:98.229.184.161 disagrees, and made this edit with the claim that my usage was invalid. See his edit. On the other hand, now the wording is "greatest common divisor (GCD) to two numbers" which, to me, seems very clunky. I would edit it back to return it to my wording, but I don't feel like starting an edit war over something so simple. I'll leave it to the rest of the community to decide. D. F. Schmidt (talk) 21:48, 14 December 2015 (UTC)

## Word origin and Etymology

There are two sections ("word origin" and "etymology") in article about one and the same topic. I think these sections need to merge. --Treisijs (talk) 14:37, 21 December 2015 (UTC)

## "Most algorithms are intended to be implemented as computer programs."

"Most algorithms are intended to be implemented as computer programs. However, algorithms are also implemented by other means, such as in a biological neural network (for example, the human brain implementing arithmetic or an insect looking for food), in an electrical circuit, or in a mechanical device."

Where is the evidence for this? This sounds like a view of a computationalist. Yoga Conflagration (talk) 19:36, 5 June 2016 (UTC)

- Can you suggest a rewrite? E.g. "The most common algorithms are hand-calculations for [arguably, source?] common arithmetic computations: addition, subtraction, multiplication and division, square-root and exponentiation. Algorithms are implemented as computer programs [source? See the Bohm-Jacopini theorem ] and by other means, such as computer programs, biological neural networks (for example, the human brain implementing arithmetic or an insect looking for food), and [combinatorial and sequential] electrical circuits
~~, or a mechanical device~~." Bill Wvbailey (talk) 23:45, 5 June 2016 (UTC)

## External links modified

Hello fellow Wikipedians,

I have just modified one external link on Algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

- Added archive https://web.archive.org/web/20130704180806/http://siam.omnibooksonline.com/2012SODA/data/papers/500.pdf to http://siam.omnibooksonline.com/2012SODA/data/papers/500.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by **InternetArchiveBot**. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template `{{source check}}`

(last update: 18 January 2022).

- If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
- If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—**InternetArchiveBot** (Report bug) 23:46, 12 June 2017 (UTC)

## Captions under illustrations

The captions are there because the examples are used throughout the text. Read the article. See where the captions are used later. Nobody is making you read them. Just because you don't want to read them doesn't mean someone else will not find them useful; for example, the caption under the first figure illustrates how to read a (classic) "algorithm" (remember, that is what this article is about). Maybe other editors have a take on this. I will continue to revert until a discussion ensues. Wvbailey (talk) 20:42, 19 October 2017 (UTC)

- WP:CAP makes it clear how captions should be used. If someone wants to see a more complete discussion of a specific image they can go to the image file to see a more complete description. Long captions, on material not relevant to the current article are distracting and a waste of space. There is no need to repeat information in the text of the article in a caption. GiovanniSidwell (talk) 14:28, 20 October 2017 (UTC)

No one cares about "space" in this context. The body of the text refers to the illustrations, so the explanations under them are useful as reference, without the cumbersome and utterly-distracting step (to say the least) of having to go to the image file to read a caption. I've never read an article that required such a step. (This would be like encountering an article in the print Scientific American with uncaptioned illustrations that require you to go to their website in order to read the captions; think about this in context of someone printing off a hard cc of the article, which is quite likely). Your last point may be valid, if in fact the info is also in the text. Let's wait awhile to see if any other editors have a take on this. Wvbailey (talk) 19:04, 20 October 2017 (UTC)

## Facebook and Google and Coatracks

Does anyone else think the sections near the end dedicated to criticism of Google and Facebook algorithms are a huge WP:COATRACK? They strike me as out of place with the style and structure of the rest of the article and overemphasize some of the least understood examples of a very broad subject. I'll probably remove most of that unless someone presents a good reason why I shouldn't. The *Legal concerns* subsection could be retained by merging it into the primary *Legal issues* section. Furrykiller (talk) 20:46, 23 August 2017 (UTC)

- I completely agree that this article shouldn't be discussing those issues. However, lately people have been saying things like "it's the algorithm" to mean "some automated process is responsible, not human judgement". There is a lot to say about that issue, and we need to find some place to discuss it, cross-referencing from here. --Macrakis (talk) 19:56, 20 October 2017 (UTC)

## On the introduction

I think that in this article basics should be included for beginners.Link:logarithms,Euclidean vectors

I removed this sentence from the intro because it does not well summarize expert belief: "Giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem. [ref: Moschovakis, Yiannis]" First, the consensus by experts is that Turing machines capture classical algorithms. Like the foundations of all fields, this is disputed by some and is continually being questioned, but this is a definite minority position. Second, the paper by Moschovakis appears to be a bad cite to support this idea. That paper discusses whether Turing machines capture computational *efficiency* correctly at the level of specific polynomials. But this is very different than suggesting that they don't capture *computability*. Jess_Riedel (talk) 12:12, 24 March 2018 (UTC)

- That is all correct, but I don't think it is what the quote was getting at. I don't think anybody argues that the definition of an algorithm is a Turing machine. Somehow, algorithms are courser than Turing machines - two different Turing machines can implement the same algorithm. Indeed this is visible even in the abstract of the reference that was given before [1], and if you open the cached article the first page says the same thing. — Carl (CBM · talk) 12:53, 24 March 2018 (UTC)

- Similarly, Knuth (1977) writes "A program is the statement of an algorithm in some well defined language. Thus a computer program represents an algorithm, although the algorithm itself is a mental concept that exists independently of any representation." The challenge that this article was referring to is how to define that mental concept - an algorithm - in a way that does not identify it with a particular program. — Carl (CBM · talk) 13:01, 24 March 2018 (UTC)

## Legal Issues

The first paragraph of this section smells strongly of WP:OR, and is entirely unsourced.

The section on Legal Issues currently relies on two sources: the first is an article in a law journal by a researcher (Andrew Tutt) who is not sufficiently notable to have his own wikipedia article. The first two pages of a google search for "Andrew Tutt" generates a lot of stuff about a cancer specialist in London; a few pages about US lawyers, none of whom appear to be researchers; and a dead cricket player. Tutt's opinion that a we need a new US regulatory agency for algorithms is arrant nonsense, and should be deleted as WP:BOLLOCKS. (As it happens, some algorithms are not even within US regulatory jurisdiction, believe it or not!)

The second source is a document published by the Web Foundation, that goes out of its way to point out that it relies on a definition of 'algorithm' very different from the one we are using (it then declines to give any proper definition of the word, just noting: 'To avoid confusion, this paper employs a systems definition of 'algorithm', describing code and data as well as "the greater socio-technical assemblage that includes algorithm, model, target goal, data, training data, application, hardware - and connect it all to a broader social endeavour"').

What?? To "avoid confusion"? That isn't even grammatical (and much of the rest of the paper contains basic grammar mistakes, which to my mind bespeak an inability to string two thoughts together coherently).

The material based on Tutt is evidently relying on a definition of 'algorithm' similar to the one the Web Foundation appears to be using, a definition that doesn't seem to include the words 'unambiguous specification'.

I think the entire section should be removed from the article; this article is about algorithms as well-defined procedures, not as "socio-technical assemblages" that can be overseen, held accountable etc. I propose to perform this deletion within a few hours. I think this section detracts from what is otherwise a pretty good article (but see my separate comment on History).

There might be an argument for including a brief paragraph noting the recent tendency to use the word to refer to any automated process, however complex or opaque. I do not want to write that paragraph. MrDemeanour (talk) 10:44, 17 September 2018 (UTC)

- I deleted the Tutt and Web Foundation stuff. I left stuff about patents and export bans; that stuff needs citing, and needs to be made more specific about (e.g.) which jurisdictions impose crypto export bans (some people reading this may not be in a jurisdiction that enforces US patent law or that defines crypto as weaponry). MrDemeanour (talk) 16:56, 17 September 2018 (UTC)

## History: Development of the notion of "algorithm"

Given the definition we are relying on in the lede, algorithms have been in use for as long as humans have been engaged in reasoning. This section implies that algorithms began with the ancient Greeks.

The section then starts burrowing into the history of automation and computing, perpetuating the incorrect belief that an algorithm is any procedure followed by a machine. This is followed by a discussion of 19th C developments in symbolic logic, which seems to me off-topic.

The 'History' section is quite a long section; I think it goes way too far back in time. We say in the lede: "A partial formalization of what would become the modern notion of algorithm began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928." I agree. But if that's where the notion began, then a section on the history of "the notion of 'algorithm'" should not start with the ancient Greeks. Change the section title, maybe?

I don't really want to try to fix these problems I see in the history section, because, well, deleting loads of stuff tends to upset people. But if enough people agree with me, then I might have a go. MrDemeanour (talk) 10:44, 17 September 2018 (UTC)

Nit on reference in section on Mechanical contrivances with discrete states. It starts with: "The clock: Bolter credits the invention of the weight-driven clock as "The key invention [of Europe in the Middle Ages]", in particular, the verge escapement[73]" This not an idea original to Bolter, it clearly comes from Lewis Mumford's Technics and Civilization (1934) and given that "key invention" is Mumford's phrase, I would guess that Bolter did not seek credit for the idea, he even quotes Mumford elsewhere. — Preceding unsigned comment added by Leo Schlosberg (talk • contribs) 22:18, 29 April 2019 (UTC)

## Computational methods, algorithms and the Halting Problem

In the lead we follow Knuth's definitions and say that the algorithm must compute an outcome in finite steps and we distinguish between an algorithm and a computational method. In the opening paragraph of the 'Informal definition' section we say that 'Generally, a program is only an algorithm if it stops eventually' citing Stone. Then the section of 'Formalization' in which we show that the prevailing academic opinion is is that the set of algorithms corresponds to the set of Turing machines through some apropriate transformation.

Since we have a 'Formalization' section and mention Turing Machines I believe it is important to mention that the definition of algorithms that requires finiteness means that we cannot tell wether a proceedure is an algorithm in the general case because of the Halting Problem. Which makes this kind of definition impractical, in the general case again.

Ofcourse, talking about well-defined processes whose termination is provably impossible to be determined is bewildering. It was bewildering among mathematicians in the times it was discovered. Maybe that's why algorithms are so difficult to conceptualize after all.

My quetion is: Mentioning the impossibility of distinguishing between algorithms and computational methods if we follow Knuth, Stone and the informal definitions in general is helpful or not helpful? I believe it is necessecary. Then again, it may not benefit the reader. It would be great if we found a way to put this mildly, withouth shocking anyone. Nxavar (talk) 18:52, 30 July 2019 (UTC)

- The relation of the Halting Problem to the informal definitions of the algorithm was just added to the main body. Nxavar (talk) 14:05, 6 August 2019 (UTC)

## Media usage

Very recently, I have noticed an increasing tendency for journalists and commentators to used the word 'algorithm' to refer to automated classifiers constructed by applying machine-learning techniques to big data. So we hear that government agencies are using algorithms to identify benefit cheats, for example. Of course the resulting classifier is not an algorithm, because the procedures it follows cannot be specified - these classifiers are 'black boxes'.

I fear that the word is losing its 'unambiguous specification' sense, because these media types think it makes them look clever to be using such a big, technical-sounding word.

Is it worth emphasising that distinction in this article? Like King Canute we can't hold the tide back, but we can at least plant a stick in the sand to show where high-tide used to be, no? MrDemeanour (talk) 09:19, 17 September 2018 (UTC)

- Strictly speaking, the classifier
*is*an algorithm. The procedures related to deep learning and similar processes are well specified and well documented. The only thing interesting about the "black boxes" is that the data stored inside them is obscured, but the process used to munge that data is not. Plokmijnuhby (talk) 09:52, 5 February 2020 (UTC)

## Proposed split

I believe that the content in the Algorithm#Design section should be split into a new article located at either Algorithm design or Algorithmic design, because the topic of "Algorithmic design" is a notable topic in conjunction with Parametric design and Generative design. [2]. In addition, the article of Algorithm is rather long in it's current state, so a content split could be appropriate depending on the outcome of this discussion. The section was BOLDly merged from the Algorithm design page; however, while the article had definitive issues from the previous tags, I don't believe that merging was the correct decision. Utopes _{(talk / cont)} 00:38, 9 March 2020 (UTC)

- I should add that the section is not the longest by any means, and the new article would need general substantial improvement. With that being said, I do think that this subject holds too much significance to be a subsection of a larger, generalized article on algorithms. [3], [4], [5], [6], [7], [8], [9], [10]. Utopes
_{(talk / cont)}00:50, 9 March 2020 (UTC)

As discussed in the talk page of the original article, substantial work will need to be done in order to bring this section up to WP:notability standards and everything must be verifiable. The original article was ultimately deleted and redirected here due to serious inaccuracies that did not seem worth fixing at the time. If you wish to take on this task, it might be best if you could build a draft page of your proposed new article, and post a link here for others to agree or disagree with the split. Much more information than what is currently in this section will be required to create a new article. In addition, you will need to write a new summary of the content to go in this article. I agree that algorithm design is almost certainly notable enough to have its own article, but it will require work to get it there. I also think that the history section in this article should probably get its own page, and maybe classification too. This article is far too large. Footlessmouse (talk) 07:00, 20 August 2020 (UTC)

- A simpler approach would be to just start improving Algorithm#Design and come back here when there's enough verifiable content there to resume this discussion. ~Kvng (talk) 14:08, 23 August 2020 (UTC)

- Yes, that's a great idea. If you improve the section to a point where it obviously deserves its own article, the split discussion would arise organically. Footlessmouse (talk) 22:40, 23 August 2020 (UTC)

## Heuristic algorithm

I was surprised to read that a heuristic is not a type of algorithm. I thought any exact specification of elementary steps was an algorithm and that there was a distinction between those that can provably solve a task, and others that just apply heuristics, that is they seem to work well in practice but they are not amenable to a mathematical proof. See for instance https://optimization.mccormick.northwestern.edu/index.php/Heuristic_algorithms — Preceding unsigned comment added by A1957 (talk • contribs) 17:20, 16 November 2021 (UTC)

- I am also confused by this comment in the intro. It's not talking about heurstic algorithms (the article mentions heuristic algorithms later on as a type of algorithm), but rather Heuristics a problem-solving technique. What is confusing is why "algorithm" is contrasted with "heuristic" as if these are somehow opposites. Caleb Stanford (talk) 18:13, 16 November 2021 (UTC)

- Added Template:non-sequitur, please discuss here. Caleb Stanford (talk) 18:24, 16 November 2021 (UTC)

- I have reworded the explanation of a heuristic. The classic introduction to heuristics is Polya's
*How to Solve It*. It presents a variety of approaches to solving a problem which may or may not work, and which are sometimes fairly vague (like "try a simple example"). - "Heuristic algorithm" something else again, though it is not great terminology, though I know it's used. Better would be "heuristic program", one which tries a variety of approaches to see if any of them work. --Macrakis (talk) 18:28, 16 November 2021 (UTC)

- I have reworded the explanation of a heuristic. The classic introduction to heuristics is Polya's

@Macrakis: Thanks for the edit. I'm more or less happy with the current sentence. Caleb Stanford (talk) 18:37, 16 November 2021 (UTC)

## Issue In Algorithm Analysis

In the section Algorithm Analysis of this article, I found saying:

for example, the sorting algorithm above has a time requirement of O(n)

In this article, there is no sorting algorithm described above as far as I saw, and there is no existing sorting algorithm (except non-deterministic ones) which's time complexity is O(n). Did I miss something? — Preceding unsigned comment added by A.H.M Fuad (talk • contribs) 20:28, 24 September 2020 (UTC)

- Caleb Stanford (talk) 22:20, 16 November 2021 (UTC) Fixed!