- 333 名前：１３２人目の素数さん [2024/05/05(日) 12:02:28.00 ID:HvNo6+XN.net]
- これ、参考になるだろう
https://zenn.dev/mineel5/articles/db3e410a05e2d8
zenn /mineel
停止性問題と不完全性定理
2023/08/12
はじめに
巷では「停止性問題は不完全性定理と深いつながりがある」みたいな主張をよく耳にしますが、その具体的な繋がりまで説明されていることは多くありません。
そこで、この記事では停止性問題が具体的にどう不完全性定理に繋がるのか解説しようと思います。
結論を言ってしまうと、「決定不能なRE集合さえあればそこから直ちに第一不完全性定理が導ける」というだけの話であり、ちょうど手頃な具体例に停止性問題があっただけで別に停止性問題である必然性はありません。
なので、私は停止性問題と不完全性定理には本質的なつながりはないと考えております。
もう少し各用語についても説明します。
停止性問題とは、一般にプログラム及びそのプログラムへの入力を受け取ったときにその実行が停止するのか有限時間で判断できるのかという問題です。
結論を言ってしまうと、できません。
停止性問題は決定不能な問題と呼ばれるコンピュータには有限時間で計算できない問題になっております。
また、第一不完全性定理とは、ある条件を満たす一階述語論理は必ず証明も反証もできない論理式を持つという論理学における基本的な定理です。
不完全性定理周辺の話題はメタ数学の極みといった感じで、何かが成り立つと言ったときそれはどの体系において成り立つのか、その条件はどの体系における条件なのか、などを常に気にする必要があります。
すなわち、常に自分の位置を把握しながら全てを相対的に捉える必要があり、これにはとても鍛錬が必要だと感じています。
(かくいう私も不完全性定理を理解できているとはとても言えません)
しかし、この記事ではそこまでの難しい話はしないのでそういったメタ数学的な混乱はないかと思われるので安心してください。
それでは以下で詳しく説明していきます。
よろしくお願いします。
|
 |
