Làm thế nào để biết máy có phải là máy Turing tương đương

Question

Tôi đã tìm thấy bài viết trên Wikipedia là a list of Turing machine equivalents. Tuy nhiên, nó không nói một phương pháp làm thế nào để xác định xem một máy đã cho là máy Turing tương đương hay không.

Tôi có cần sử dụng định nghĩa của máy Turing để chứng minh không? Bạn có thể đưa ra một ví dụ?

Cảm ơn.

Answer 1

Cách tiêu chuẩn để chứng minh điều gì đó hoàn chỉnh là thực hiện một trong các TM-tương đương trong máy của bạn. Nếu điều đó có thể thực hiện được, thì máy của bạn sẽ hoàn thiện. Nếu không, thì không. Vì vậy, nếu tôi đã cố gắng để chứng minh, nói rằng một ngôn ngữ lập trình mới là hoàn toàn turing, tôi muốn chọn TM-tương đương đó là đơn giản nhất để thực hiện, và sau đó cho thấy rằng ngôn ngữ lập trình của tôi có thể mô phỏng nó.

Answer 2

Phần trên cùng của đầu: Nếu máy của bạn có thể mô phỏng một trong các máy tương đương với máy Turing đã biết, thì máy của bạn cũng tương đương với máy Turing.

Có lẽ cách dễ nhất để làm gì đó giống như thế này.

CHỈNH SỬA: Tôi không ngụ ý rằng đây là một yêu cầu cho một máy tính tương đương với máy Turing, có lẽ nó có thể là như vậy. Có lẽ ai đó giỏi hơn một chút về thông tin lý thuyết có thể làm rõ tôi về điều này?

Answer 3

Thực ra nó không thể thực sự được chứng minh. Ít nhất, hoàn toàn chính thức hóa các bằng chứng bình đẳng chung này có thể yêu cầu logic chính thức hơn nhiều so với dự kiến ​​ngay cả trong khoa học máy tính lý thuyết. (nếu bạn không đồng ý, hãy cho tôi biết! Tôi mong muốn thảo luận về điều này.)

Tuy nhiên, điều này chủ yếu là rõ ràng từ ngữ cảnh. Bạn thử xây dựng một mô phỏng của một "máy" của sơ đồ tính toán A trong một mô hình tính toán như vậy B. Điều này có nghĩa B có thể mô phỏng A, và do đó có toàn bộ sức mạnh của A. Nếu bạn làm ngược lại, hai mô hình này được gọi là tương đương.