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

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$