任意の入力（与えられたアルゴリズムで可能な一定数の入力のうち）から始まり、入力によって完全に決まる結果（または出力）を得ることを目的とした命令で、計算過程（このときアルゴリズム的と言われます）を定義する詳細な指示。 例えば、小学校で習う列順の足し算、引き算、掛け算、割り算はアルゴリズムであり、これらのアルゴリズムで考えられる結果は10進法で書かれた非負の整数であり、考えられる入力はその数の順序付けられた組である。 あるアルゴリズムをある入力に適用する過程（すなわち、この入力を起点として進行するアルゴリズム的過程）は、結果を得ることなく終了することもあるし（この場合、無結果停止となる）、全く終了しないこともあり得る。 プロセスが終了する（終了しない）場合、その入力は当該アルゴリズムに適している（適していない）と言う。
この分野における重要な結果は、いわゆる停止問題の決定不可能性である。 特に、可能な入力の集合が自然数の集合であるようなアルゴリズム$ \alpha $を見つけることができます。 以下にその例を示します。 ある型の方程式の数値解を求めることは、この型の任意の方程式と任意の正の有理数$ \epsilon $を、この方程式の根と$ \epsilon $より小さい差のある数（または数の集合）に変換するアルゴリズムを構築することと等しい。 ただし、アルゴリズムの文脈で使われる「計算過程」という言葉は、単に数値計算を意味するものであってはならず、初等代数学でも文字を使った計算が行われている。 標準的な算術計算には数字以外の記号（括弧、等号、算術演算子の記号）が使われる。 そこで、任意の記号を含むアルゴリズムや、記号から構成されるオブジェクトを考えることが有効である。 最も単純な例は、単語を構成する記号の直線的な列である。 また、代数的行列、形式言語の導出木、一般的なグラフなど、「非線 形」オブジェクトを考慮することも可能である。 直感的には、アルゴリズムの入力と結果に対する最小の要件は、それらが構成的オブジェクトでなければならないということです（cf. 構成的オブジェクト）。 このように、アルゴリズムの概念は非常に一般的である。 ある言語から別の言語への翻訳アルゴリズム、航空管制官のアルゴリズム（航空機の運動に関する情報を一定の規則に従って処理）、その他アルゴリズムで記述された制御プロセスの例などを挙げることができる。 その結果、アルゴリズムという概念は、サイバネティックスやコンピュータサイエンスの中心的な考え方の1つとなっている。
アルゴリズムの例
入力と結果の可能性を、アルファベット$ \{ a, b } $上のすべての可能な単語とする。 ある単語$ X $からある単語$ Y $への遷移が「許される」のは、次の2つの場合（ここで$ P $は任意の単語を表す）：1）$ X $が$ aP $の形で、$ Y $が$ Pb $の形、または2）$ X $が$ baP $の形で、$ Y $が$ Paba $の形。 命令は以下の通り定式化されている。 「ある単語を入力とし、aaPの形の単語が得られるまで許可された遷移を実行し、その後停止して単語Pを結果とする」。 これらの命令が1つのアルゴリズムを構成し、これを$ \mathfrak A $と呼ぶことにする。 ここで、アルゴリズムは $ baaba $ という結果を得て停止する。 別の入力 $ baaba $ を考える。 すると，$ abaaba, baabab, abababa, bababab, babababa , … と続けて得られる． この処理は決して終わらない（つまり、生成される単語はどれも $ aa $ で始まらない）ことが示される。 ここで、$ abaab $を入力とする。 baabb, abbaba, bbabab $を得る。これ以上許容される遷移はなく、同時に終了条件も満たされない。 無結果停止となる。 このように、入力$ babaa $は$ \mathfrak A $に適しており、入力$ baaba $と$ abaab $は適していない。
アルゴリズムの意義
科学において、アルゴリズムはどこでも遭遇します：問題の「一般」解はアルゴリズムが必要です。 人間が数字を足す能力はその一例である。 どんな2つの数の和も遅かれ早かれ求められるということではなく、文字で与えられたどんな2つの数の足し算も一意にできる方法、つまりよく知られた列方向加算法のような加算アルゴリズムを持っているという意味においてである。 “一般的に “問題を解くことは、アルゴリズム的な問題を解くこととして定式化される。 アルゴリズム問題は別々の問題インスタンスから構成され、それらすべての解を求める単一のアルゴリズムが必要である。 もしそのようなアルゴリズムがない場合、そのアルゴリズム問題は解けないということになる。 従って、ある型の方程式を数値的に解く問題や、自動翻訳の問題はアルゴリズム問題である。 その問題インスタンスは、それぞれ、与えられた型の個々の方程式の数値解を求めることと、個々のフレーズの翻訳である。 他の例としては、代数学における代数的等式の検証、数理論理学における与えられた公理から命題の演繹性を認識するアルゴリズム問題などがある。 (数理論理学では、アルゴリズムという概念も重要で、これは直感的な「証明」「実証」という概念を一般化し、より正確にしたものである「微積分」という重要な概念の基礎となっている) 与えられたアルゴリズム問題（例えば、ある論理数学的言語における文の真理性または実証性を確立する問題）の解決不可能性を確立することは、原理的に、その問題の特定の問題インスタンスは、個々の問題インスタンスに固有の方法によってのみ解決できることを示すので、重要である
アルゴリズムの概念の科学的重要性は長い間認識されていた。 古くから、人々は数学的問題を解決するための建設的な方法を探してきた。 このような努力は、通常、適切な記号的表記法の新たな利用可能性から利益を得ていた。 特に、ある種の問題が本質的に解決不可能であること（円の二乗など）が明らかになった後、このプロセスは科学的知識に大きな貢献をしてきた。 ある種の問題が直接計算では解けないことが認識された後、19世紀に集合という理論的な概念が生まれたのである。 この概念が急速に発展した時期（現代的な意味での構成的手法の問題を含まない）を経て、20世紀半ばに構成的問題に戻ることが可能になったが、それは、その間に結晶化したアルゴリズムの概念によって豊かになった、別の次元での問題であった。 この概念は、数学における構成的傾向の基盤を形成している。
「アルゴリズム」という言葉は、9世紀のアラブの数学者アル・クワリズミーの名前のラテン語訳である「アルゴリトミー」という言葉に由来している。 中世ヨーロッパにおける「アルゴリズム」とは、「十進法とそれを用いた計算術」のことで、位置法がヨーロッパに導入されたのは、アル・クワリズミの論文のラテン語訳（12世紀）であるからだ。 したがって、単語 $ baaba $ にアルゴリズム $ \mathfrak A $ を適用すると、単語 $ baaba, abaaba, baabab $ などのように連続的に続くことになります。 例えば、数字<307, 49 >の組に列方向の引き算のアルゴリズムを適用すると、次のような構成的オブジェクトが次々に得られる：
$ \begin{array}{rrr}307 &3 \dot{0} 7 &Thesisdot{3} >$5503 \♪♪～ \dot{0} 7 \underline{- 49 }. &アンダーライン{- 49 }. &アンダーライン{- 49 }. & Underline{- 49 }. \\{} & 8 &58 &258 \end{array}$$
連続する構成的オブジェクトにおいて、それぞれの連続する構成的オブジェクトは（与えられたアルゴリズムの枠内で）その直前の構成的オブジェクトによって完全に決定されていることに注意されたい。 より厳密なアプローチでは、任意の構成的オブジェクトからその直後のオブジェクトへの移行が十分に「初歩的」であることも仮定される–先行オブジェクトから直後のオブジェクトへの1ステップ変換が局所的であるという意味で（変換されるのは構成的オブジェクト全体ではなく、そのアルゴリズム限定部分のみ、さらに、この変換自体が、先行オブジェクト全体ではなく、その限定部分のみにより決定される）。
したがって、人は可能な入力と可能な結果のセットだけでなく、可能な中間結果のセットを持ち、アルゴリズム的プロセスが発展している作業媒体を表しているのである。 しかし、列ごとの引き算のアルゴリズムでは、可能な入力は数の組、可能な結果は数（すべて10進法）、可能な中間結果は
$$ 型の「3階建て」レコードになります。 \\ ここで、$qは10進数で書かれた記録、$rは同様の記録または空白語、$pは10進数で書かれた記録で、一部の桁にドットをつけたものです。 原則として、アルゴリズムの特徴であるいくつかの（独立ではない）パラメータは、 1）可能な入力の集合、2）可能な結果の集合、3）可能な中間結果の集合、4）開始規則、 5）直接遷移規則、6）終了規則、7）結果の検索規則、に区別することができ る。
アルゴリズムの概念の公式化
一般的な形のアルゴリズムの概念は、より単純な概念では定義できない基本的な数学的概念である。 厳密には、アルゴリズムの概念の形式化は、実際にはそれをいくらか制限する。 そのような形式化では、各パラメータが変化してもよいあるクラスの正確な定義が与えられます。 様々な形式化は、そのようなクラスの選択によって互いに異なる。 パラメータはあるアルゴリズムを明確に定義しているので、パラメータ領域の選択によって、あるアルゴリズムのクラスが決定される。 しかし、そのような選択は、任意の「直感的な」アルゴリズムに対して、検討中の選択によって定義されるアルゴリズムのクラスに等価なアルゴリズムが存在すると確信できる場合にのみ、アルゴリズムの直感的な概念の形式化であると主張することができる。 この要件は各正式化において基本的な仮説として定式化されており、現在の知識では数学的に証明することはできない。
このタイプの最初の形式化はE.L. Post
とA.M. Turing 、彼らの構成は多くの点で現代のコンピュータが基づいているアイデアを先取りしている。 また、マルコフ(A.A. Markov)
(cf. Normal algorithm) やコルモゴロフ (A.N. Kolmogorov) によるものもあり、彼らはある種の構成的位相複合体に基づいてアプローチし、変換の「局所性」という性質をより正確に表現することが可能になった。 これらの形式化のいずれにおいても、基本仮説は実践と十分な一致をみている。 この仮説を支持するもう1つの論拠は、実証されるように、提案された（有効計算可能性の）すべての形式的バージョンが等価であるという事実である
例として、チューリングの提案した形式化を考えてみよう。 その原型は、1）連続したセルに分割された無限テープ、各セルは機械の「テープ・アルファベット」のうち何らかの記号を含むことができる、2）各時点で（与えられた有限の状態リストのうち）何らかの「状態」にある「有限の制御」から成るある理論コンピュータの記述であった。 有限制御は、テープに沿って一度に1セルずつ移動することができ、通過したセルの内容を変更することができる。 有限制御の動きを監視するプログラムは、このような機械で行われる計算のアルゴリズム（「チューリング・アルゴリズム」）を構成する。 より正確で詳細な説明は、チューリングマシンを参照。 ここでは、チューリングの構成を現代風にアレンジした解説を行う。 チューリングアルゴリズムを定義するには、a) 対になった不連続なアルファベット $ B, D, C $ を指定し、D $ には識別文字 $ \lambda $ が、C $ には識別文字 $ \alpha $ と $ \omega $ が入っているものとする。 b) $ \langle p \xi , \eta Tq \rangle $ここで $ p, q \in C $, $ \xi , \eta \in B \cup D $, $ T $ は -, 0, + $ の3つの記号のうちの1つ; この集合（これをプログラムと呼ぶ）には、同じ第1座標の対は2つとし て存在しない。 入力と出力は$ B $上の単語であり、中間結果は$ B \cup D \cup C $上の単語で$ C $を1文字以上含まないものでなければならない。開始規則は最初の単語$ P $を$ \lambda \alpha P \lambda $に変換すること、終了規則は中間結果に$ \omega $が含まれていれば最終結果とすることである。 出力の取り出し規則は、最終中間結果のうち、$ \omega $に続き、$ B $に属さない最初の文字より前の文字の並びを出力とする。 $ A $を$ A ^ \prime $に変換する変換規則は次の通りである。 A $の左と右に$ \lambda $を書き、こうしてできた単語のうち、$ \epsilon p \xi $（$ p \in C $, $ \epsilon \xi \in B \cup D $）の形の部分は、規則に従って単語$ Q $に置き換えられる。 プログラム中に初項 $ p \xi $ の組を求め、この組の第2項を $ \eta Tq $ とし、$ T $ が $ – $ なら $ Q = q \epsilon \eta $、$ T = 0 $ なら $ Q = \epsilon q \eta $ とする。 Tが$ + $であれば、$ Q = \epsilon \eta q $である。この交換で生成される単語は$ A ^ \prime $である。 参考文献： , , , , ,
of Algorithms, theory of.
上記の基本仮説は通常、チャーチ・チューリング仮説またはチューリング仮説と呼ばれる。 このテーゼは、何が効果的なプロセスを構成するかについての人の直感に従って効果的に計算できるものは、チューリング機械、すなわち正式に定義されたアルゴリズムの概念によっても計算できることを述べている。 直感的な非公式概念と正式な正確な定義を識別するというその性質上、チャーチ・チューリング論文は正式には証明できない。
多くの正式化が同等であることが判明しており、厳密に強力であることが判明した正式化はない。 上記の形式化とは別に、欧米では以下の文献が最も標準的なものである。 チャーチのラムダ項による数と計算可能な関数の形式化、クリーネの一般再帰スキーム、シェファードソンとスタージスの提案したレジスタマシンモデル、そしてそれをより現実的なコンピュータモデルに拡張したクックとレックホーのモデルなどである。 マルコフやコルモゴルフのバージョンはあまり知られていない。 6564>
| A.M.Turing, “On computable numbers, with an application to the Entscheidungsproblem” Proc. London Math.Soc. Ser. 2 , 42 (1936) pp. 230-265 | |
| A.M. Turing, “Corrections to “On computable numbers, with an application to the Entscheidungsproblem” ” Proc.M.Turing, “On computable numbers, with an application to the Entscheidungsproblem” ” Proc.M.Turing, “On computable numbers, with an application to the Entscheidungsproblem” ” Proc. London Math.Soc. Ser.2 , 43 (1937) pp.544-546 | |
| A. Church, “An unsolvable problem of elementary number theory” Amer. J. Math. 58 (1936) pp.345-363 | |
| S.C. Kleene, “General recursive functions of natural numbers” Math.J. Math.Math. Ann. 112 (1936) pp.727-742 | |
| E.L. Post, “Formal reductions of the general combinatorial decision problem” Amer.L.C. (1936) pp.727-742 | |
| J.C. Shepherdson, H.E. Sturgis, “Computability of recursive functions” J. Assoc. Mach. 10 (1963) pp.217-255 | |
| S.A. Cook, R.A. Reckhow, “Time-bounded random access machines” J. Computer and System Sciences , 7 (1973) pp.354-375 |