Nền tảng toán học

Hàm đệ quy, máy Turing

Các mô hình hình thức xác định chính xác những hàm nào có thể tính được bằng thuật toán.

Trực giácMáy tính được những gì?

Máy tính bỏ túi cộng và nhân được; trình biên dịch kiểm tra kiểu được; AI (đôi khi) trả lời câu hỏi được. Nhưng có hàm nào mà không thuật toán nào, dù thông minh đến đâu, có thể tính được không? Câu trả lời của Alan Turing — có — đến từ một mô hình toán học chính xác cho "thuật toán": máy Turing, gồm một băng, một đầu đọc/ghi, và một bảng quy tắc hữu hạn. Hai cách hình thức hóa tưởng chừng khác nhau, hàm đệ quy (xây từ các mảnh đơn giản bằng hợp thành và đệ quy) và máy Turing (một quá trình cơ học từng bước), hóa ra tính được chính xác cùng một lớp hàm — bằng chứng mạnh cho luận đề Church–Turing rằng đây thực sự là "mọi thứ tính được".

Đồ thị chuyển trạng thái của một máy Turing nhỏ: đỉnh là trạng thái, cạnh là chuyển tiếp gắn nhãn (đọc → ghi, di chuyển).

Đại họcHàm đệ quy nguyên thủy và hàm $\mu$ -đệ quy

Định nghĩa: Hàm đệ quy nguyên thủy

Hàm đệ quy nguyên thủy là lớp hàm nhỏ nhất $\mathbb N^k \to \mathbb N$ chứa hàm không, hàm kế tiếp $S(n)=n+1$ , mọi phép chiếu, và đóng dưới hợp thành và đệ quy nguyên thủy: cho $g:\mathbb N^k\to\mathbb N$ và $h:\mathbb N^{k+2}\to\mathbb N$ , phép đệ quy $f(\vec x,0)=g(\vec x)$ , $f(\vec x,n+1)=h(\vec x,n,f(\vec x,n))$ định nghĩa một hàm đệ quy nguyên thủy mới $f$ . Cộng, nhân, lũy thừa, và mọi chương trình "vòng lặp for" có chặn cố định đều là đệ quy nguyên thủy — và mọi hàm đệ quy nguyên thủy đều toàn phần (xác định trên mọi đầu vào) và dừng sau số bước bị chặn với mỗi đầu vào.

f(\vec x,0)=g(\vec x), \qquad f(\vec x,n+1)=h(\vec x,n,f(\vec x,n))

Để bắt trọn mọi hàm tính được — kể cả hàm có thể không dừng — ta thêm một phép toán nữa. Hàm ** $\mu$ -đệ quy (đệ quy tổng quát) thêm phép cực tiểu hóa không chặn**: $\mu y.\,[P(\vec x,y)=0]$ trả về $y$ nhỏ nhất sao cho $P(\vec x,y)=0$ , tìm kiếm $y=0,1,2,\dots$ — và đơn giản không bao giờ trả về nếu không tồn tại $y$ như vậy. Chính điều này làm hàm $\mu$ -đệ quy có khả năng không dừng, và định lý Kleene chỉ ra chúng tính đúng cùng lớp hàm (bộ phận) như máy Turing.

\mu y.\,[P(\vec x,y)=0] = \min\{y : P(\vec x,y)=0\}

Đệ quy nguyên thủy so với đệ quy tổng quát ( $\mu$ ) so với khả tính Turing
Lớp	Xây từ	Luôn dừng?	Ví dụ
Đệ quy nguyên thủy	Hợp thành + đệ quy có chặn	Có, luôn toàn phần	$+,\times,$ lũy thừa
Đệ quy tổng quát ( $\mu$ )	Đệ quy nguyên thủy + $\mu$ không chặn	Không, có thể chạy mãi	Hàm Ackermann $A$
Khả tính Turing (bộ phận)	Trạng thái + băng + quy tắc chuyển	Không, đúng bằng $\mu$ -đệ quy	Bất kỳ thuật toán nào

Định lý: Tính không quyết định của bài toán dừng

Không tồn tại thuật toán $H(e,x)$ mà, với mọi chỉ số chương trình $e$ và đầu vào $x$ , luôn dừng và cho ra chính xác việc $\varphi_e(x)$ (chạy chương trình $e$ trên đầu vào $x$ ) có dừng hay không.

Vì sao đúng?

Đây là lý do toán học vì sao không phần mềm diệt vi-rút, trình biên dịch, hay IDE nào có thể phát hiện hoàn hảo vòng lặp vô hạn, mã chết, hay "hàm này luôn lỗi" một cách tổng quát — không phải giới hạn kỹ thuật hiện tại, mà là một bức tường toán học cứng.

Chứng minh

Giả sử phản chứng tồn tại bộ quyết định $H$ : $H(e,x)=1$ nếu $\varphi_e(x)\!\downarrow$ (dừng) và $H(e,x)=0$ nếu $\varphi_e(x)\!\uparrow$ (chạy mãi), và bản thân $H$ luôn dừng với đáp án đúng.

Dùng $H$ , xây một chương trình mới $D$ mà, với đầu vào $e$ : tính $H(e,e)$ ; nếu $H(e,e)=1$ , thì $D$ vào vòng lặp vô hạn; nếu $H(e,e)=0$ , thì $D$ dừng ngay. $D$ được xây hiệu quả từ $H$ (chỉ là $H$ cộng một câu lệnh if và một vòng lặp), nên nó có chỉ số chương trình nào đó $d$ , tức $D=\varphi_d$ .

Giờ đặt câu hỏi tự quy chiếu: $\varphi_d(d)$ có dừng không?

Trường hợp 1: nếu $\varphi_d(d)$ dừng, thì theo tính đúng của $H$ , $H(d,d)=1$ . Nhưng theo định nghĩa của $D$ , $H(d,d)=1$ làm $D$ chạy mãi ở đầu vào $d$ — tức $\varphi_d(d)$ không dừng. Mâu thuẫn.

Trường hợp 2: nếu $\varphi_d(d)$ không dừng, thì theo tính đúng của $H$ , $H(d,d)=0$ . Nhưng theo định nghĩa của $D$ , $H(d,d)=0$ làm $D$ dừng ở đầu vào $d$ — tức $\varphi_d(d)$ có dừng. Mâu thuẫn.

Cả hai trường hợp đều mâu thuẫn, nên giả thiết $H$ tồn tại là sai. Bài toán dừng không quyết định được. $\blacksquare$

Nâng caoĐịnh lý Rice

Bài toán dừng chỉ là một ví dụ của hiện tượng rộng lớn hơn nhiều. Gọi tính chất $P$ của các hàm khả tính bộ phận là ngữ nghĩa nếu nó chỉ phụ thuộc vào hàm $\varphi_e$ mà chương trình $e$ tính, không phụ thuộc mã nguồn, và không tầm thường nếu một hàm khả tính có nó và một hàm khác thì không.

Định lý: Định lý Rice

Với mọi tính chất ngữ nghĩa không tầm thường $P$ của các hàm khả tính bộ phận, tập $\{e : \varphi_e \text{ has property } P\}$ không quyết định được.

Vì sao đúng?

Định lý duy nhất này ngay lập tức loại trừ thuật toán cho "chương trình này có tính hàm không hay không", "chương trình này có tính toàn phần không", "hai chương trình này có tương đương không", và vô số câu hỏi tự nhiên khác về hành vi chương trình — tất cả cùng một lúc, không cần lập luận đường chéo riêng cho từng câu.

Chứng minh

Không mất tổng quát giả sử hàm không xác định khắp nơi $\emptyset$ (tính bởi chương trình không bao giờ dừng ở đầu vào nào) không có tính chất $P$ — nếu không thì lập luận với tính chất bù $\lnot P$ , tính chất này quyết định được đúng khi $P$ quyết định được. Vì $P$ không tầm thường, cố định một chương trình $e_0$ mà hàm $\varphi_{e_0}$ của nó có tính chất $P$ .

Giả sử phản chứng $P$ quyết định được bởi thuật toán $D$ nào đó (cho một chỉ số chương trình, $D$ dừng và báo cáo đúng liệu hàm của chương trình đó có tính chất $P$ hay không). Ta quy về bài toán dừng bởi $P$ , mâu thuẫn với Định lý 1.

Cho một cặp $(e,x)$ bất kỳ, xây dựng hiệu quả (bằng thao tác văn bản đơn giản — định lý s-m-n của Kleene) một chương trình mới $e'$ mà, với đầu vào $y$ bất kỳ: trước hết mô phỏng chương trình $e$ chạy trên đầu vào $x$ ; nếu mô phỏng đó dừng, thì $e'$ tiếp tục mô phỏng chương trình $e_0$ trên đầu vào $y$ và cho ra bất cứ gì nó cho ra.

Xét hai khả năng. Nếu $e$ dừng ở $x$ : mô phỏng $e$ trên $x$ kết thúc, nên $e'$ sau đó hành xử y hệt $e_0$ ở mọi đầu vào, tức $\varphi_{e'}=\varphi_{e_0}$ — hàm này có tính chất $P$ (vì $P$ ngữ nghĩa, chỉ phụ thuộc hàm được tính, và $\varphi_{e_0}$ có $P$ ). Nếu $e$ không dừng ở $x$ : mô phỏng $e$ trên $x$ không bao giờ kết thúc, nên $e'$ không bao giờ tới bước mô phỏng $e_0$ ở bất kỳ đầu vào $y$ nào; do đó $\varphi_{e'}$ là hàm không xác định khắp nơi $\emptyset$ , theo giả định không có tính chất $P$ .

Vậy: $e$ dừng ở $x$ $\iff$ $\varphi_{e'}$ có tính chất $P$ $\iff$ $D(e')$ trả lời "có". Vì $(e,x)\mapsto e'$ tính được, thuật toán "tính $e'$ từ $(e,x)$ , rồi chạy $D(e')$ " sẽ quyết định được bài toán dừng — mâu thuẫn Định lý 1. Vậy không tồn tại $D$ như thế: $P$ không quyết định được. $\blacksquare$

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Trình tối ưu hóa biên dịch phải quyết định những điều như "đoạn mã này có tới được không?" hay "giá trị biến này có quan trọng không?" — theo định lý Rice, những điều này không quyết định được một cách tổng quát, đó chính xác là lý do trình biên dịch thật dùng xấp xỉ bảo thủ (có thể giữ lại mã chết thật sự thay vì mạo hiểm xóa mã sống). Hàm Busy Beaver $BB(n)$ — số bước lớn nhất một máy Turing $n$ -trạng thái dừng có thể thực hiện trước khi dừng — là một hàm cụ thể, không tính được: các giá trị đã biết là $BB(1)=1$ , $BB(2)=6$ , $BB(3)=21$ , $BB(4)=107$ , và năm 2024 dự án hợp tác Busy Beaver Challenge (dẫn dắt bởi Tristan Stérin và cộng sự, với chứng minh được xác minh bằng Coq từ một người đóng góp dùng bút danh "mxdys") xác lập $BB(5)=47{,}176{,}870$ — cho thấy ngay cả câu hỏi tổ hợp "đơn giản" này cũng chỉ tính được từng trường hợp, không bao giờ bằng một thuật toán tổng quát.

Ví dụ: Khai triển hàm Ackermann $A(2,2)$

Dùng các quy tắc $A(0,n)=n+1$ , $A(m,0)=A(m-1,1)$ với $m>0$ , và $A(m,n)=A(m-1,A(m,n-1))$ với $m,n>0$ , tính $A(2,2)$ từng bước, và giải thích vì sao hàm Ackermann toàn phần nhưng không đệ quy nguyên thủy.

Lời giải

$A(2,2)=A(1,A(2,1))$ theo quy tắc thứ ba. Trước hết cần $A(2,1)=A(1,A(2,0))$ , và $A(2,0)=A(1,1)$ theo quy tắc thứ hai.

$A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3$ (khai triển hai lần bằng quy tắc thứ hai và thứ nhất). Vậy $A(2,0)=A(1,1)=3$ , nên $A(2,1)=A(1,3)$ .

$A(1,3)=A(0,A(1,2))$ , và $A(1,2)=A(0,A(1,1))=A(0,3)=4$ . Vậy $A(1,3)=A(0,4)=5$ . Nên $A(2,1)=5$ .

Quay lại đỉnh: $A(2,2)=A(1,A(2,1))=A(1,5)=A(0,A(1,4))$ ; khai triển $A(1,4)=A(0,A(1,3))=A(0,5)=6$ ; nên $A(1,5)=A(0,6)=7$ . Vậy $A(2,2)=7$ .

Hàm Ackermann được chứng minh toàn phần (nó luôn cuối cùng quy về trường hợp $A(0,n)$ ), nên nó thuộc lớp hàm đệ quy tổng quát — nhưng nó tăng nhanh hơn mọi hàm đệ quy nguyên thủy (ví dụ $A(3,n)=2^{n+3}-3$ , $A(4,n)$ đã là tháp lũy thừa). Vì có thể chỉ ra mọi hàm đệ quy nguyên thủy cuối cùng bị chặn bởi một $A(k,\cdot)$ cố định nào đó, không hàm đệ quy nguyên thủy nào có thể bằng chính $A$ — một lập luận thống trị kiểu đường chéo, không phải toán tử $\mu$ , mới là điều đặt Ackermann ra ngoài đệ quy nguyên thủy dù nó toàn phần.

Ví dụ: Quy bài toán dừng về "chương trình này có in hello không?"

Chứng minh bài toán "cho chương trình $e$ , chạy $e$ (không đầu vào) có bao giờ in chuỗi `hello` không?" không quyết định được, bằng quy về trực tiếp từ bài toán dừng — không dùng định lý Rice.

Lời giải

Giả sử phản chứng thuật toán $Q(e)$ quyết định được việc chạy $e$ có bao giờ in `hello` không. Ta dùng $Q$ để quyết định bài toán dừng, mâu thuẫn Định lý 1.

Cho chương trình $e$ và đầu vào $x$ bất kỳ, xây hiệu quả chương trình mới $e'$ (không cần đầu vào) mà: mô phỏng $e$ chạy trên $x$ ; nếu mô phỏng đó dừng, $e'$ tiếp đó in `hello` rồi dừng.

Nếu $e$ dừng ở $x$ : mô phỏng kết thúc, nên $e'$ tới bước in và in `hello`. Nếu $e$ không dừng ở $x$ : mô phỏng không bao giờ kết thúc, nên $e'$ không bao giờ tới bước in và không bao giờ in `hello`.

Vậy $e$ dừng ở $x$ $\iff$ $Q(e')$ trả lời "có". Vì $(e,x)\mapsto e'$ tính được, "xây $e'$ rồi chạy $Q(e')$ " quyết định được bài toán dừng — mâu thuẫn Định lý 1. Vậy $Q$ không thể tồn tại: bài toán "in hello" không quyết định được. (Đây chính là khuôn mẫu phân tích trình biên dịch: "dòng mã này có bao giờ được tới không" có cùng hình dạng.)

Ghi chú lịch sử

Năm 1936, bài báo "On Computable Numbers, with an Application to the Entscheidungsproblem" của Alan Turing giới thiệu máy Turing và chứng minh bài toán dừng không quyết định được, độc lập giải quyết bài toán quyết định của Hilbert cùng lúc với lập luận phép tính lambda tương đương của Alonzo Church cùng năm — sự ra đời của luận đề Church–Turing. Wilhelm Ackermann đã công bố hàm tăng nhanh của mình từ 1928 (ban đầu được Ackermann và David Hilbert nghiên cứu) như ví dụ đầu tiên đã biết về hàm khả tính toàn phần mà không đệ quy nguyên thủy. Henry Gordon Rice chứng minh định lý của mình năm 1953, tổng quát hóa tính không quyết định từ một bài toán cụ thể thành cả một họ.

Alan Turing

Dùng $A(1,n)=n+2$ , $A(1,3)$ bằng bao nhiêu?

Điều nào sau đây là hệ quả của tính không quyết định của bài toán dừng đối với thiết kế trình biên dịch?

Định lý Rice KHÔNG áp dụng cho tính chất nào?

Trong chứng minh đường chéo của tính không quyết định của bài toán dừng, điều gì dẫn tới mâu thuẫn?

Tài liệu tham khảo

Wikipedia contributors (2024). Halting problem
Wikipedia contributors (2024). Rice's theorem
Wikipedia contributors (2024). Ackermann function