Bài toán dừng và tính không quyết định được

Bài toán dừng, tức là quyết định xem một chương trình nhất định có dừng lại trên một đầu vào nhất định hay không, là ví dụ điển hình về một bài toán không quyết định được bằng thuật toán, và các phép quy giản từ nó chứng minh tính không quyết định được của nhiều bài toán khác.

Definition

Một bài toán quyết định được gọi là không quyết định được nếu không có máy Turing nào giải quyết nó một cách chính xác trên tất cả các đầu vào; bài toán dừng hỏi liệu một máy tùy ý có dừng trên một đầu vào tùy ý hay không, và nó là bài toán không quyết định được nguyên mẫu mà từ đó các bài toán khác được chứng minh là không quyết định được bằng phép quy giản.

Scope

Chủ đề này bao gồm phát biểu chính xác của bài toán dừng, chứng minh tính không quyết định được của nó bằng phương pháp chéo hóa, kỹ thuật quy giản nhiều-một để chuyển giao tính không quyết định được, định lý Rice về các thuộc tính không tầm thường của chương trình, và các bài toán không quyết định được kinh điển như Entscheidungsproblem và bài toán từ cho nhóm.

Core questions

• Tại sao không có thuật toán nào quyết định được liệu các chương trình có dừng hay không?
• Làm thế nào để sử dụng phép quy giản để chứng minh một bài toán không quyết định được từ một bài toán khác?
• Định lý Rice nói gì về việc quyết định các thuộc tính của chương trình?
• Những bài toán toán học nổi tiếng nào hóa ra là không quyết định được?

Key theories

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

Một lập luận chéo hóa cho thấy rằng việc giả định một bộ quyết định dừng sẽ dẫn đến mâu thuẫn, do đó không có thuật toán nào có thể quyết định sự dừng cho tất cả các chương trình và đầu vào.

Quy giản và chuyển giao tính không quyết định được

Nếu một bài toán không quyết định được đã biết quy giản về một bài toán mục tiêu, thì bài toán mục tiêu cũng không quyết định được, biến phép quy giản thành công cụ tiêu chuẩn để thiết lập tính không quyết định được.

Định lý Rice

Mọi thuộc tính không tầm thường của hàm được tính toán bởi một chương trình đều không quyết định được, do đó về cơ bản không có thuộc tính hành vi thú vị nào của chương trình có thể được quyết định bằng thuật toán.

Clinical relevance

Các kết quả về tính không quyết định được thiết lập giới hạn cứng đối với suy luận tự động và phân tích chương trình: chúng cho thấy rằng các công cụ tổng quát hoàn hảo để xác minh sự kết thúc hoặc các thuộc tính của chương trình không thể tồn tại, và chúng giải thích tại sao nhiều bài toán trong logic, đại số và lý thuyết số không có giải pháp thuật toán.

History

Turing và Church đã chỉ ra vào năm 1936 rằng Entscheidungsproblem, câu hỏi về một thuật toán quyết định tính hợp lệ bậc nhất, là không giải được, với bài toán dừng là trọng tâm trong lập luận của Turing. Rice đã khái quát hóa hiện tượng này vào năm 1953, và tính không quyết định được sau đó đã được thiết lập cho các bài toán cụ thể như bài toán từ cho nhóm bởi Novikov và bài toán thứ mười của Hilbert bởi Matiyasevich.

Key figures

• Alan Turing
• Alonzo Church
• Henry Gordon Rice
• Pyotr Novikov

Seminal works

• sipser2013
• turing1936
• rogers1987

Frequently asked questions

Tại sao máy tính nhanh hơn không thể giải quyết bài toán dừng?

Tính không quyết định được không phụ thuộc vào tốc độ hay bộ nhớ: lập luận chéo hóa loại trừ bất kỳ thuật toán nào, bất kể nó được cấp bao nhiêu thời gian. Bài toán dừng về nguyên tắc là không giải được, chứ không chỉ đơn thuần là không thực tế.

Chúng ta có thể biết liệu một chương trình có dừng hay không?

Thường là có đối với các chương trình cụ thể, bằng cách phân tích hoặc chạy chúng. Điều không thể là một thuật toán duy nhất trả lời chính xác câu hỏi cho mọi chương trình và đầu vào. Do đó, các công cụ kiểm tra sự kết thúc thực tế chỉ thành công trên các lớp hạn chế hoặc có thể không đưa ra được câu trả lời.