Trong lý thuyết tính toán là các thuật ngữ Có thể hoán đổi và có thể thay đổi được? Chúng có nghĩa là giống nhau không?Does Provable == Decidable?
Ví dụ: bạn thường thấy câu hỏi liệu có điều gì đó có thể chứng minh được gọi là vấn đề quyết định (Das Entscheidungsproblem) hay không.
Chúng khác nhau. Trong thực tế, họ đề cập đến các khu vực hoàn toàn khác nhau.
Phương tiện có thể giải quyết được, vấn đề quyết định có thể được giải quyết cho tất cả các đầu vào có thể bằng máy Turing, đặt ra 'chấp nhận' hoặc 'từ chối'.
Phương tiện khả thi, một tuyên bố toán học có thể được chứng minh bằng, tốt, bằng chứng toán học.
Thực tế, bạn không thể so sánh 'có thể giải mã' và 'có thể chứng minh', vì các thuộc tính này đề cập đến những thứ hoàn toàn khác nhau.
Bạn phải chứng minh rằng quyết định của máy hoạt động bình thường;) – Dario
Có lẽ câu hỏi phù hợp cho mathoverflow.net? –
Tôi nghĩ về điều đó nhưng như Comp. Lý thuyết (và phức tạp) khóa học có thể được tìm thấy trên hầu hết tất cả các khóa học CS \ SE tôi nghĩ ở đây sẽ phù hợp hơn. –