Bài toán dừng
Trong lý thuyết khả tính, bài toán dừng có thể diễn đạt như sau: cho trước một chương trình máy tính, quyết định xem chương trình đó có chạy mãi mãi hay không. Bài toán này tương đương với việc cho trước một chương trình và dữ liệu vào, quyết định xem chương trình đó có dừng với dữ liệu đó hay chạy mãi mãi.
Alan Turing chứng tỏ năm 1936 rằng không sống sót thuật toán nào xử lý bài toán dừng cho mọi cặp chương trình-dữ liệu vào. Một phần quan trọng của chứng tỏ là định nghĩa của máy tính và chương trình, nay được biết đến là máy Turing. Bài toán dừng là không hề quyết định hành động được trên máy Turing. Nó là một trong những ví dụ tiên phong của những bài toán quyết định hành động .Theo Jack Copeland ( 2004 ), tên gọi bài toán dừng ( tiếng Anh – halting problem ) là của Martin Davis .
Bài toán dừng là một bài toán quyết định về tính chất của chương trình máy tính trên một mô hình tính toán Turing-đầy đủ nhất định. Bài toán yêu cầu quyết định xem một chương trình với dữ liệu vào cho trước có dừng hay chạy mãi mãi. Trong mô hình trừu tượng này, không có bất kì một giới hạn nào về bộ nhớ hay thời gian cho máy chạy; máy có thể chạy lâu bao nhiêu cũng được, sử dụng tùy ý bộ nhớ, trước khi dừng. Câu hỏi chỉ là liệu chương trình cuối cùng có dừng hay không trên dữ liệu đã cho.
Bạn đang đọc: Bài toán dừng – Wikipedia tiếng Việt
Ví dụ như chương trình sau dưới dạng mã giả
- while True:
- continue
không khi nào dừng, nó tái diễn mãi mãi. Trong khi đó, chương trình sau
- print “Xin chào”
dừng rất nhanh .Chương trình càng phức tạp thì càng khó để nghiên cứu và phân tích. Ta hoàn toàn có thể chạy chương trình một thời hạn. Tuy nhiên, nếu nó không dừng trong thời hạn đó thì cũng không hề biết được nó có chạy mãi mãi hay không. Turing chứng tỏ rằng không một thuật toán nào hoàn toàn có thể quyết định hành động đúng cho mọi cặp chương trình và tài liệu vào, liệu chương trình có dừng hay không trên tài liệu đã cho .
Tầm quan trọng và hệ quả[sửa|sửa mã nguồn]
Bài toán dừng là vô cùng quan trọng trong lịch sử vẻ vang kim chỉ nan khả tính do nó là một trong những bài toán tiên phong được chứng tỏ là không quyết định hành động được .
Biểu diễn bài toán dừng dưới dạng tập hợp[sửa|sửa mã nguồn]
Cách biểu diễn thông thường của các bài toán quyết định là tập hợp các đối tượng thỏa mãn tính chất đang xét. Tập dừng
K:= {(i, x) | chương trình i với dữ liệu vào x dừng trong hữu hạn bước}
đại diện thay mặt cho bài toán dừng .Có nhiều định nghĩa tương tự của bài toán dừng. Tất cả những tập có bậc Turing bằng với bài toán dừng là một cách định nghĩa. Sau đây là một vài ví dụ :
- { i | chương trình i dừng khi chạy trên dữ liệu vào 0 }
- { i | tồn tại dữ liệu vào x sao cho chương trình i dừng khi chạy trên dữ liệu x }
Tóm tắt chứng tỏ[sửa|sửa mã nguồn]
Sau đây là một chứng minh rằng không tồn tại một hàm khả tính nào quyết định được liệu một chương trình cho trước có dừng trên một dữ liệu vào cho trước hay không. Nói cách khác, nếu định nghĩa hàm h(i, x) trả về 1 nếu chương trình thứ i dừng trên dữ liệu vào x và 0 nếu nó không dừng, thì h là không tính được. Ở đây chương trình thứ i là theo thứ tự của một cách liệt kê tất cả các chương trình của một mô hình tính toán Turing đầy đủ.
| f(i,j) | i | i | i | i | i | i | |
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| j | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| j | 2 | 0 | 0 | 0 | 1 | 0 | 0 |
| j | 3 | 0 | 1 | 0 | 1 | 0 | 1 |
| j | 4 | 1 | 0 | 0 | 1 | 0 | 0 |
| j | 5 | 0 | 0 | 0 | 1 | 1 | 1 |
| j | 6 | 1 | 1 | 0 | 0 | 1 | 0 |
| f(i,i) | 1 | 0 | 0 | 1 | 1 | 0 | |
| g(i) | U | 0 | 0 | U | U | 0 | |
Các giá trị của hàm f xếp trên một bảng hai chiều. Các ô màu cam là đường chéo chính. Các giá trị f(i,i) và g(i) được liệt kê ở dưới; U đánh dấu việc hàm g không được định nghĩa cho dữ liệu vào tương ứng
Ý tưởng chính ở đây là chứng minh mọi hàm khả tính đều khác với hàm h. Thật vậy, xem xét một hàm f bất kì. Định nghĩa hàm khả tính g như sau:g(i) không được định nghĩa khi f(i,i) = 0 (chẳng hạn bằng cách g lặp mãi mãi khi f(i,i)=0)và bằng 0 trong trường hợp còn lại. Nhận thấy rằng nếu f khả tính thì g khả tính.
Do g khả tính, tồn tại một chương trình e trong mô hình tính toán đã định để tính hàm g. Theo định nghĩa của g, luôn xảy ra một trong hai trường hợp sau:
- g(e) = f(e, e) = 0. Khi đó h(e,e) = 1 vì chương trình e dừng trên dữ liệu e.
- g(e, e) ≠ 0. Trong trường hợp này h(e,e) = 0, do chương trình e không dừng trên dữ liệu vào e.
Trong cả hai trường hợp, f và h nhận giá trị khác nhau. Do f là một hàm khả tính bất kì, mọi hàm khả tính đều khác với h.
Source: https://khoinganhcntt.com
Category: NGÀNH TUYỂN SINH