Algorithm: Difference between revisions

Revision as of 18:33, 10 April 2002

Revision as of 19:11, 10 April 2002

Line 1:

An '''algorithm''' is a well-defined method or procedure for solving a certainproblem, usually a problem in [[mathematics]] or otherwise relating to the manipulation of [[information]] rather than involving physical work (though physical work may be required to complete the algorithm). Typically, an algorithm is described as a series of actions that have to be done plus an indication of whether and when they are to be repeated. Some people define ''algorithm'' to only include procedures that eventually finish. Others define ''algorithm'' to also include procedures that run forever without stopping. Algorithms are often implemented as computer programs, but can also be implemented as circuits, or even performed directly by humans.

The word ''algorithm'' is a corruption of the word ''algorism'' which came from the name of [[al-Khwarizmi|Abu Ja'far Mohammed ibn Musa al-Khwarizmi]] (ca. 780 - ca. 850). He was the author of the book "''Kitab al-jabr w'al-muqabala''" (''Rules of Restoration and Reduction'') which introduced [[Algebra|algebra]] to people in the West. The word ''algebra'' itself originates from ''al-Jabr'' from the book title. The word "algorism" originally referred only to the rules of performing arithmetic using [[Arabic numerals]], but evolved into "algorithm" by the eighteenth century. The word has now evolved to include all definite procedures for solving problems, includingand is sometimes used to describe procedures for humans doing physical tasks - cooking, for instance. The remainder of this article relates to the definition of algorithm as advanced in this article's first :)sentence.

The lack of mathematical rigor in the "well-defined procedure" definition of algorithm posed some difficulties for mathematicians and logicians of the 19th and early 20th centuries. This problem was largely solved with the description of the [[Turing machine]], an abstract model of a [[computer]] described by Alan Turing, and the demonstration that every method yet found for describing "well-defined procedures" advanced by other mathematicians could be emulated on a Turing machine (a concept known as the [[Church-Turing thesis]]) a formal criterion for an algorithm is that it is a procedure implementable on a completely-specified Turing machine or one of the equivalent formalisms.

As an example of an algorithm, here is one given to us by [[Euclid]], and thus known as the [[Euclidean algorithm]], for finding the [[greatest common divisor]] (GCD) of two positive [[integer|integers]] A and B: