計算

計算とは、明確に定義されたあらゆる種類の算術計算または非算術計算です。 [ 1 ] [ 2 ]計算の一般的な例としては、数式を解くことやコンピュータアルゴリズムの実行などがあります。

計算を実行する機械的または電子的な装置（あるいは歴史的には人間）はコンピュータと呼ばれます。コンピュータサイエンスは、計算を研究する学問分野です。

導入

数学的記述は「明確に定義される」べきであるという概念は、少なくとも1600年代から数学者によって議論されてきたが[ 3 ]、適切な定義についての合意はなかなか得られなかった。[ 4 ]候補となる定義は、1930年代に数人の数学者によって独立に提案された。[ 5 ]最もよく知られた変種は数学者アラン・チューリングによって形式化され、チューリングマシンの初期化パラメータで表現できる任意の記述として明確に定義された。[ 6 ]その他の（数学的に同等の）定義には、アロンゾ・チャーチのラムダ定義可能性、ヘルブランド・ゲーデル・クリーネの一般再帰性、エミール・ポストの1定義可能性などがある。[ 5 ]

今日では、この明確な定義の特性を示す正式なステートメントや計算は「計算可能」と呼ばれ、ステートメントや計算自体は「計算」と呼ばれます。

チューリングの定義は、すべての整形式の代数的ステートメントと現代のコンピュータプログラミング言語で書かれたすべてのステートメントを含む、非常に大規模な数学的ステートメントのクラスに「明確さ」を割り当てました。 [ 7 ]

この定義は広く受け入れられているにもかかわらず、この定義の下では明確に特徴づけられない数学概念もいくつか存在します。これには停止問題やビジービーバーゲームが含まれます。計算可能な命題と計算不可能な命題の両方を包含できる、より強力な「明確に定義された」定義が存在するかどうかは、依然として未解決の問題です。[注 1 ] [ 8 ]

計算可能な数学的記述の例には次のものがあります。

計算できない数学的記述の例には次のようなものがあります。

  • 計算や文が明確に定義されていないため、チューリング マシンに明確にエンコードすることができません (「ポールはジョーの 2 倍私を愛している」など)。
  • 明確に定義されているように見えるが、それを解くチューリングマシンが存在しないことが証明できる問題ステートメント（停止問題など）

計算は、コンピュータと呼ばれる閉じた物理システム内で行われる純粋に物理的なプロセスと見なすことができます。チューリングが1937年に発表した『計算可能数とその計算問題への応用』は、計算可能な文と、一般的にコンピュータと呼ばれる特定の物理システムとの間に形式的な等価性があることを示しました。このような物理システムの例としては、チューリングマシン、厳格な規則に従う人間の数学者、デジタルコンピュータ、機械式コンピュータ、アナログコンピュータなどが挙げられます。

計算の代替的な説明

マッピングアカウント

ヒラリー・パトナムらの著作には、計算に関する別の説明が数多く見られる。ピーター・ゴッドフリー＝スミスはこれを「単純写像説明」と名付けた[ 9 ] 。グアルティエロ・ピッチニーニはこの説明を要約し、物理系が特定の計算を実行するのは、その系の状態と計算の間に写像が存在し、「（系の）微視的物理的状態が計算状態間の状態遷移を反映する」場合である、と述べている[ 10 ] 。

意味論的説明

ジェリー・フォーダー[ 11 ]などの哲学者は、意味内容が計算の必要条件であるという制約の下で、計算に関する様々な説明を提唱してきた（つまり、任意の物理システムと計算システムを区別するのは、計算のオペランドが何かを表現しているかどうかである）。この概念は、汎計算主義の写像的説明、すなわちあらゆるものがあらゆるものを計算しているという考え方を論理的に抽象化することを防ごうとしている。

機械論的説明

グアルティエロ・ピッチニーニは、機械哲学に基づく計算の説明を提唱している。彼は、物理計算システムとは、設計上、物理計算、すなわち「媒体非依存」な乗り物を規則に従って（機能的メカニズムによって）操作するメカニズムの一種であると述べている。「媒体非依存」とは、特性が複数の実現者と複数のメカニズムによって具体化できること、そしてメカニズムの入力と出力も多重に実現可能であることを要求する。つまり、媒体非依存は、電圧以外の特性を持つ物理変数（典型的なデジタルコンピュータの場合）の使用を可能にする。これは、脳や量子コンピュータで行われるような他の種類の計算を考える上で不可欠である。この意味での規則は、物理計算システムの入力、出力、および内部状態間のマッピングを提供する。[ 12 ]

数学モデル

計算理論においては、多様な計算の数学的モデルが開発されてきました。代表的なコンピュータの数学的モデルは以下のとおりです。

ジュンティは計算理論によって研究されるモデルを計算システムと呼び、それらはすべて離散時間と離散状態空間を持つ数学的動的システムであると主張する。 [ 13 ]：ch.1 彼は、計算システムは3つの部分からなる複雑なオブジェクトであると主張する。第1に、離散時間と離散状態空間を持つ数学的動的システム、第2に、理論部分と実部分からなる計算セットアップ、第3に、動的システムとセットアップを結び付ける解釈である。[ 14 ]：pp.179–80 DS{\displaystyle DS}H＝（F、BF）{\displaystyle H=\left(F,B_{F}\right)}F{\displaystyle F}BF{\displaystyle B_{F}}私DS、H{\displaystyle I_{DS,H}}DS{\displaystyle DS}H{\displaystyle H}

参照

注記

参考文献

  1. ^ 「COMPUTATIONの定義」 www.merriam-webster.com 2024年10月11日2024年10月12日閲覧。
  2. ^ 「Computation: Definition and Synonyms from Answers.com」 . Answers.com . 2009年2月22日時点のオリジナルよりアーカイブ。2017年4月26日閲覧。
  3. ^ルイ・クーチュラ (1901)。la Logique de Leibniz a'Après des Document Inédits。パリ。ISBN 978-0343895099。{{cite book}}:ISBN / 日付の非互換性（ヘルプ）
  4. ^デイビス、マーティン; デイビス、マーティンD. (2000). 『ユニバーサルコンピュータ』 . WW Norton & Company. ISBN 978-0-393-04785-1。
  5. ^ a bデイビス、マーティン (1982-01-01).計算可能性と非解決可能性. クーリエコーポレーション. ISBN 978-0-486-61471-7。
  6. ^チューリング, AM (1937) [1936年11月学会発表]. 「計算可能数について、そして計算問題への応用」(PDF) .ロンドン数学会報. 第2巻. 第42巻. pp.  230–65 . doi : 10.1112/plms/s2-42.1.230 .
  7. ^ a bデイビス、マーティン; デイビス、マーティンD. (2000). 『ユニバーサルコンピュータ』 . WW Norton & Company. ISBN 978-0-393-04785-1。
  8. ^デイビス、マーティン (2006). 「なぜハイパーコンピューティングという分野が存在しないのか」.応用数学と計算. 178 (1): 4– 7. doi : 10.1016/j.amc.2005.09.066 .
  9. ^ゴッドフリー＝スミス、P.（2009）「機能主義に対する瑣末な議論」、哲学研究、145（2）：273-95、doi：10.1007/s11098-008-9231-3、S2CID 73619367 
  10. ^ピチニーニ、グアルティエロ (2015). 『物理計算：機械論的説明』オックスフォード：オックスフォード大学出版局. p. 18. ISBN 9780199658855。
  11. ^ Fodor, JA (1986)、「心身の問題」、Scientific American、244 (1986年1月)
  12. ^ピチニーニ、グアルティエロ (2015). 『物理計算：機械論的説明』オックスフォード：オックスフォード大学出版局. p. 10. ISBN 9780199658855。
  13. ^ジュンティ、マルコ（1997年）『計算、ダイナミクス、認知』ニューヨーク：オックスフォード大学出版局、ISBN 978-0-19-509009-3。
  14. ^ジュンティ、マルコ（2017）「計算システムの物理的実現とは何か？」イソノミア-エピステモロジカ、9：177-92、ISSN 2037-4348 
「 https://en.wikipedia.org/w/index.php?title=Computation&oldid=1328386350」より取得