next up previous contents
Next: Turing Machine Up: AI Lecture 1 Previous: Information theory   Contents

Compution theory

``Algorithm'' is named after the 9th C Persian mathematician Abu Ja'far Mohammed ibn Mûsâ al-khowârizm who wrote, around 825 A.D., the book Kitab al jabr w'al-muqabala (it is conjectured that al-khowârizm got many of his ideas through the study of Indian texts but these original sources are now lost; algorithms existed in Greek times eg. Euclid's algorithm for finding the HCF of two numbers (300 B.C.), + in India?).

Loosely, an algorithm is a finite, systematic procedure. One the simplest and also historically most important description of an algorithm is in terms of the Turing Machine (TM).

Alan Turing's 1936 paper proved the existence of a simple, general form (universal language) thought to underly all possible algorithmic computations. A Turing machine can (as far as is known) carry out any well-defined series of formal operations.