Một bằng chứng cho thấy có ít nhất một chương trình máy tính tầm thường không thể tồn tại

Bằng chứng toán học đẹp nhất, tập. 2, Coutte tối đa.

Bài báo tuần trước là về một số người nổi tiếng lớn hơn những người khác? và đối số đường chéo Cantor. Tuần này tôi muốn chia sẻ một trong những vấn đề khoa học máy tính lý thuyết yêu thích của tôi.

Các bộ phận từ bốn máy tính đầu năm 1962. Từ trái sang phải: bảng ENIAC, bảng EDVAC, bảng ORDVAC và bảng BRLESC-I, cho thấy xu hướng thu nhỏ.

Tôi nhớ hồi còn học cấp hai khi tôi bắt đầu học Khoa học Máy tính, tôi đã nghĩ rằng về mặt lý thuyết tôi có thể giải quyết bất kỳ Bài toán tính toán nào bằng các công cụ Toán học và Lập trình phù hợp. Tôi đã sai. Có giới hạn lý thuyết cho bất kỳ Máy tính nào và ở đây chúng ta sẽ thấy bằng chứng rằng có ít nhất một vấn đề logic mà không Chương trình máy tính nào có thể giải quyết được.

Xác định H, Chương trình máy tính bất khả thi

Chúng tôi định nghĩa Chương trình máy tính P (i) là danh sách các hướng dẫn P mà khi được thực hiện với đầu vào i, đưa ra đầu ra o.

Ví dụ,

là một chương trình tính tổng hai số bạn đưa ra làm đầu vào và

là một chương trình sử dụng một chương trình khác - P_add - làm đầu vào và vượt qua chương trình này hai đầu vào khác. Nó làm những gì P_add (a, b) làm và nhân đôi nó.

Khi một chương trình được thực thi, nó có thể bị kẹt, chạy mãi mãi và không bao giờ xuất ra bất cứ thứ gì, ví dụ, một chương trình P_sum tiến hành tổng của tất cả các số tự nhiên sẽ tiếp tục thêm số tự nhiên mãi mãi mà không bao giờ kết thúc chạy (ví dụ: tạm dừng) và xuất kết quả.

Bây giờ, giả sử rằng nó tồn tại một chương trình H (P, i) lấy đầu vào là danh sách các hướng dẫn P của chương trình P (i) và i là đầu vào của P (i) và xuất ra 1 nếu P (i) dừng lại ở một số điểm và 0 nếu P (i) bị kẹt và chạy mãi mãi. Nói một cách đơn giản,

Tại sao Danh sách Hướng dẫn Logic H không thể tồn tại

Dựa trên bằng chứng của Alan Turing trên tờ giấy Trên các số có thể tính toán được, với một ứng dụng cho Entscheidungspro Hiệu -1937, chúng tôi sẽ chứng minh rằng H không thể tồn tại.

Dựa trên giả định rằng H tồn tại, chúng ta xây dựng chương trình X (P) chạy mãi mãi khi và chỉ khi H (P, P) = 1 và dừng lại khi và chỉ khi H (P, P) = 0. Nói cách khác,

Bây giờ chúng ta có thể xem xét đưa ra X (i) danh sách hướng dẫn X riêng của mình làm đầu vào: X (X).

Do đó X (X) chạy mãi khi và chỉ khi H (X, X) = 1 và X (X) tạm dừng khi và chỉ khi H (X, X) = 0. Nói cách khác,

Chúng tôi có một mâu thuẫn! Chúng tôi đã chỉ ra bởi Reductio ad absurdum rằng H không thể tồn tại vì sự tồn tại của nó dẫn đến kết luận vô lý.

Do đó, một Chương trình Máy tính có thể xác định xem bất kỳ Chương trình Máy tính nào được cung cấp bất kỳ đầu vào nào sẽ bị kẹt và chạy mãi mãi hoặc chạy xong là không thể. Có ít nhất một Chương trình Máy tính giải quyết vấn đề logic không thể tồn tại.

Tài liệu tham khảo, Alan Turing. Một số ứng dụng có thể tính toán được, với một ứng dụng cho Entscheidungspropet. 1937.

Tôi là Max Coutte, đồng sáng lập Relativty.com, một tai nghe VR tôi thiết kế từ đầu, trong đó tôi đã mở mã nguồn và phần cứng. Theo dõi tôi trên Twitter @maxcoutte.