Alan Turing và Sức Mạnh của Tư Duy Tiêu Cực

Phiên bản gốc của câu chuyện này xuất hiện trên Tạp chí Quanta.

Thuật toán đã trở nên phổ biến. Chúng tối ưu hóa việc di chuyển của chúng ta, xử lý thanh toán và điều phối luồng lưu lượng internet. Dường như đối với mọi vấn đề có thể được mô tả bằng thuật ngữ toán học chính xác, đều có một thuật toán có thể giải quyết nó, ít nhất là về nguyên tắc.

Nhưng điều đó không đúng—một số vấn đề dường như đơn giản có thể không bao giờ được giải quyết bằng thuật toán. Nhà khoa học máy tính tiên phong Alan Turing đã chứng minh sự tồn tại của những vấn đề 'không thể tính toán' như vậy gần một thế kỷ trước, trong cùng một bài báo mà ông sáng tạo ra mô hình toán học của máy tính, khởi đầu cho khoa học máy tính hiện đại.

Turing đã chứng minh kết quả đột phá này bằng cách sử dụng một chiến lược đầy nghịch lý: Ông xác định một vấn đề đơn giản chỉ cần phủ nhận mọi cố gắng giải quyết nó.

“Tôi hỏi bạn đang làm gì, và sau đó tôi nói, ‘Không, tôi sẽ làm điều gì đó khác,’” nói Rahul Ilango, một sinh viên sau đại học tại Viện Công nghệ Massachusetts nghiên cứu khoa học máy tính lý thuyết.

Chiến lược của Turing dựa trên một kỹ thuật toán học được gọi là đường chéo có một lịch sử lừng lẫy. Dưới đây là một bản tóm tắt đơn giản về logic đằng sau bằng chứng của ông.

Lý Thuyết Chuỗi 

Đường chéo bắt nguồn từ một mẹo thông minh để giải quyết một vấn đề đơn điệu liên quan đến chuỗi bit, mỗi chuỗi có thể là 0 hoặc 1. Cho một danh sách các chuỗi như vậy, đều có chiều dài như nhau, bạn có thể tạo ra một chuỗi mới không có trong danh sách không?

Chiến lược phổ biến nhất là xem xét từng chuỗi có thể có một cách lượt. Giả sử bạn có năm chuỗi, mỗi chuỗi dài năm bit. Bắt đầu bằng cách quét danh sách để tìm 00000. Nếu không có, bạn có thể dừng; nếu có, bạn chuyển sang 00001 và lặp lại quá trình. Điều này đơn giản đến mức đủ, nhưng chậm đối với danh sách dài của chuỗi dài.

Đường chéo là một cách tiếp cận khác xây dựng một chuỗi thiếu bit theo từng bit. Bắt đầu với bit đầu tiên của chuỗi đầu tiên trong danh sách và đảo ngược nó—đó sẽ là bit đầu tiên của chuỗi mới của bạn. Sau đó đảo ngược bit thứ hai của chuỗi thứ hai và sử dụng nó làm bit thứ hai của chuỗi mới, và lặp lại cho đến khi bạn đến cuối danh sách. Những bit bạn đảo ngược đảm bảo rằng chuỗi mới khác biệt từ mọi chuỗi trên danh sách ban đầu ít nhất một nơi. (Chúng cũng tạo ra một đường chéo qua danh sách chuỗi, cho phép kỹ thuật mang tên đường chéo.)

Đường chéo chỉ cần xem xét một bit từ mỗi chuỗi trên danh sách, nên thường nhanh hơn nhiều so với các phương pháp khác. Nhưng sức mạnh thực sự của nó nằm ở cách nó chơi tốt với vô cực.

“Bây giờ, chuỗi có thể vô cực; danh sách cũng có thể vô cực—nó vẫn hoạt động,” nói Ryan Williams, một nhà khoa học máy tính lý thuyết tại MIT.

Người đầu tiên khai thác sức mạnh này là Georg Cantor, người sáng lập ra lĩnh vực toán học của lý thuyết tập hợp. Năm 1873, Cantor sử dụng đường chéo để chứng minh rằng một số vô cực lớn hơn số khác. Sáu thập kỷ sau đó, Turing điều chỉnh phiên bản đường chéo của Cantor vào lý thuyết tính toán, mang lại cho nó một hương vị phản đối đặc biệt.

Trò Chơi Hạn Chế

Turing muốn chứng minh sự tồn tại của các vấn đề toán học mà không có thuật toán nào có thể giải quyết—nghĩa là, các vấn đề có đầu vào và đầu ra được xác định rõ nhưng không có thủ tục đảm bảo cho việc đi từ đầu vào đến đầu ra. Anh làm nhiệm vụ mơ hồ này trở nên dễ quản lý hơn bằng cách tập trung đặc biệt vào các vấn đề quyết định, trong đó đầu vào có thể là bất kỳ chuỗi 0 và 1 nào và đầu ra là 0 hoặc 1.

Xác định xem một số có phải là số nguyên tố (chỉ chia hết cho 1 và chính nó) là một ví dụ về vấn đề quyết định—với một chuỗi đầu vào biểu thị một số, đầu ra đúng là 1 nếu số đó là số nguyên tố và 0 nếu không phải. Một ví dụ khác là kiểm tra chương trình máy tính để phát hiện lỗi cú pháp (tương đương với các lỗi ngữ pháp). Ở đó, các chuỗi đầu vào biểu thị mã cho các chương trình khác nhau—tất cả các chương trình có thể được biểu thị như vậy, vì đó là cách chúng được lưu trữ và thực thi trên máy tính—và mục tiêu là xuất ra 1 nếu mã chứa lỗi cú pháp và 0 nếu không chứa.

Một thuật toán giải quyết một vấn đề chỉ nếu nó tạo ra đầu ra đúng cho mọi đầu vào có thể có—nếu nó thất bại ít nhất một lần, nó không phải là thuật toán chung cho vấn đề đó. Thông thường, bạn sẽ đầu tiên xác định vấn đề bạn muốn giải quyết và sau đó cố gắng tìm thuật toán giải quyết nó. Turing, tìm kiếm các vấn đề không thể giải quyết, đã đảo ngược logic này—anh ấy tưởng tượng một danh sách vô cùng của tất cả các thuật toán có thể có và sử dụng đường chéo để xây dựng một vấn đề cứng nhắc mà sẽ làm thất bại mọi thuật toán trên danh sách.

Hãy tưởng tượng một trò chơi 20 câu hỏi bị sắp đặt, nơi thay vì bắt đầu với một đối tượng cụ thể trong tâm trí, người trả lời nghĩ ra một lý do để từ chối từng câu hỏi. Đến cuối trò chơi, họ đã mô tả một đối tượng được định nghĩa hoàn toàn bởi những đặc tính nó thiếu.

Bằng chứng chéo của Turing là một phiên bản của trò chơi này, trong đó các câu hỏi chạy qua danh sách vô hạn của các thuật toán có thể có, liên tục hỏi, “Liệu thuật toán này có thể giải quyết vấn đề mà chúng ta muốn chứng minh là không thể tính toán được không?”

“Điều này có phần như là ‘vô cực câu hỏi,’” Williams nói.

Để chiến thắng trò chơi, Turing cần phải tạo ra một vấn đề mà câu trả lời là không đối với mọi thuật toán. Điều đó có nghĩa là xác định một đầu vào cụ thể khiến cho thuật toán đầu tiên xuất ra câu trả lời sai, một đầu vào khác khiến cho thuật toán thứ hai thất bại, và cứ tiếp tục như vậy. Anh ấy tìm ra những đầu vào đặc biệt đó bằng một mánh khéo léo tương tự như một mánh khéo léo mà Kurt Gödel vừa sử dụng để chứng minh rằng các phát biểu tự tham chiếu như “câu nói này không thể chứng minh” gây khó khăn cho cơ sở của toán học.

Hiểu biết quan trọng nhất là mọi thuật toán (hoặc chương trình) có thể được biểu diễn dưới dạng một chuỗi các số 0 và 1. Điều này có nghĩa, như trong ví dụ về chương trình kiểm tra lỗi, rằng một thuật toán có thể lấy mã của một thuật toán khác làm đầu vào. Theo nguyên tắc, một thuật toán thậm chí có thể lấy mã của chính nó làm đầu vào.

Với cái nhìn này, chúng ta có thể định nghĩa một vấn đề không thể tính toán như trong bằng chứng của Turing: “Cho một chuỗi đầu vào đại diện cho mã của một thuật toán, đầu ra là 1 nếu thuật toán đó xuất ra 0 khi mã của nó là đầu vào; nếu không, đầu ra là 0.” Mọi thuật toán cố gắng giải quyết vấn đề này sẽ tạo ra đầu ra sai ít nhất một lần trên một đầu vào—nói cách khác, đầu vào tương ứng với mã của nó. Điều đó có nghĩa là vấn đề nghịch đảo này không thể được giải quyết bởi bất kỳ thuật toán nào.

Những Gì Phủ Nhận Không Thể Làm

Những nhà khoa học máy tính vẫn chưa xong với chứng minh chéo. Năm 1965, Juris Hartmanis và Richard Stearns điều chỉnh lập luận của Turing để chứng minh rằng không phải tất cả các vấn đề có thể tính toán đều được tạo ra bằng nhau—một số vấn đề nội tại khó hơn so với các vấn đề khác. Kết quả này đã khởi đầu lĩnh vực lý thuyết độ phức tạp tính toán, nghiên cứu về độ khó của các vấn đề tính toán.

Nhưng lý thuyết độ phức tạp cũng đã bộc lộ giới hạn của phương pháp phủ nhận của Turing. Năm 1975, Theodore Baker, John Gill, và Robert Solovay chứng minh rằng nhiều vấn đề mở trong lý thuyết độ phức tạp không thể bao giờ được giải quyết chỉ thông qua phương pháp chéo. Trong số đó, vấn đề nổi tiếng P so với NP đặt câu hỏi liệu liệu tất cả các vấn đề có giải pháp kiểm tra dễ dàng có thể dễ dàng giải quyết với thuật toán khéo léo phù hợp hay không.

Những điểm mù của chéo chéo là hậu quả trực tiếp của mức độ trừu tượng cao khiến nó trở nên mạnh mẽ như vậy. Bằng chứng của Turing không liên quan đến bất kỳ vấn đề không thể tính toán nào có thể phát sinh trong thực tế—thay vào đó, nó pha trộn ra một vấn đề như vậy ngay lập tức. Các chứng minh chéo chéo khác cũng giữ vững từ thế giới thực, nên chúng không thể giải quyết những vấn đề mà chi tiết thế giới thực quan trọng.

“Chúng xử lý tính toán từ xa,” Williams nói. “Tôi tưởng tượng một người đang xử lý virus và tiếp cận chúng thông qua một hộp găng tay nào đó.”

Sự thất bại của chéo chéo là dấu hiệu sớm cho thấy việc giải quyết vấn đề P so với NP sẽ là một hành trình dài. Nhưng mặc dù có nhược điểm, chéo chéo vẫn là một trong những công cụ chính trong kho vũ khí của các nhà lý thuyết độ phức tạp. Năm 2011, Williams đã sử dụng nó cùng với nhiều kỹ thuật khác để chứng minh rằng một mô hình giới hạn của tính toán không thể giải quyết một số vấn đề cực kỳ khó—một kết quả mà các nhà nghiên cứu đã khám phá trong 25 năm. Đó không phải là giải quyết P so với NP, nhưng vẫn đại diện cho một tiến triển đáng kể.

Nếu bạn muốn chứng minh rằng một điều gì đó không khả thi, đừng đánh giá thấp sức mạnh của việc chỉ cần nói không.

Bài viết gốc được tái in với sự cho phép từ Quanta Magazine, một tờ báo độc lập về biên tập của Simons Foundation với sứ mệnh tăng cường sự hiểu biết công bố về khoa học bằng cách đưa ra các phát triển nghiên cứu và xu hướng trong toán học cũng như các ngành khoa học tự nhiên và sinh học.