アルゴリズム
チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明する。このレベルでは機械の状態や遷移関数の詳細は説明しない。
(以上の2つのような内容では、そもそも概要で説明したように「はっきり」していない可能性もあるし、詳細が無ければ無限ループに陥らないことを証明することもできない。従ってそもそも実際には「アルゴリズムを記述」してはいない)
ここに分類されるのは広義のアルゴリズム、ないし、遺伝的アルゴリズムのように(名前に反して)アルゴリズムではないものである。 乱択アルゴリズム - 選択を無作為(あるいは擬似無作為)的に行う。問題によっては、無作為性をもった解法が最も性能がよいと証明されているものもある。 遺伝的アルゴリズム - 生物の進化過程をまねた手法で解を求めるもの。無作為な突然変異を加えて、次世代の解を生成していく。自然淘汰と自己複製をエミュレートしているものと看做す視点から「遺伝的」という命名がされた。 ヒューリスティクス - 計算資源が限られている状況での近似解を求めることを目的としている。正解を求めるのには適さない。例えば、局所探索法、タブーサーチ、焼きなまし法といった、何らかの無作為性を導入して確率的に解を発見しようとするアルゴリズムがある。例えば焼きなまし法という名前は、冶金学の焼きなましに由来する。加熱と冷却によって金属結晶の欠陥がなくなるように、無作為性を与えて局所的な最適解に陥るのを防ぎ、徐々に無作為性を小さくすることによって最終的に1つの解に落ち着くという手法である。
科学のどんな分野にも固有の問題があり、効率的なアルゴリズムが必要とされている。ある分野の問題はまとめて研究されることが多い。そのような分類として、探索アルゴリズム、ソートアルゴリズム、マージアルゴリズム、数値アルゴリズム、グラフアルゴリズム、文字列アルゴリズム、計算幾何アルゴリズム、組合せアルゴリズム、機械学習、暗号理論、データ圧縮アルゴリズム、構文解析などがある。
各分野はオーバーラップしており、ある分野でのアルゴリズムの進歩が、時には全く異なる分野での改善につながることがある。例えば、動的計画法は、本来、産業における資源消費の最適化のために発明されたが、現在では様々な分野での各種問題に適用されている。