Tính khả dụng và tính đệ quy

Question

Giả sử tồn tại máy Turing M1, M2, M3, các ngôn ngữ mà chúng nhận dạng là L (M1), L (M2) và L (M3) tương ứng. Ngôn ngữ sau L = {(M1, M2, M3): L (M1), L (M2) và L (M3) không bằng nhau} Ngôn ngữ có thể giải quyết được không? Đệ quy enumerable? Hay không?

Answer 1

Hãy M _{M i, tôi} là một cỗ máy mô phỏng chạy một số máy khác M _i trên đầu vào I và trả true nếu M _i cuối cùng dừng trên I, và vòng lặp mãi mãi khác.

Cho phép M _∞ là một máy tầm thường chỉ lặp lại mãi mãi.

Sau đó, (M _{M i, tôi}, M _∞, M _∞) là trong L iff M _i tạm dừng trên đầu vào I.

Điều này làm giảm khả năng decidability của vấn đề tạm dừng để decidability của L, do đó, L là undecidable.

=============

Tiếp theo, hãy chứng minh rằng L không đệ quy đếm được do mâu thuẫn.

Giả sử rằng L là đệ quy đếm được, do đó tồn tại một máy Turing M ví dụ rằng nếu M _i, M _j, và M _k ba máy Turing có ngôn ngữ tương ứng không bằng nhau, sau đó M sẽ cuối cùng nhổ ra ba (M _i, M _j, M _k).

Bây giờ hãy xem xét một sửa đổi đối với M, được gọi là M ', được xác định bằng cách lấy M và thêm giá trị (M, M', M ') vào L (M'). Câu hỏi quan trọng cần đặt ra là nếu (M, M ', M') nằm trong L? Vâng, nếu (M, M ', M') là trong L, thì L (M) không được bằng L (M ') (nếu không nó sẽ không phù hợp với định nghĩa trong L), vì vậy L (M) không được bao gồm (M, M ', M') (vì đó là sửa đổi duy nhất chúng tôi đã thực hiện). Ngược lại, nếu (M, M ', M') không có trong L, thì L (M)! = L (M ') (vì chúng ta đã thêm tripe đó vào L (M')), do đó, nó phải nằm trong L (M), bởi vì các ngôn ngữ không bằng nhau.

Vì vậy, chúng tôi đã đạt đến một nghịch lý ngụ ý rằng M không thể tồn tại, và do đó L không đệ quy đếm được.