Algorithm: Difference between revisions

Revision as of 08:03, 18 December 2002

Revision as of 21:12, 18 December 2002

Line 10:

# Repeat steps 1 and 2 until A and B are equal, this number will then be the greatest common divisor of the original numbers.

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. [[845]]). 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 [[18th century]]. The word has now evolved to include all definite procedures for solving problems andor is sometimes used to describe procedures for humans doing physicalperforming tasks -- alphabetizing a box of file cards, for instance. The remainder of this article relates to the formal definition of algorithm in the field of mathematics.

The lack of mathematical rigor in the "well-defined procedure" definition of algorithm posed some difficulties for mathematicians and [[logic]]ians of the [[19th century|19th]] and early [[20th century|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 statement known as the [[Church-Turing thesis]]). Nowadays, a formal criterion for an algorithm is that it is a procedure implementable on a completely-specified Turing machine or one of the equivalent [[formalism]]s.