Chương trình tự tái sinh (hết)

Trong các bài trước, ta đã "chứng minh" rằng mọi chương trình có thể lấy được đoạn mã của chính nó. (Chứng minh điều này một cách chặt chẽ bằng toán học cũng không có gì khó khăn, tương tự như các ý tưởng ta đã trình bày, chỉ cần định nghĩa rõ ràng thế nào là một chương trình.) Phát biểu này thường được gọi là định lý đệ qui (recursion theorem).

Trong bài này, ta minh họa một ứng dụng của định lý đệ qui. Ta sẽ dùng định lý này để chứng minh rằng bài toán dừng không quyết định được. Tôi sẽ thảo luận ý tưởng chính, bỏ qua các chi tiết toán không quan trọng. Bài toán dừng đại khái có thể phát biểu như sau: " cho một đoạn mã chương trình [M] và một chuỗi w, quyết định xem với input w thì M có dừng sau một số hữu hạn các bước hay không? " (Ta dùng [M] để chỉ đoạn mã của chương trình M.)

Định lý : không tồn tại chương trình nào giải bài toán dừng.

Chứng minh: giả sử có chương trình A giải bài toán dừng, ta thiết kế một chương trình M để làm phản chứng như sau

1. Gọi input của M là w
2. M tự lấy đoạn mã [M] của chính nó
3. M chạy A với input là ([M], w).
4. Nếu A trả lời là "dừng" thì M nhảy vào một vòng lặp vô tận.
5. Nếu A trả lời là "không dừng" thì M dừng.

Như vậy A không thể nào quyết định xem M có dừng hay không!

Chứng minh trên rất đặc trưng cho lập luận đường chéo của Cantor, thường được dùng cho các bài toán mà đối tượng có tính tự tham chiếu. Lý luận kiểu như trên là một trong những công cụ rất mạnh để chứng minh phản chứng trong lý thuyết tính toán.

Không biết các bạn thế nào chứ lúc đầu tôi thấy việc thiết kế chương trình tự in khá là phản trực quan. (Tưởng tượng một nhà máy sản xuất gỗ lại có thể sản xuất một nhà máy sản xuất gỗ y hệt như nó.) Thế mà câu trả lời không những là có các chương trình như vậy, mà còn có cả một nguyên tắc viết các chương trình đó.

Trong loạt bài này, ta đã đi từ một câu hỏi tự tham chiếu này (chương trình tự in) sang câu hỏi tự tham chiếu khác (bài toán dừng). Ta dùng câu trả lời có cho câu hỏi đầu để trả lời không cho câu hỏi thứ hai.