Algorithm

In mathematics and computer science an algorithm (the word is derived from the name of the Persian mathematician Al-Khwarizmi) is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state (contrast with heuristic). Algorithms can be implemented by computer programs, although often in restricted forms; mistakes in implementation and limitations of the computer can prevent a computer program from correctly executing its intended algorithm.

History

The word algorithm comes from the name of the 9th century Persian mathematician Abu Abdullah Muhammad bin Musa al-Khwarizmi. 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 or performing tasks.

Related Topics:
9th century - Persian - Abu Abdullah Muhammad bin Musa al-Khwarizmi - Algorism - Arithmetic - Arabic numerals - 18th century

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The first case of an algorithm written for a computer was Ada Byron's notes on the analytical engine written in 1842, for which she is considered by many to be the world's first programmer. However, since Charles Babbage never completed his analytical engine the algorithm was never implemented on it.

Related Topics:
Computer - Ada Byron - Notes on the analytical engine - 1842 - Programmer - Charles Babbage - Analytical engine

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The lack of mathematical rigor in the "well-defined procedure" definition of algorithms 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 formulated 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).

Related Topics:
Mathematical rigor - Logic - 19th - 20th centuries - Turing machine - Computer - Alan Turing - Church-Turing thesis

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Nowadays, a formal criterion for an algorithm is that it is a procedure that can be implemented on a completely-specified Turing machine or one of the equivalent formalisms. Turing's initial interest was in the halting problem: deciding when an algorithm describes a terminating procedure. In practical terms computational complexity theory matters more: it includes the problems called NP-complete, which are generally presumed to take more than polynomial time for any (deterministic) algorithm. NP denotes the class of decision problems that can be solved by a non-deterministic Turing machine in polynomial time.

Related Topics:
Formalism - Halting problem - Computational complexity theory - NP-complete - Polynomial time

~ ~ ~ ~ ~ ~ ~ ~ ~ ~