Blog Khoa Học Máy Tính

“Tầm mắt của chúng ta chẳng xa gì lắm, mà ta đã thấy bao nhiêu việc để làm.”

[Alan Turing - 1950]

Việc ai đó có tin là Church đã giải được entscheidungsproblem hay không phụ thuộc vào việc người đó có tin rằng giải tích lambda thật sự bao gồm những gì tính toán được hay không. Hồi đó Gödel và nhiều người khác chưa thật sự tin là các hàm tính được đều tính được bằng giải tích lambda. Turing thay đổi niềm tin này. Khoảng năm 1935, 1936, Turing cũng tìm được một phương pháp để trả lời entscheidungsproblem, không biết rằng Church cũng đang làm bài này và đã gần xong. Cuối cùng Church làm xong trước Turing khoảng 6 tháng – có một transcript một cuộc phỏng vấn Church ở UCLA có đề cập đến điều này. Tuy vậy, phương pháp của Church và Turing khác nhau hoàn toàn và chúng có giá trị độc lập.

Phương pháp của Turing có thể được tóm tắt như sau. Entscheidungsproblem đại khái nói: “tìm một giải thuật để quyết định xem một phát biểu logic có thể chứng minh được hay không”.

• Trước hết, Turing sáng tạo ra một mô hình “máy” để nắm bắt khái niệm giải thuật. Cái máy của ông – mà ta sẽ gọi là máy Turing (Turing Machine) từ giờ trở đi – được thiết kế để bắt chước quá trình tính toán một cách cơ học của con người (ví dụ như trẻ nhỏ có thể cộng và nhân hai số trên giấy mà không hiểu tại sao làm thế thì đúng).
• Sau đó, ông thuyết phục chúng ta là máy Turing có thể tính tất cả các hàm tính toán được bằng cách thiết kế cái máy của ông cho nó tính rất nhiều hàm khác nhau, rồi chứng minh rằng tất cả các hàm tính được bằng giải tích lambda hay các hàm đệ qui Herbrand-Gödel đều có thể tính được bằng máy Turing. Dịp khác tôi sẽ viết chi tiết về máy Turing. Để cảm nhận được máy Turing mạnh như thế nào, ta nên biết rằng tất cả các chương trình máy tính hiện đại đều tương đương với một máy Turing nào đó. Mỗi máy Turing tương đương với một chương trình viết bằng ngôn ngữ lập trình yêu thích nhất của bạn. Một chương trình chơi cờ vua viết bằng Java là một máy Turing, chương trình Kazaa để download nhạc/phim là một máy Turing, chương trình mô phỏng big-bang là một máy Turing.
• Cuối cùng, ông thiết kế một bài toán mà không máy Turing nào có thể tính được, gọi là bài toán dừng (halting problem). Có lẽ đến đây bạn cũng có thể đoán được là để chứng minh bài toán dừng không quyết định được bằng máy Turing thì ông đã dùng lập luận đường chéo của Cantor!

Turing cũng có luận đề tương tự như luận đề của Church, và Kleene gọi chung là luận đề Church-Turing. Trong ngôn ngữ hiện đại luận đề Church-Turing nói rằng “máy Turing nắm bắt chính xác khái niệm giải thuật, hàm nào tính được bằng một giải thuật thì tính được bằng máy Turing và ngược lại”. Máy Turing hiện nay là công cụ phổ biến nhất để nghiên cứu độ phức tạp tính toán. Người ta đã sáng chế ra nhiều mô hình tính toán khác như máy truy cập ngẫu nhiên (Random Access Machine – RAM) của von Neumann, hệ thống Post, giải thuật Markov, logic tổ hợp (combinatory logic), giải tích lambda, các hàm đệ qui Herbrand-Godel, máy thanh ghi vô hạn (unlimited register machine), máy tính xử lý song song (parallel computers), máy tính lượng tử (quantum computer), vân vân, nhưng không có mô hình nào mạnh hơn máy Turing về khả năng tính toán. Chú ý rằng ta vẫn chưa định nghĩa thật rõ ràng thế nào là “khả năng tính toán”, “hàm tính được”. Bạn có thể hiểu nôm na sự tính toán là một thủ tục rõ ràng, không có chỗ nào mơ hồ, có thể về nguyên tắc làm được bởi một người bình thường nếu có đủ thời gian và giấy nháp.

Đóng góp của Turing vào khoa học máy tính không dừng ở đó. Năm 1950, bài báo “máy tính và sự thông minh” (Computing Machinary and Intelligence) của ông là một trong những bài báo đặt nền móng cho ngành trí tuệ nhân tạo. Phép thử Turing (Turing test) vẫn là một thách thức khổng lồ cho cả ngành khoa học máy tính. Sẽ có các bài khác về trí tuệ nhân tạo trong blog này và chắc chắn đề tài này sẽ còn được thăm lại trong một dịp gần đây.

Tầm nhìn của Turing, không xa lắm đối với ông, nhưng đã vượt qua cả thời đại chúng ta.

Chủ đề: Lý thuyết tính toán |