アルゴリズムの特性

アルゴリズムの特徴付けとは、「アルゴリズム」という言葉を形式化しようとする試みである。アルゴリズムには、一般的に受け入れられている形式的な定義は存在しない。研究者^{[ 1 ]}はこの問題に積極的に取り組んでいる。本稿では、「アルゴリズム」という概念の「特徴付け」のいくつかについて、より詳細に紹介する。

過去200年の間に、アルゴリズムの定義は、研究者たちがその用語を明確にしようと試みるにつれて、より複雑かつ詳細になってきました。実際、「アルゴリズム」には複数の種類があるかもしれません。しかし、ほとんどの研究者は、アルゴリズムとは、紙と鉛筆を使って人が実行できる有限の規則の集合によって、識別可能な記号（自然数）を操作することによって、他の「入力」整数（範囲が任意かつ無限であるか、範囲が限定されているものの可変である「入力パラメータ」）から「出力」整数を作成するための一般化されたプロセスを定義することに関係しているという点で一致しています。

形式数学と日常生活の両方で最も一般的な数値操作スキームは、(1)紙と鉛筆で人が計算する再帰関数、および (2)チューリングマシンまたはそのチューリング相当物、すなわち原始レジスタマシンまたは「カウンタマシン」モデル、ランダムアクセスマシンモデル^{[ 1 ]} (RAM)、ランダムアクセスストアードプログラムマシンモデル (RASP) およびその機能的相当物である「コンピュータ」です。

私たちが「算術」を行うとき、実際には小学校で習った簡略化されたアルゴリズム、例えば足し算や引き算などにおいて、「再帰関数」を用いて計算しているのです。

手計算で計算できるすべての「再帰関数」は機械でも計算でき、その逆もまた然りであるという証明（計算する、計算するという言葉の使い方に注目）は注目に値する。しかし、この等価性と、これがすべての計算を含むというテーゼ（証明されていない主張）は、特定のアルゴリズムの定義においてチューリングマシンと同等の機械の使用がなぜこれほど重視されてきたのか、そして「アルゴリズム」の定義自体がしばしば「チューリングマシン」に言及する理由を示している。これについては、スティーブン・クリーネによる特徴付けの項でより詳しく論じられている。

以下は、より有名な特徴付け（クリーネ、マルコフ、クヌース）の概要と、定義をさらに拡張したり、より正確な定義に貢献したりする新しい要素を導入した特徴付けの概要です。

数学の問題とその結果は、 空間内の2点と見なすことができ、解はそれらを繋ぐ一連の手順、あるいは経路から構成される。解の質は経路によって決まる。経路には、長さ、形状の複雑さ、一般化の容易さ、難易度など、複数の属性が定義される可能性がある。

「単純なアルゴリズム」という概念の「特徴づけ」については、より多くの合意が得られている。

すべてのアルゴリズムは形式言語で記述する必要があり、「単純性の概念」は言語の単純性から生じます。チョムスキー階層（1956）は、形式言語を生成する形式文法のクラスの包含階層です。これは、プログラミング言語や抽象機械の分類に使用されます。

チョムスキー階層の観点から言えば、アルゴリズムが（制約のない）より単純な言語で記述できる場合、それはこの種の言語によって特徴づけられ、そうでない場合は典型的な「制約のないアルゴリズム」である。

例： M4のような「汎用」マクロ言語は制限がない（チューリング完全）が、Cプリプロセッサマクロ言語は制限がないため、 Cプリプロセッサで表現されたアルゴリズムはすべて「単純なアルゴリズム」である。

複雑性クラス間の関係も参照してください。

ScheiderとGersting（1995）で論じられているように、明確に定義されたアルゴリズムには以下のような望ましい特徴がある。

• 明確な操作：アルゴリズムには、具体的で明確な手順が必要です。各手順は、それぞれの段階で何を行うべきかを正確に指定できるほど正確でなければなりません。
• 整然とした順序：アルゴリズムで実行される操作の正確な順序は、具体的に定義されるべきである。
• 実現可能性：アルゴリズムのすべてのステップは実行可能である必要があります（実質的に計算可能であるとも呼ばれます）。
• 入力：アルゴリズムは、明確に定義された一連の入力を受け入れることができなければならない。
• 出力：アルゴリズムは、その正しさを検証できるように、何らかの結果を出力として生成する必要がある。
• 有限性：アルゴリズムは有限個の命令の実行後に終了するべきである。^{[ 2 ]}

特定のアルゴリズムに求められる特性としては、空間効率と時間効率、汎用性（つまり、多くの入力を処理できること）、決定性などが挙げられる。

1870年初頭、W.スタンレー・ジェボンズは、三段論法やその他の論理形式（例えば、ブール方程式に還元された議論）を分析するための「論理機械」（ジェボンズ 1880:200）を発表した。クチュラ（1914）が「一種の論理ピアノ」と呼んだものによって、前提を表す等式はタイプライターのようなキーボードで「演奏」される。すべての前提が「演奏」されると、パネルには合計が1に等しい構成要素、つまり論理全体のみが表示される。この機械的な方法は、ベンの幾何学的方法よりも優れている…」（クチュラ 1914:75）。

一方、ジェボンズと同時代の論理学者ジョン・ヴェンは、あまり感激しておらず、「現在知られている、あるいは今後発見されるであろういかなる仕掛けも、論理機械という名にふさわしいとは思えない」と述べている（ヴェン 1881:120、強調追加）。しかし、「アルゴリズム」という概念の発展にとって歴史的に有用なのは、彼が「そうでなければ避けられない労力を回避することで、真に価値のある目的を果たすかもしれない」機械に対して否定的な反応を示した理由の説明である。

（１）「まず、我々のデータを正確な論理言語で記述する」

（２）「次に、これらの命題をエンジンが処理できる形式に変換する必要がある。この場合、各命題をその基本的な否定に還元する」

（３）「第三に、上記減額後の当社の施設の組み合わせまたはさらなる処理があります。」

（４）「最後に、結果を解釈したり読み取ったりする必要がある。この最後の段階は、一般的に、スキルと洞察力を発揮する余地を大きく広げる。」

彼は「これらのステップのうち3番目以外では、いかなる機械も我々を助けることはできないと思う。したがって、このようなものが論理エンジンという名に値するかどうかは非常に疑わしい」と結論付けている（Venn 1881:119–121）。

このセクションは、そのトピックにとって重要であるため、他のセクションよりも長く詳細になっています。クリーネは、あらゆる種類の計算/演算のすべてが、 (i) 5 つの「原始再帰演算子」と 1 つの特殊演算子であるミュー演算子を使用して計算するか、(ii)チューリングマシンまたは同等のモデルの動作によって計算することができると最初に提案しました。

さらに彼は、これらどちらもアルゴリズムの定義として成立するだろうと述べた。

これから述べる言葉を初めて目にする読者は戸惑うかもしれないので、簡単に説明しておこう。計算とは手作業で行うことを意味し、演算とはチューリングマシン（または同等のもの）で行うことを意味する。（時々、著者が言葉を間違えることがある。）「関数」は「入力出力ボックス」と考えることができ、そこに「引数」または「パラメータ」と呼ばれる自然数（ただし、0を含む非負整数のみ）を入力すると、単一の非負整数（慣習的に「答え」と呼ばれる）が出力される。「関数ボックス」は、手作業で「一般再帰」を用いて計算するか、チューリングマシン（または同等の機械）で演算を行う小さな人間だと考えてみよう。

「実質的に計算可能」はより一般的な表現で、「何らかの手順、方法、技術などによって計算可能」という意味です。「一般再帰」は、今日では単に「再帰」と呼ばれるものをクリーネが表現した方法でしたが、「原始再帰」、つまり5つの再帰演算子を用いた計算は、まれな場合にのみ必要となる6番目の追加のμ演算子にアクセスできない、より低次の再帰です。そのため、日常生活のほとんどは「原始再帰関数」だけで済んでいます。

アンドレイ・マルコフ・ジュニア（1954年）は、アルゴリズムについて次のような定義を示した。

「1. 数学において、「アルゴリズム」とは、一般的に、さまざまな初期データから望ましい結果に至る計算プロセスを定義する、正確な手順書として理解されている。

「以下の3つの特徴はアルゴリズムに特有のものであり、数学におけるアルゴリズムの役割を決定づけるものである。」

「a) 処方の正確さ、恣意性の余地がないこと、そして普遍的な理解可能性、つまりアルゴリズムの明確さ」

b) 与えられた範囲内で変動する可能性のある初期データから開始できる可能性 ― アルゴリズムの汎用性。

c) アルゴリズムが望ましい結果を得る方向に向かっていること、そして適切な初期データを用いることで最終的にその結果が得られること――アルゴリズムの確実性。」（1ページ）

彼はこの定義が「数学的な正確さを装うものではない」と認めた（ 1ページ）。1954年の彼のモノグラフは、アルゴリズムをより正確に定義しようとする試みであり、その結果として得られた定義、すなわち彼の「通常の」アルゴリズムは「再帰関数の概念と同等である」と彼は考えた（3ページ ）。彼の定義には4つの主要な構成要素が含まれていた（第II.3章 63ページ以降）。

「1. それぞれが[置換]規則のいずれかに従って実行される、個別の基本ステップ...[冒頭で示された規則]」

「2. ...局所的な性質のステップ... [したがって、アルゴリズムは、観測対象の単語/記号の左右にある一定数以上の記号を変更することはありません]」

「3．置換式の規則…[彼はこれらのリストをアルゴリズムの「スキーム」と呼んだ]

「4. …「終結置換」を区別する手段[すなわち、区別可能な「終端/最終」状態または複数の状態]」

マルコフは序論の中で、アルゴリズムをより正確に定義しようとする試みの「数学にとっての意義全体」は「数学の構成的基礎の問題と関連している」と述べている（ 2ページ）。イアン・スチュワート（ブリタニカ百科事典参照）も同様の考えを示しており、「…構成的解析は、コンピュータ科学と非常によく似たアルゴリズム的精神に基づいている…」と述べている。詳しくは、 「構成的数学」および「直観主義」を参照のこと。

識別可能性と局所性：これらの概念はどちらもチューリング（1936～1937年）によって初めて登場した。

「新たに観測された正方形は、コンピュータ（1936年当時はコンピュータは人間であった）によって即座に認識されなければならない。それらは、直近に観測された正方形のうち最も近い正方形からの距離が一定の固定値を超えない正方形でなければならないと考えるのが妥当だと思う。新たに観測された正方形はそれぞれ、以前に観測された正方形のいずれかからL個の正方形以内にあるとしよう。」（チューリング（1936）デイビス編『決定不能』136ページ）

局所性は、グレヴィッチとガンディ（1980）（グレヴィッチが引用している）の研究において重要な位置を占めている。ガンディの「メカニズムの第4原理」は「局所的因果律」である。

「ここで、我々の原理の中で最も重要な点について述べよう。チューリングの分析では、作用が記録の限られた部分のみに依存するという要件は、人間の限界に基づいていた。我々はこれを、局所的因果律の原理と呼ぶ物理的な限界に置き換える。その正当性は、効果と信号の伝播速度が有限であることにある。現代物理学は、遠隔での瞬間的な作用の可能性を否定している。」（ガンディ（1980）J.バーワイズ他編著、135ページ）

1936年：クルト・ゲーデルの有名な言葉が、マーティン・デイヴィスが翻訳した論文「証明の長さについて」の「（ドイツ語原著の）校正に追加された注釈」として、『決定不能なもの』 の82～83ページに掲載されている。クリーネ、グレヴィッチ、ガンディなど多くの著者が、以下の言葉を引用している。

「したがって、『計算可能』という概念はある特定の意味で『絶対的』であるのに対し、他のほとんどすべての馴染みのあるメタ数学的概念（例えば、証明可能、定義可能など）は、本質的にそれらが定義されるシステムに依存している。」（83ページ）

1963年：ゲーデルは、有名な論文「形式的に決定不可能な命題について」（1931年）に1963年8月28日付で追加された「注釈」の中で、（脚注で）「形式体系」には「原理的に、その体系における推論は機械装置によって完全に置き換えられる」という特徴的な性質があると述べている（ van Heijenoort著、616ページ）。「…A.M.チューリングの研究のおかげで、形式体系の一般的な概念の正確かつ疑いなく適切な定義を与えることができ、定理VIと定理XIの完全な一般版が可能になった」（ 616ページ）。1964年の別の著作への注釈では、同じ意見をより強く、より詳細に述べている。

1964年：1934年春にプリンストン高等研究所で発表した論文に対する1964年付けの追記の中で、ゲーデルは「形式体系」とは機械化可能な体系であるという自身の確信をさらに強調した。

「その後の進歩、特にA.M.チューリングの研究により、形式体系の一般概念について正確かつ疑いなく適切な定義を与えることができるようになったという事実の結果として、…チューリングの研究は「機械的手順」（別名「アルゴリズム」または「計算手順」または「有限組み合わせ手順」）の概念の分析を提供している。この概念は「チューリングマシン」の概念と同等であることが示されている。* 形式体系は、証明可能な式と呼ばれる式を生成するための任意の機械的手順として単純に定義することができる…」（マーティン・デイビス編『決定不能なもの』72ページ：「形式数学体系の決定不能な命題について」の「追記」、前掲書39ページ）

*印は脚注を示しており、ゲーデルはそこでアラン・チューリング（1937年）とエミール・ポスト（1936年）の論文を引用し、その後、次のような興味深い発言をしている。

「計算可能性に関する以前の同等の定義については、ただしそれらは我々の目的にはあまり適していないので、Alonzo Church、Am. J. Math.、vol. 58 (1936) [ The Undecidable pp. 100-102に掲載]を参照のこと。」

チャーチの定義には、いわゆる「再帰」と「ラムダ計算」（すなわちλ定義可能な関数）が含まれる。彼の脚注18には、彼が「実効計算可能性」と「再帰性」の関係についてゲーデルと議論したが、「実効計算可能性」と「λ定義可能性」については独自に疑問を呈したと記されている。

^{「我々はここで、正の整数の再帰関数18} （または正の整数のλ定義可能な関数）の概念と同一視することによって、正の整数の効果的に計算可能な関数の概念を定義する。

「既に指摘したように、先ほど定義した意味で効果的に計算可能な正の整数の関数はすべて、その値を計算するアルゴリズムが存在する。」

「逆に言えば、それは真実である…」（『決定不能なもの』100ページ）。

このことから、そして以下のことからもわかるように、ゲーデルにとってチューリングマシンは十分であり、ラムダ計算は「はるかに不適切」であったようだ。彼はさらに、人間の理性の限界に関しては、まだ結論が出ていないと指摘している。

（「アルゴリズムと等価でない有限の非機械的手順が存在するかどうかという問題は、『形式システム』および『機械的手順』の定義の妥当性とは全く関係がないことに注意されたい。」）（前掲書72ページ）

（脚注**で示されているより一般的な意味での理論や手順については、状況が異なる場合がある。なお、後書きで述べた結果は、人間の理性の能力に限界を設けるものではなく、数学における純粋な形式主義の潜在能力を示すものである。）（前掲書73ページ）

脚注**：「つまり、抽象的な用語をその意味に基づいて使用するような場合です。私の論文はDial. 12(1958)、p. 280に掲載されています。」（この脚注は前掲書のp. 72に掲載されています）。

ミンスキー（1967）は、「アルゴリズムとは『効果的な手順』である」と断言し、本文中で「アルゴリズム」という言葉をそれ以上使用することを拒否している。実際、彼の索引には「アルゴリズム、効果的な手順の同義語 」（ 311ページ）という彼の考えが明確に示されている。

「以降では後者の用語［効果的な手順］を使用します。これらの用語はほぼ同義ですが、特に『アルゴリズム』に関しては、文脈によって意味合いに多くの違いがあります。」（原文ではイタリック体、105ページ）

他の著者（下記のクヌースを参照）は「効果的な手順」という言葉を使っている。そこで疑問が生じる。ミンスキーの言う「効果的な手順」とは何だろうか？彼は次のように述べている。

「…それは、刻々と変化する状況において、私たちがどのように行動すべきかを正確に教えてくれる一連の規則である」（106ページ）

しかし彼は、これには批判の余地があることを認識している。

「…規則の解釈が特定の人物や代理人に委ねられているという批判がある」（106ページ）

彼の改良点とは？「規則の記述とともに、それらを解釈するメカニズムの詳細を規定する」ことである。「個々の手順ごとにこれを繰り返す」という「面倒な」プロセスを避けるために、彼は「合理的に統一された規則遵守メカニズムのファミリー」を特定したいと考えている。彼の「定式化」は以下の通りである。

（１）行動規則の集合を表現する言語、

「（２）当該言語の文を解釈し、各指定処理のステップを実行できる単一の機械。」（原文ではイタリック体、この段落の引用はすべて107ページ）

しかし結局のところ、彼は「この問題には主観的な側面が残る。ある手順が効果的であるかどうかについて、人によって意見が一致しない可能性がある」と懸念している（ 107ページ） 。

しかしミンスキーはひるまない。彼はすぐに「チューリングの計算過程の分析」（彼の第5.2章）を紹介する。彼は「チューリングのテーゼ」と呼ぶものを引用する。

「自然と有効な手順と呼ばれるプロセスはすべてチューリングマシンによって実現できる」（108ページ）。（ミンスキーは、より一般的な形ではこれは「チャーチのテーゼ」と呼ばれていると述べている）。

「チューリングの議論」（彼の第5.3章）の分析の後、彼はチューリング、チャーチ、クリーネ、ポスト、スミュリアンの「多くの直観的定式化の等価性」が「…ここに実際に『客観的』または『絶対的』概念が存在すると考えるように導く」と述べている。ロジャース[1959]が述べたように、

「この意味で、実効的に計算可能な関数という概念は、数学の基礎に関する現代の研究によって生み出された数少ない『絶対的な』概念の一つである。」(ミンスキー、111ページ、ロジャース、ハートリー・ジュニア（1959）『チューリングマシンの計算可能性に関する現在の理論』、J. SIAM 7、114-130からの引用)

ハートリー・ロジャースは、1967年の著書『再帰関数と有効計算可能性の理論』の中で、「アルゴリズム」を大まかに「記号入力に適用され、最終的に各入力に対して対応する記号出力を生成する事務的な（つまり、決定論的な、簿記的な）手順」と特徴づけている（1ページ ）。そして、この概念を「おおよそ直感的な用語で」10の「特徴」を持つものとして説明し、そのうち5つについては「事実上すべての数学者が同意するだろう」と主張している（ 2ページ）。残りの5つについては、「1～5ほど明白ではなく、それについては一般的な合意が得られないかもしれない」と主張している（3ページ ）。

5つの「明白な」例は以下のとおりです。

• 1 アルゴリズムとは、有限サイズの命令の集合であり、
• 2 有能な計算エージェントが存在する。
• 3.「計算の手順を作成、保存、取得するための設備がある」
• 4. 与えられた条件1と2に基づいて、エージェントは連続的な方法やアナログデバイスを使用せずに「離散的な段階的方法」で計算を行う。
• 5 計算エージェントは「サイコロなどのランダムな方法や装置に頼ることなく」計算を進める（脚注でロジャースは4番と5番が本当に同じかどうか疑問を呈している）。

彼が議論の対象としている残りの5つは以下のとおりです。

• 6 入力のサイズに固定の上限はありません。
• 7 命令セットのサイズに固定の上限はありません。
• 8 利用可能なメモリ容量に固定の上限はありません。
• 9 計算エージェントの容量または能力に対する固定された有限の制限（ロジャースは、ポストチューリングマシンやカウンタマシンに似た単純なメカニズムを例に挙げて説明しています）。
• 10 計算の長さの上限 ― 「計算にどれくらいの時間がかかるかを『事前に』把握しておくべきでしょうか？」(p.  5)。ロジャースは「計算が有限のステップ数で終了することだけを要求しており、この数を事前に推定できる能力を要求しているわけではない」と述べています(p.  5)。

クヌース（1968年、1973年）は、アルゴリズムの要件として広く受け入れられている5つの特性を挙げている。

1. 有限性：「アルゴリズムは常に有限のステップ数で終了しなければならない…非常に有限な数、妥当な数でなければならない」
2. 明確性：「アルゴリズムの各ステップは正確に定義されなければならない。各ケースにおいて実行されるアクションは、厳密かつ曖昧さなく指定されなければならない。」
3. 入力：「…アルゴリズム開始前に最初に与えられる数量。これらの入力は、指定されたオブジェクトのセットから取得されます。」
4. 出力：「入力値と特定の関係を持つ数量」
5. 有効性：「…アルゴリズムで実行されるすべての操作は、原理的には紙と鉛筆を使って人間が正確に、かつ有限時間内に実行できるほど十分に基本的なものでなければならない。」

クヌースは、2つの自然数の最大公約数を求めるためのユークリッドの互除法を例として挙げている（クヌース著『第1巻』2ページ参照）。 

クヌースは、アルゴリズムの説明は直感的には明確かもしれないが、形式的な厳密さに欠けることを認めている。なぜなら、「厳密に定義されている」とはどういう意味か、「厳密かつ曖昧さなく指定されている」とはどういう意味か、「十分に基本的である」とはどういう意味かなどが明確に定義されていないからである。彼は最初の著書で、この方向で努力しており、そこで「架空のMIX …世界初の多不飽和コンピュータ」（120ページ以降）の「機械語」と呼ぶものを詳細に定義している。彼の著書に掲載されているアルゴリズムの多くはMIX言語で書かれている。彼はまた、ツリー図、フロー図、状態図も使用している。 

アルゴリズムの「良さ」、つまり「最良の」アルゴリズム：クヌースは、「実際には、アルゴリズムだけでなく、優れたアルゴリズムが必要なのです…」と述べています。彼は、アルゴリズムの良さの基準として、アルゴリズムを実行するステップ数、「コンピュータへの適応性、シンプルさ、優雅さなど」を挙げています。同じ計算を実行する複数のアルゴリズムがある場合、どれが「最良の」アルゴリズムでしょうか？彼はこの種の調査を「アルゴリズム分析：与えられたアルゴリズムの性能特性を決定する」と呼んでいます（この段落の引用はすべてクヌース著『クヌース』第1巻 7ページ）。

ストーン（1972年）とクヌース（1968年、1973年）は同時期にスタンフォード大学の教授を務めていたため、彼らの定義に類似点があっても不思議ではない（強調のために太字を追加）。

「要約すると、アルゴリズムとは、各ルールが有効かつ明確であり、かつ一連の操作が有限時間内に終了するような、操作のシーケンスを正確に定義する一連のルールであると定義する。」（太字は原文ママ、8ページ）

ストーンの主張が注目に値するのは、「効果的な」ルールとは何かを詳細に論じている点である。彼のロボット、あるいはロボットのように振る舞う人間は、何らかの情報と能力を内部に備えていなければならず、そうでなければ、その情報と能力は「アルゴリズム」によって提供されなければならない。

「人々がアルゴリズムのルールに従うためには、ルールはロボットのように、つまり思考を必要とせずに従えるように定式化されなければならない。しかし、もし（彼の例である二次方程式を解くという）指示が、算術演算の実行方法は知っているが平方根の求め方は知らない人に従うことを想定するならば、アルゴリズムの定義を満たすために平方根を求めるためのルールも提供しなければならない。」(p. 4-5)

さらに、「…すべての指示が受け入れられるわけではない。なぜなら、ロボットに我々が合理的と考える能力を超える能力を要求する可能性があるからだ。」彼は、「ヘンリー8世はイングランド王か？」という質問に直面したロボットを例に挙げ、イエスなら1、ノーなら0を出力するように指示するが、ロボットには事前にこの情報が与えられていない。さらに悪いことに、ロボットにアリストテレスがイングランド王だったかどうかを尋ね、ロボットに与えられた名前が5つだけだった場合、ロボットはどのように答えるべきかわからないだろう。したがって、

「許容可能な命令シーケンスの直感的な定義は、各命令が正確に定義されており、ロボットが確実にそれに従うことができるものである。」(p. 6)

ストーンは定義を示した後、チューリングマシンモデルを紹介し、マシンの命令である5タプルの集合は「チューリングマシンプログラムとして知られるアルゴリズム」であると述べている（9ページ）。その直後、彼は「チューリングマシンの計算は次のように記述される 」と述べている。

「１．テープアルファベット

2.入力パラメータがテープ上に提示される形式

3. チューリングマシンの初期状態

4.チューリングマシンが停止したときに、回答（出力）がテープ上に表現される形式

「5．機械プログラム」（強調追加、10ページ）

「計算」に必要なものをこのように正確に規定することは、ブラスとグレヴィッチの今後の研究の精神に沿ったものである。

「計算とは、入力と呼ばれる最初に与えられた対象から、プログラム、手順、またはアルゴリズムと呼ばれる一連の規則に従って、一連のステップを経て、出力と呼ばれる最終結果に到達するプロセスである。アルゴリズムは、入力から出力へと進む一連の規則であるため、各ステップが明確に決定され、正確かつ明確でなければならない。計算可能性の概念は、原理的に計算によって指定できる対象に関するものである。」（原文ではイタリック体、3ページでは太字を追加）

1960年代半ばにプリンストン大学の学生だったデビッド・ベルリンスキーは、アロンゾ・チャーチの教え子だった（ 160ページ参照）。彼が2000年に出版した著書『アルゴリズムの到来：アイデアからコンピュータへの300年の旅』には、アルゴリズムの次のような定義が記されている。

論理学者の声で言うと：

「アルゴリズムとは

有限の手続き、

固定された記号語彙で書かれ、

正確な指示によって管理され、

離散的なステップで移動します、1、2、3、...、

その実行には洞察力や賢さは必要なく、

直感、知性、または明晰さ、

そしてそれは遅かれ早かれ終わりを迎える。（原文では太字斜体、18ページ）

Gurevich 2000 を注意深く読むと、彼が「アルゴリズム」とは実際には計算を実行する「チューリングマシン」または「ポインタマシン」であると考えている（と推測する？）という結論に至る。「アルゴリズム」とは、マシンの動作を指示するシンボルテーブルだけではなく、特定の入力パラメータセットが与えられたときに計算を実行するマシンのインスタンスだけでもなく、電源が切れた適切にプログラムされたマシンでもない。むしろ、アルゴリズムとは、マシンが実行可能なあらゆる計算を実際に実行するものである。Gurevich はこれをはっきりと述べていないため、上記のように表現されたこの結論（推測？）は確かに議論の余地がある。

「…すべてのアルゴリズムはチューリングマシンによってシミュレートできる…プログラムはチューリングマシンによってシミュレートでき、したがって正確な意味を与えることができる。」(p. 1)

「逐次アルゴリズムの概念を形式化する問題は、チャーチ[1936]とチューリング[1936]によって解決されたとよく考えられている。例えば、サベージ[1987]によれば、アルゴリズムとはチューリングマシンによって定義される計算プロセスである。チャーチとチューリングは、逐次アルゴリズムの概念を形式化する問題を解決したわけではない。彼らは、計算可能な関数の概念について（異なるが同等の）形式化を与えたのであり、アルゴリズムにはそれが計算する関数以上のものがある。（強調追加 p. 3）」

もちろん、アルゴリズムと計算可能な関数の概念は密接に関連しています。定義上、計算可能な関数とは、アルゴリズムによって計算可能な関数のことです。（4ページ）

BlassとGurevich（2002）は、「Quisani」（「Q」）と「著者」（A）との対話を提起し、Yiannis Moshovakisを対照的な人物として用いて、率直にこう述べている。

「A:意見の相違点を明確にするために、まず合意点を2つ挙げましょう。第一に、チューリングマシン、逐次時間ASM（抽象状態機械）など、誰の定義でも明らかにアルゴリズムであるものがあります。…第二に、その反対の極端な例として、計算方法を一切示さないため、誰の定義でもアルゴリズムとはみなされない仕様があります。…問題は、アルゴリズムとみなされるために、情報がどの程度詳細でなければならないかということです。…モショバキスは、私たちが宣言的仕様と呼ぶものも認めており、私たちがアルゴリズムと呼ぶものに対してはおそらく「実装」という言葉を使うでしょう。」（読みやすさのために段落を連結、2002年：22）

この「実装」という言葉の使い方は、問題の本質を的確に捉えている。論文の冒頭で、Qはモショバキスの解釈について次のように述べている。

「…おそらく彼は、あなたの実務（グレヴィッチはマイクロソフトに勤務している）によって、アルゴリズムよりも実装について考えることを余儀なくされていると考えているでしょう。彼は実装を機械と同一視することには全く抵抗がありませんが、アルゴリズムはもっと一般的なものだと言います。要するに、あなたはアルゴリズムを機械だと言い、モスコヴァキスはそうではないと言うということです。」(2002:3)

しかし、著者らはここで曖昧な表現を用い、「アルゴリズム」と「マシン」に絞って説明し、読者は再び混乱させられる。以下の脚注コメントは、ダーショウィッツとグレヴィッチによる2007年の研究まで待たなければならない。

「…しかし、モショヴァキスの見解を受け入れるならば、我々が特徴づけようとしたのはアルゴリズムの「実装」である。」(脚注9 2007:6参照)

ブラスとグレヴィッチは、自分たちの研究はチューリングマシンとポインターマシン、特にコルモゴロフ＝ウスペンスキーマシン（KUマシン）、シェーンハーゲ記憶変更マシン（SMM）、そしてクヌースによって定義された連結オートマトンに関する考察から発展したものであると述べている。ガンディとマルコフの研究もまた、影響力のある先駆者として挙げられている。

グレヴィッチはアルゴリズムの「強力な」定義を提示している（太字は筆者による）：

「…チューリングの非公式な議論は、彼のテーゼを支持するより強力なテーゼを正当化する。すなわち、あらゆるアルゴリズムはチューリングマシンによってシミュレートできるというテーゼである。…実際には、それはばかげているだろう…[しかしながら、] []チューリングマシンを一般化して、どんなに抽象的なアルゴリズムでも、一般化されたマシンによってモデル化できるだろうか？…しかし、そのような一般化されたチューリングマシンが存在すると仮定しよう。それらの状態はどのようなものだろうか？…一階構造…特定の小さな命令セットですべての場合に十分…計算は状態の進化として…非決定論的である可能性がある…環境と相互作用できる…[並列かつマルチエージェントである可能性がある]… [動的意味論を持つ可能性がある]…[彼らの研究の2つの基礎は、]チューリングのテーゼ…[と][タルスキー 1933]の（一階）構造の概念である」(グレヴィッチ 2000、1-2ページ)

上記の「状態の進化としての計算」という表現は、クヌースとストーンの定義、すなわちチューリングマシンプログラムとしての「アルゴリズム」とは大きく異なります。むしろ、それはチューリングが完全構成と呼んだもの（チューリングの『決定不能』118ページにおける定義を参照 ）に対応し、現在の命令（状態）とテープの状態の両方を含みます。[クリーネ（1952） 375ページを参照。彼は6つのシンボルが書かれたテープ（他のマスはすべて空白）の例と、そのテーブルとテープの状態をゲーデル化する方法を示しています]。 

アルゴリズムの例では、状態の変化を直接見ることができます。

哲学者ダニエル・デネットは、 1995年の著書『ダーウィンの危険な思想』の中で、進化をアルゴリズム的プロセスとして捉えることの重要性を分析している。デネットは、アルゴリズムの3つの重要な特徴を挙げている。

• 基質中立性：アルゴリズムはその論理 構造に依存する。したがって、アルゴリズムがどのような形式で表現されるかは重要ではない（デネットの例は長除法である。長除法は紙でも羊皮紙でも、コンピュータ画面でも、ネオンライトでもスカイライティングでも同様に機能する）。（ 51ページ）
• 根底にあるのは無意識性：アルゴリズム処理の最終成果物がどれほど複雑であっても、アルゴリズムの各ステップは、知覚を持たない機械装置でも実行できるほど十分に単純である。アルゴリズムは、維持や操作に「脳」を必要としない。「標準的な教科書のアナロジーでは、アルゴリズムは一種のレシピであり、料理初心者でも従えるように設計されていると述べられている。」(p.  51)
• 結果の保証：アルゴリズムが正しく実行されれば、常に同じ結果が得られます。「アルゴリズムは失敗のないレシピである。」（ 51ページ）

デネットはこの分析に基づいて、「ダーウィンによれば、進化はアルゴリズム的なプロセスである」と結論付けている（ 60ページ）。

しかし、前のページで彼はさらに大胆な主張を展開している。「アルゴリズムとしてのプロセス」と題された章の中で、彼は次のように述べている。

「しかし、では、アルゴリズム的プロセスとみなせるものに何らかの制限はあるのでしょうか？おそらく答えはノーでしょう。もし望むなら、抽象的なレベルではどんなプロセスでもアルゴリズム的プロセスとして扱うことができます。…もしあなたが不思議に思うのが、海の砂粒の均一性や焼き入れ鋼の刃の強度であるなら、アルゴリズム的な説明があなたの好奇心を満たしてくれるでしょう。そしてそれは真実です。…」

「アルゴリズムの成果物がどれほど印象的であっても、その根底にあるプロセスは常に、知的な監視の助けなしに次々と続く、個々に無思慮な一連のステップから成り立っているに過ぎない。それらは定義上『自動的』であり、オートマトンの動作そのものである。」(59ページ)

上記からは、デネットが、物理世界はそれ自体で、観察者なしでは本質的にアルゴリズム的（計算的）であると述べているのか、それとも記号処理を行う観察者が観察に「意味」を付加しているのだと述べているのかは明らかではない。

ダニエル・デネットは、強力な人工知能の提唱者であり、アルゴリズムの論理構造だけで心を説明するのに十分だという考えを主張している。中国語の部屋思考実験の考案者であるジョン・サールは、「構文（つまり論理構造）だけでは意味内容（つまり意味）を説明するには不十分である」と主張している（サール 2002 、p. 16）。言い換えれば、記号の「意味」は、それを使用する心によって相対的なものであり、アルゴリズム（論理的な構成要素）だけでは心を説明するには不十分なのである。 

サールは、アルゴリズム的（計算的）プロセスが自然に内在すると主張する人々（例えば、宇宙論者、物理学者、化学者など）に警告を発している。

計算は観察者相対的なものであり、これは計算が記号操作によって定義されるものの、「記号」という概念は物理学や化学の概念ではないためです。何かが記号であるのは、それが記号として使用され、扱われ、またはみなされる場合のみです。中国語の部屋の議論は、意味論が構文に内在するものではないことを示しました。しかし、これは構文が物理学に内在するものではないことを示しています。[...]何かが記号であるのは、それに記号的解釈を割り当てる観察者、使用者、またはエージェントに相対する場合のみです。[...]何にでも計算的解釈を割り当てることができます。しかし、「意識は本質的に計算的か？」という質問であれば、答えは「本質的に計算的なものは何もない」です（強調のためにイタリック体を追加）。計算は、何らかの現象に計算的解釈を課すエージェントまたは観察者に相対する場合にのみ存在します。これは明白な点です。10年前に気づくべきでしたが、気づきませんでした。

この仕様方法が加算アルゴリズム「m+n」に適用された例については、「アルゴリズムの例」を参照してください。

Boolos-Burgess-Jeffrey (2002) (31-32ページ) の例は、 アルゴリズムの完全な仕様に必要な精度を示しています。この例では、m+n という 2 つの数値を加算します。これは、上記の Stone の要件と似ています。

（i）彼らは計算における「数値形式」の役割について議論し、数値を表すために「集計表記」を選択した。

「確かに、計算は表記法によっては実際的に難しい場合があるが、…原理的には、データを変換するだけで他の表記法でも計算は可能である。…厳密に定義された計算可能性の概念を構築する目的では、単項表記法またはタリー表記法を使用するのが便利である。」(p. 25-26)

（ii）例の冒頭で、計算に使用するマシンをチューリングマシンと指定している。 チューリングマシンは5タプルではなく4タプルであると、すでに（26ページで）指定している。この慣例の詳細については、「チューリングマシン」を参照のこと。

（iii）著者らは既に、テープヘッドの位置はスキャンされたシンボルの右側の添え字で示されると規定している。この慣例の詳細については、「チューリングマシン」を参照のこと。（以下、強調のため太字を使用）

「チューリングマシンで計算可能な数値関数とは何か、入力や引数をマシン上でどのように表現するか、出力や値をどのように表現するかといった公式な定義は、これまで示してきませんでした。正の整数から正の整数へのk桁関数の仕様は以下のとおりです。」

(a) [初期数値形式: ] 引数 m ₁、... m _k、... は、単項表記で、それらのストローク数のブロックによって表され、各ブロックは、それ以外は空白のテープ上に単一の空白で区切られます。

例：3+2、111B11

(b) [初期ヘッド位置、初期状態: ] 最初は、機械はテープの左端の1をスキャンしており、初期状態である状態1にあります。

例：3+2、1 ₁ 111B11

(c) [計算成功 - 停止時の数値形式: ] 計算対象の関数が、テープ上に最初に表現される引数に値 n を割り当てる場合、マシンは最終的にストロークのブロックを含むテープ上で停止し、そうでない場合は空白のテープ上で停止します...

例：3+2、11111

(d) [計算成功 - 停止時のヘッド位置: ] この場合[c]、機械はテープ上の左端の1のスキャンを停止します...

例: 3+2, 1 _n 1111

「(e) [計算の失敗 - 停止の失敗または非標準の数値形式での停止: ] 計算対象の関数が、テープ上に最初に表現された引数に値を割り当てない場合、マシンは決して停止しないか、または何らかの非標準構成で停止します...」(同上)

例: B _n 11111 または B11 _n 111 または B11111 _n

この仕様は不完全です。命令を配置する場所と、機械内での命令のフォーマットが必要です。

（iv）有限状態機械のテーブル、またはテープ上のユニバーサルチューリングマシンの場合は、

（v）指定された形式の指示表

この後者の点は重要です。Boolos-Burgess-Jeffreyは、 表のエントリの予測可能性により、エントリを順番に配置し、入力状態とシンボルを省略することで表を「縮小」できることを実証しています（36ページ）。実際、チューリングマシンの計算例では、以下の表に示すように4つの列のみが必要でした（ただし、これらは行としてマシンに提示されたことに注意してください）。

この仕様方法が加算アルゴリズム「m+n」に適用された例については、「アルゴリズムの例」を参照してください。

Sipserはまず、「アルゴリズム」を次のように定義する。

「非公式に言えば、アルゴリズムとは、何らかの作業を実行するための単純な手順の集合体である。日常生活ではごく一般的なアルゴリズムは、手順やレシピと呼ばれることもある（原文ではイタリック体、154ページ）」

「…これからの私たちの真の焦点はアルゴリズムにあります。つまり、チューリングマシンはアルゴリズムの定義のための正確なモデルとしてのみ機能します。…私たちは、チューリングマシンがすべてのアルゴリズムを捉えていると信じるのに十分なほど、チューリングマシンに慣れ親しむだけでよいのです。」(156ページ)

Sipserは「アルゴリズム」とはチューリングマシンの「命令」に過ぎないという意味なのか、それとも「命令＋（特定の種類の）チューリングマシン」の組み合わせという意味なのか。例えば、彼は自身の特定のバージョン（チューリングのオリジナルとは異なる）の2つの標準的なバージョン（マルチテープと非決定性）を定義し、さらに「問題」（160～161ページ）で4つのバージョン（一度書き込み、二重無限テープ（つまり左無限と右無限）、左リセット、および「左ではなくその場にとどまる」）について説明している。さらに、彼はいくつかの制約を課している。まず、入力は文字列としてエンコードされなければならない（157ページ）とし、複雑性理論の文脈における数値エンコードについて次のように述べている。

「しかし、数値を符号化するための単項表記（例えば、数値17を単項数111111111111111111で符号化するなど）は、k ≥ 2 の任意の値に対する基数k表記など、真に妥当な符号化方法よりも指数関数的に大きくなるため、妥当ではないことに注意してください。」(p. 259)

ヴァン・エムデ・ボアスは、「アルゴリズムの分析」を行う際にチューリングマシンの代わりに使われることがあるランダムアクセスマシン（RAM）の抽象計算モデルに関して、同様の問題について次のように述べています。「乗算および並列ビット操作操作の有無は、アルゴリズムの分析におけるいくつかの結果を正しく理解する上で重要です。」

「…均一な時間測定において、標準RAMモデルの『無害な』拡張などというものはほとんど存在しない。加算演算のみを扱うか、あるいは小さなオペランドに対するすべての妥当な乗算命令および／またはビット単位のブール命令を含めるかのどちらかである。」(Van Emde Boas、1990:26)

アルゴリズムの「記述言語」に関して、シプサーはストーンとブーロス＝バージェス＝ジェフリーが始めた仕事を完成させた（太字は筆者による）。彼はチューリングマシンアルゴリズムの記述を3つのレベルで提示している（ 157ページ）。

高レベルの説明：「ここでは、実装の詳細を無視して、散文を用いてアルゴリズムを説明します。このレベルでは、マシンがテープやヘッドをどのように管理するかについて言及する必要はありません。」

実装の説明：「ここでは、チューリングマシンがヘッドを動かす方法と、テープにデータを格納する方法を散文で説明します。このレベルでは、状態や遷移関数の詳細は説明しません。」

形式的記述：「…最も低く、最も詳細なレベルの記述であり、チューリングマシンの状態、遷移関数などを完全に記述する。」

ヤノフスキー（2011）^{[ 3 ]}では、アルゴリズムは、そのアルゴリズムを実装するプログラムの集合として定義されています。すべてのプログラムの集合は同値類に分割されます。プログラムの集合はカテゴリを形成しませんが、アルゴリズムの集合は追加の構造を持つカテゴリを形成します。2つのプログラムが同値である条件は、アルゴリズムのカテゴリに追加の構造を与える整合性関係であることがわかります。

Seiller (2024) ^{[ 4 ]}では、アルゴリズムはエッジラベル付きグラフとして定義され、ラベルは抽象データ構造内のマップとして解釈されます。この定義は、プログラム（および計算モデル）の形式的な定義とともに与えられ、プログラムがアルゴリズムを実装する、つまり実装の概念を形式的に定義することができます。このようにして得られたアルゴリズムの概念は、いくつかの既知の問題を回避し、何らかの仕様として理解されます。特に、特定のプログラムは複数のアルゴリズムを実装することができ（そして実際、常に実装しています）、このアプローチのもう 1 つの重要な特徴は、特定のアルゴリズムが異なる（そしておそらく無関係な）計算モデルで実装できるという事実を考慮に入れていることです。

• デイビッド・ベルリンスキー(2000) 『アルゴリズムの出現：アイデアからコンピュータへの300年の旅』ハーコート社、サンディエゴ、ISBN 0-15-601391-6（ペーパーバック）
• ジョージ・ブーロス、ジョン・P・バージェス、リチャード・ジェフリー（2002）、『計算可能性と論理：第4版』、ケンブリッジ大学出版局、ケンブリッジ、英国。ISBN 0-521-00758-5（ペーパーバック）
• Andreas BlassおよびYuri Gurevich (2003)、「アルゴリズム：絶対的な定義を求めて」、欧州理論計算機科学協会紀要 81、2003 年。56 件の参考文献を含む優れた文献目録が含まれています。
• Burgin, M. 『超再帰アルゴリズム』、コンピュータサイエンスモノグラフ、Springer、2005年。ISBN 0-387-95569-0
• デイビス、マーティン（1958）。計算可能性と解決不可能性。ニューヨーク：マグロウヒル・ブック・カンパニー。重要な定義と、いくつかの再帰関数に対するチューリングマシンベースのアルゴリズムの出典。
• デイビス、マーティン（1965）。決定不能なもの：決定不能な命題、解決不能な問題、計算可能な関数に関する基礎論文。ニューヨーク：レイヴン・プレス。デイビスは各論文の前に解説を加えている。ゲーデル、アロンゾ・チャーチ、チューリング、ロッサー、クリーネ、エミール・ポストの論文が収録されている。
• デネット、ダニエル（1995）。ダーウィンの危険な思想。ニューヨーク：タッチストーン／サイモン＆シュスター。
• ガンディ、ロビン、「チャーチのテーゼとメカニズムの原理」、J. バーワイズ、HJ ケイスラー、K. クーネン編、『クリーネ・シンポジウム』、ノースホランド出版、1980 年、 123～148 ページ。ガンディの有名な「[計算]メカニズムの 4 つの原理」には、「原理 IV - 局所的因果律の原理」が含まれています。
• Gurevich, Yuri、「逐次抽象状態機械による逐次アルゴリズムの捕捉」、ACM Transactions on Computational Logic、第1巻、第1号（2000年7月）、77～111ページ。33件の参考文献リストを含む。
• Kleene C., Stephen (1943). "再帰述語と量化子" .アメリカ数学会紀要. 54 (1): 41– 73. doi : 10.2307/1990131 . JSTOR 1990131 . 『決定不能』 255ページ以降に再録 。クリーネは「一般再帰」の定義を洗練し、第12章「アルゴリズム理論」で「テーゼI」（274ページ）を提唱した。彼は後にこのテーゼを繰り返し（クリーネ1952:300）、それを「チャーチのテーゼ」（クリーネ1952:317）（つまり、チャーチのテーゼ ）と名付けた。
• クリーネ、スティーブン C. (1991) [1952].メタ数学入門（第10 版）. ノースホランド出版.数学の「基礎」を学ぶための、優れた――分かりやすく読みやすい――参考資料。
• Knuth, Donald E. (1973) [1968].コンピュータプログラミングの技法 第2版、第1巻/基本アルゴリズム(第2 版)。Addison-Wesley Publishing Company。クヌースの有名な三部作の最初の著作。
• Lewis, HRおよびPapadimitriou, CH 『計算理論の要素』、Prentice-Hall、Uppre Saddle River、NJ、1998年
• A.A.マルコフ（1954）アルゴリズムの理論。[ジャック・J・ショール＝コンおよびPSTスタッフによる翻訳] 発行元：モスクワ、ソ連科学アカデミー、1954年 [すなわち、エルサレム、イスラエル科学翻訳プログラム、1961年；米国商務省技術サービス局（ワシントン）より入手可能] 内容：444ページ、 28cm  。ソ連科学アカデミー数学研究所著作集ロシア語翻訳版第42巻に追加されたtp。原題：Teoriya algerifmov。[QA248.M2943 ダートマス大学図書館。米国商務省技術サービス局、番号OTS 60–51085。]
• ミンスキー、マービン（1967）。計算：有限マシンと無限マシン（初版 ）。プレンティス・ホール、ニュージャージー州エングルウッド・クリフス。ミンスキーは、第 5.1計算可能性、有効な手順、アルゴリズム、無限の機械で、彼の「アルゴリズム、つまり有効な手順の概念」を拡張しています。
• ロジャース、ハートリー・ジュニア、（1967）、『再帰関数と有効計算可能性の理論』、MIT Press（1987）、マサチューセッツ州ケンブリッジ、ISBN 0-262-68052-1（ペーパーバック）
• サール、ジョン（2002）。意識と言語。ケンブリッジ（英国）：ケンブリッジ大学出版局。ISBN 0-521-59744-7。
• Seiller, Thomas , (2024),数理情報学, ハビリテーション論文, ソルボンヌ大学パリ北校,。
• Sipser, Michael (2006)、『計算理論入門：第2版』、Thompson Course Technology div. of Thompson Learning, Inc.、ボストン、マサチューセッツ州。ISBN 978-0-534-95097-2。
• Soare, Robert、(1995 年、第 10 回国際論理学、方法論、科学哲学会議の議事録、1995 年 8 月 19 ～ 25 日、イタリア、フィレンツェ) に掲載予定、Computability and Recursion )、ウェブ上 ??。
• イアン・スチュワート著、『アルゴリズム』、ブリタニカ百科事典、2006年。
• ストーン、ハロルド・S. 『コンピュータ構成とデータ構造入門』（1972年 版）。マグロウヒル、ニューヨーク。特に「アルゴリズム、チューリングマシン、プログラム」と題された第1章を参照されたい。彼の簡潔で非公式な定義は、「ロボットが従うことができる一連の命令は、アルゴリズムと呼ばれる」（4ページ ）である。
• ファン・エムデ・ボアス、ピーター（1990）、「機械モデルとシミュレーション」、3～66ページ、ヤン・ファン・レーウェン（1990）、「理論計算機科学ハンドブック 第A巻：アルゴリズムと複雑性」、MIT Press/Elsevier、1990年、ISBNに掲載。 0-444-88071-2（A巻）