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 minh năm 1936 rằng không tồn tại thuật toán nào giải quyết 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 minh 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 thể quyết định được trên máy Turing. Nó là một trong những ví dụ đầu tiên của các bài toán quyết định.

Theo Jack Copeland (2004), tên gọi bài toán dừng (tiếng Anh - halting problem) là của Martin Davis.

Giới thiệu

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.

Ví dụ như chương trình sau dưới dạng mã giả

while True:

continue

không bao giờ dừng, nó lặp lại 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ó để phân tích. Ta có thể chạy chương trình một thời gian. Tuy nhiên, nếu nó không dừng trong thời gian đó thì cũng không thể biết được nó có chạy mãi mãi hay không. Turing chứng minh rằng không một thuật toán nào có thể quyết định đúng cho mọi cặp chương trình và dữ liệu vào, liệu chương trình có dừng hay không trên dữ liệu đã cho.

Tầm quan trọng và hệ quả

Bài toán dừng là vô cùng quan trọng trong lịch sử lý thuyết khả tính do nó là một trong những bài toán đầu tiên được chứng minh là không quyết định được.

Biểu diễn bài toán dừng dưới dạng tập hợp

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 cho bài toán dừng.

Có nhiều định nghĩa tương đương của bài toán dừng. Tất cả các 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 minh

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
f(i,j)		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.

Tham khảo

Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230–265. Phiên bản online^{[liên kết hỏng]} Đây là bài báo lịch sử định nghĩa máy Turing, bài toán dừng, và chứng minh nó (cùng với bài toán Entscheidungsproblem) là không giải được.
Sipser, Michael (2006). “Phần 4.2: The Halting Problem”. Introduction to the Theory of Computation (ấn bản thứ 2). PWS Publishing. tr. 173–182. ISBN 053494728X.
B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7.
Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press.. Bài báo của Turing là bài thứ 3 trong cuốn sách này. Ngoài ra còn có các bài báo của Godel, Church, Rosser, Kleene, và Post.
Davis, Martin (1958). Computability and Unsolvability. New York: McGraw-Hill..
Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980.
Marvin Minsky, Computation, Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967. Xem chương 8, phần 8.2 "The Unsolvability of the Halting Problem."
Roger Penrose, The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics, Oxford University Press, Oxford England, 1990 (with corrections). Xem chương 2, "Algorithms and Turing Machines".
John Hopcroft và Jeffrey Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading Mass, 1979. Xem chương 7 "Turing Machines."
Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Chương "The Spirit of Truth" mô tả lịch sử và thảo luận về chứng minh của Turing.
Constance Reid, Hilbert, Copernicus: Springer-Verlag, New York, 1996 (first published 1970). Lịch sử toán học và vật lý Đức từ thập kỉ 1880 đến 1930.
Edward Beltrami, What is Random? Chance and order in mathematics and life, Copernicus: Springer-Verlag, New York, 1999.
Ernest Nagel và James R. Newman, Godel’s Proof, New York University Press, 1958.
Taylor Booth, Sequential Machines and Automata Theory, Wiley, New York, 1967. Xem chương 9, Turing Machines.
David Bolter, Turing’s Man: Western Culture in the Computer Age, The University of North Carolina Press, Chapel Hill, 1984.
Stephen Kleene, Introduction to Metamathematics, North-Holland, 1952. Chương XIII ("Computable Functions") thảo luận về việc bài toán dừng không giải được trên máy Turing.

Tham khảo