Định lýĐã chứng minh

Tính không giải được của bài toán dừng

Phát biểu

Không tồn tại thuật toán nào, khi nhận một chương trình (máy Turing) $P$ và đầu vào $x$ bất kỳ, luôn quyết định đúng trong thời gian hữu hạn xem $P$ có dừng khi chạy trên $x$ hay không.

Vì sao đúng?

Giả sử tồn tại bộ quyết định dừng $H$ như vậy. Xây dựng chương trình $D$ mà, với đầu vào là một chương trình $Q$ , chạy $H$ để kiểm tra xem $Q$ có dừng khi chạy trên chính nó hay không, rồi làm điều ngược lại (lặp mãi nếu $Q$ dừng, dừng nếu $Q$ lặp mãi). Chạy $D$ với chính nó làm đầu vào dẫn tới mâu thuẫn dù theo hướng nào, nên $H$ không thể tồn tại.

Phác thảo chứng minh

Lập luận đường chéo: giả sử tồn tại bộ quyết định $H(P,x)$ cho biết $P$ có dừng trên $x$ hay không; định nghĩa $D(P) =$ 'lặp mãi' nếu $H(P,P)$ trả lời 'dừng', ngược lại 'dừng'; rồi tự hỏi $D(D)$ có dừng không. Nếu nó dừng thì theo định nghĩa $H(D,D)$ đã trả lời 'lặp mãi', mâu thuẫn; nếu nó lặp mãi thì $H(D,D)$ đã trả lời 'dừng', cũng mâu thuẫn. Vậy $H$ không thể tồn tại.

Người chứng minh

chứng minh năm 1936Alan Turing

Chủ đề chứa định lý này

Hàm đệ quy, máy Turing Định lý bất toàn Gödel

Định lý liên quan

Định lý bất toàn thứ nhất của Gödel

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Alan M. Turing (1936). On Computable Numbers, with an Application to the Entscheidungsproblem · DOI:10.1112/plms/s2-42.1.230
Michael Sipser (2012). Introduction to the Theory of Computation