計算上の不可分性

計算の既約性は、特定の計算プロセスは単純化できず、その結果を判断する唯一の方法は、計算の各ステップを実行することであるということを意味します。これは、スティーブン・ウルフラムが2002 年の著書「A New Kind of Science」で提唱した主要なアイデアの 1 つですが、この概念は 1980 年代の研究にまで遡ります。

多くの物理システムは複雑すぎて、効果的に測定することができません。より単純なプログラムでさえ、非常に多様な動作が含まれます。したがって、実験を行う前に、初期条件のみを使用して、特定の物理システムで何が起こるかを正確に予測できるモデルはありません。計算の形式言語におけるこの決定不能性の問題があることから、Wolfram は、システム(または「プログラム」) を「ショートカット」できないこと、またはその動作を簡単な方法で説明できないことを「計算の既約性」と呼んでいます。この考え方は、理論の予測が事実上不可能な状況が発生することを示しています。Wolfram は、いくつかの現象は通常は計算の既約性がないと述べています^[要出典]。

計算の不可逆性は、多くの自然システムを予測またはシミュレートするのが難しい理由を説明します。計算等価性の原理は、これらのシステムが設計されたコンピュータと同等の計算能力を持っていることを意味します。

• 複雑に見える行動には、簡単な理論は存在しません。
• 複雑な動作特性は、単純な基礎構造を持つモデルで捉えることができます。
• 単純な構造に基づくシステム全体の動作は、それでも、合理的に「単純な」法則では説明できない動作を示すことがあります。

Navot Israeli と Nigel Goldenfeld は、それほど複雑でないシステムの中には、単純かつ予測可能な動作をするものがある (したがって、近似値が可能) ことを発見しました。しかし、より複雑なシステムは、依然として計算上は不可能で予測不可能でした。複雑な現象を単純かつ予測可能な形で記述できる条件が何であるかは不明です。

Marius Krumm と Markus P Muller は、計算の非還元性を両立主義に結び付けています。^[1]彼らは、計算の源泉性と呼ばれる新しい概念の中間要件を介して概念を洗練しています。この概念は、表現される問題またはプロセスに関連する特徴の本質的に完全かつほぼ正確な表現と、完全な近道のない計算を必要とします。このアプローチは、近道のないメタファーを介して問題の概念化を簡素化します。これは、望ましい最終製品を得るために、レシピのすべての材料が必要であり、「調理スケジュール」に従う必要がある料理のプロセスに類似しています。これは、類似性と同一性の深い違いの問題に似ています。

• カオス理論
• ゲーデルの定理
• 計算
• 計算等価性の原則
• 人工知能
• ロバート・ローゼン
• 出現行動

• Weisstein, Eric W. 他、「計算の既約性」。MathWorld—Wolfram Web リソース。
• ウルフラム、スティーブン、「新しい種類の科学」。ウルフラムメディア社、2002 年 5 月 14 日。ISBN 1-57955-008-8 
  • ウルフラム、スティーブン、「計算の既約性」。新しい種類の科学。
  • ウルフラム、スティーブン、「計算不可約性の歴史」。新しい種類の科学。
  • ウルフラム、スティーブン、「計算不可約性ノートの歴史」。新しい種類の科学。
  • ウルフラム、スティーブン、「理論物理学における決定不能性と扱いにくさ」。Physical Review Letters、1985年。
• Israeli、Navot、Nigel Goldenfeld、「複雑な物理システムの計算上の既約性と予測可能性について」。Physical Review Letters、2004 年。
• 「計算の既約性」。ISAAC/EINSTein の研究開発。2011 年 12 月 11 日にオリジナルからアーカイブされました。
• バーガー、デイビッド、「スティーブン・ウルフラム、新しい種類の科学」。セレンディップの本棚。
• 「複雑さはとらえどころがない」。Physical Review Letters、2004 年 3 月 4 日。
• Tomasson, Gunnar、「科学理論と計算の不可逆性」。新しい種類の科学：NKS フォーラム。