computation-theory - Provable ==決定可能ですか？

Question

計算理論では、ProvableとDecidableという用語は交換可能ですか？それらは同じことを意味しますか？

たとえば、決定問題（Das Entscheidungsproblem）と呼ばれる何かが証明可能かどうかという質問をよく目にします。

Answer 1

これらは異なります。実際、それらは完全に異なる領域を指しています。

決定可能とは、「受け入れ」または「拒否」を出すチューリングマシンによって、すべての可能な入力について決定問題を解決できることを意味します。

証明可能とは、数学的なステートメントが数学的な証明によって証明できることを意味します。

実際、「決定可能」と「証明可能」を比較することはできません。これらの属性はまったく異なるものを指すからです。