Loading article…
計算とは、明確に定義されたあらゆる種類の算術計算または非算術計算です。 [1] [2]計算の一般的な例としては、数式を解くことやコンピュータアルゴリズムの実行などがあります。
計算を実行する機械的または電子的な装置（または歴史的には人）は、コンピュータとして知られています。
コンピュータサイエンスは計算の研究を含む学問分野です。
導入
数学的記述は「明確に定義される」べきであるという概念は、少なくとも1600年代から数学者によって議論されてきたが[3]、適切な定義についての合意はなかなか得られなかった。[4]候補となる定義は、1930年代に数人の数学者によって独立に提案された。[5]最もよく知られている変種は数学者アラン・チューリングによって形式化されたもので、チューリングマシンの初期化パラメータで表現できる任意の記述として明確に定義された記述または計算が定義された。[6]その他の（数学的に同等の）定義には、アロンゾ・チャーチのラムダ定義可能性、ヘルブラント・ゲーデル・クリーネの一般再帰性、エミール・ポストの1定義可能性などがある。[5]
今日では、この明確な定義を示す形式的なステートメントや計算は「計算可能」と呼ばれ、ステートメントや計算自体は「計算」と呼ばれます。
チューリングの定義は、すべての整形式の代数文と現代のコンピュータプログラミング言語で書かれたすべての文を含む、非常に大規模な数学的文のクラスに「明確さ」を割り当てました。 [7]
この定義は広く受け入れられているが、この定義では明確に特徴づけられない数学的概念もいくつかある。これには停止問題やビジービーバーゲームが含まれる。計算可能なステートメントと計算不可能なステートメントの両方を捉えることができる、より強力な「明確に定義された」定義が存在するかどうかは未解決の問題である。[注 1] [8]
計算可能な数学的記述の例には次のものがあります。
- C++、Python、Javaなどの現代のプログラミング言語で特徴付けられるすべてのステートメント。[7]
- 電子計算機、電卓、そろばんなどによって行われるすべての計算。
- すべての計算は解析エンジンで実行されます。
- すべての計算はチューリングマシンで実行されます。
- 数学の教科書に記載されている数学的な記述と計算の大部分。
計算できない数学的記述の例には次のものがあります。
- 計算またはステートメントが不明確であるため、チューリング マシンに明確にエンコードすることはできません (「ポールはジョーの 2 倍私を愛しています」)。
- 問題文は明確に定義されているように見えますが、それを解決するためのチューリング マシンが存在しないことが証明できます (停止問題など)。
計算の物理的プロセス
計算は、コンピュータと呼ばれる閉じた物理システム内で行われる純粋に物理的なプロセスと見ることができます。チューリングの 1937 年の証明、「計算可能数とその計算問題への応用」は、計算可能なステートメントと、一般にコンピュータと呼ばれる特定の物理システムとの間に形式的な等価性があることを示しました。このような物理システムの例としては、チューリング マシン、厳格な規則に従う人間の数学者、デジタル コンピュータ、機械式コンピュータ、アナログ コンピュータなど があります。
計算の代替説明
マッピングアカウント
ヒラリー・パトナムらの著作には、計算に関する別の説明が数多く見られる。ピーター・ゴッドフリー＝スミスはこれを「単純マッピング説明」と名付けた。[9] グアルティエロ・ピッチニーニによるこの説明の要約では、物理システムが特定の計算を実行するのは、そのシステムの状態と計算との間にマッピングがあり、「[システムの]ミクロ物理的状態が計算状態間の状態遷移を反映する」場合である、としている。[10]
意味論的説明
ジェリー・フォーダー[11]などの哲学者は、意味内容が計算の必要条件であるという制限を課した計算のさまざまな説明を提案してきました（つまり、任意の物理システムと計算システムを区別するのは、計算のオペランドが何かを表現しているかどうかです）。この概念は、すべてのものがすべてを計算していると言えるという考えである 汎計算主義のマッピング説明の論理的抽象化を防ごうとしています。
機械論的説明
グアルティエロ・ピチニーニは、機械哲学に基づく計算の説明を提唱している。それによれば、物理的計算システムは、設計上、物理的計算、または「媒体に依存しない」乗り物を規則に従って（機能的メカニズムによって）操作するメカニズムの一種である。「媒体に依存しない」ためには、その特性が複数の実現者（説明が必要）と複数のメカニズムによってインスタンス化（説明が必要）でき、メカニズムの入力と出力も複数回実現可能であることが必要である。つまり、媒体に依存しないということは、電圧以外の特性を持つ物理的変数の使用を可能にする（一般的なデジタルコンピューターの場合のように）。これは、脳や量子コンピューターで行われる計算など、他の種類の計算を検討する上で不可欠である。この意味で、規則は、物理的計算システムの入力、出力、および内部状態間のマッピングを提供する。[12]
数学モデル
計算理論では、さまざまな計算の数学的モデルが開発されてきました。代表的なコンピュータの数学的モデルは次のとおりです。
- チューリングマシン、プッシュダウンオートマトン、有限状態オートマトン、PRAMなどの状態モデル
- ラムダ計算を含む関数モデル
- 論理プログラミングを含む論理モデル
- アクターモデルとプロセス計算を含む並行モデル
ジュンティは計算理論によって研究されるモデルを計算システムと呼び、それらはすべて離散時間と離散状態空間を持つ数学的動的システムであると主張している。[ 13] : ch.1 彼は、計算システムは3つの部分からなる複雑なオブジェクトであると主張している。第1に、離散時間と離散状態空間を持つ数学的動的システム。第2に、理論部分と実部分からなる計算セットアップ。第3に、動的システムとセットアップをリンクする解釈。[14] : pp.179–80
参照
注記
- ^計算不可能なステートメントの研究は ハイパーコンピューティングの分野です。
参考文献
- ^ 「COMPUTATIONの定義」www.merriam-webster.com 2024-10-11 2024-10-12閲覧。
- ^ 「Computation: Definition and Synonyms from Answers.com」。Answers.com 。 2009年2月22日時点のオリジナルよりアーカイブ。2017年4月26日閲覧。
- ^ ルイ・クーチュラ (1901)。la Logique de Leibniz a'Après des Document Inédits。パリ。ISBN 978-0343895099。
- ^ デイビス、マーティン; デイビス、マーティン D. (2000)。ユニバーサルコンピュータ。WW ノートン アンド カンパニー。ISBN 978-0-393-04785-1。
- ^ ab デイビス、マーティン (1982-01-01)。計算可能性と解決不可能性。クーリエコーポレーション。ISBN 978-0-486-61471-7。
- ^ Turing, AM (1937) [1936年11月に学会に提出]. 「計算可能数について、その計算問題への応用」(PDF) .ロンドン数学会の議事録. 2. 第42巻. pp. 230–65. doi :10.1112/plms/s2-42.1.230.
- ^ ab デイビス、マーティン; デイビス、マーティン D. (2000)。ユニバーサルコンピュータ。WW ノートン アンド カンパニー。ISBN 978-0-393-04785-1。
- ^ Davis, Martin (2006). 「なぜハイパーコンピューティングという分野が存在しないのか」.応用数学と計算. 178 (1): 4–7. doi :10.1016/j.amc.2005.09.066.
- ^ ゴッドフリー・スミス、P.（2009）、「機能主義に対する瑣末な議論」、哲学研究、145（2）：273–95、doi：10.1007 / s11098-008-9231-3、S2CID 73619367
- ^ ピチニーニ、グアルティエロ (2015)。『物理計算：機械論的説明』オックスフォード：オックスフォード大学出版局。p. 18。ISBN 9780199658855。
- ^ フォダー、JA (1986)、「心身の問題」、サイエンティフィック・アメリカン、244 (1986年1月)
- ^ ピチニーニ、グアルティエロ (2015)。『物理計算：機械論的説明』オックスフォード：オックスフォード大学出版局。p. 10。ISBN 9780199658855。
- ^ Giunti, Marco (1997).計算、ダイナミクス、認知。ニューヨーク: Oxford University Press。ISBN 978-0-19-509009-3。
- ^ ジュンティ、マルコ（2017）、「計算システムの物理的実現とは何か？」、イソノミア-エピステモロジカ、9：177-92、ISSN 2037-4348