“Không. Hồi đó khoa Triết Học không có ai quan tâm đến mấy thứ ấy.”
[
Bản chất của bài toán Hilbert số 10 nằm ở các câu hỏi: “các hàm nào có thể tính toán được ?”, và “thế nào là một giải thuật tính một hàm, hay nói cách khác: tính toán là gì ?”. Từ đầu thế kỷ 20, các nhà logic học đã nhận ra rằng một số rất lớn các hàm toán học đều có thể được định nghĩa bằng phương pháp đệ qui (và vài luật đơn giản khác). Tuy vậy, có một số hàm không định nghĩa được theo cách đệ qui sơ đẳng này (primitive recursive), ví dụ như hàm Ackermann vì nó tăng siêu nhanh. Thế là các nhà logic học tập trung đi tìm các hệ thống tạo hàm mạnh hơn, với mục tiêu tối hậu là hệ thống ấy có thể tạo được tất cả các hàm tính toán được.
Alonzo Church (1903-1995) sáng tạo ra hệ thống giải tích lambda (lambda calculus) cho mục tiêu này. Church và Gödel thảo luận về giải tích lambda ở đại học tổng hợp Princton. Lúc đầu Gödel không thích món giải tích này lắm vì Gödel nghĩ hệ thống
Một giải thuật thật ra cũng là một hàm số (hay ánh xạ), ví dụ như giải thuật xếp thứ tự chuyển một dãy số thành dãy có thứ tự. Khi nói đến “tính toán được”, ta thực sự muốn nói là “có giải thuật để tính”. Vì thế, luận đề Church cũng có thể được phát biểu là: “cái gì tính được bằng một giải thuật thì tính được bằng giải tích lambda”. Chú ý rằng “luận đề” có ý nghĩa như một định nghĩa, một tiên đề, không cần phải chứng minh. Vấn đề là ta có tin rằng giải tích lambda nắm bắt được mấu chốt của khái niệm “giải thuật” hay không mà thôi. Năm 1936, Church dùng luận đề này để giải quyết entscheidungsproblem của Hilbert. Ông thiết kế hai biểu thức trong giải tích lambda mà sự tương đương của chúng không thể tính được bằng một hàm đệ qui. Nói cách khác, có các phát biểu toán học không thể chứng minh được một cách cơ bắp (bằng giải thuật).
Giải tích lambda và các hàm đệ qui có ảnh hưởng sâu sắc đến ngành trí tuệ nhân tạo. Các ngôn ngữ hàm (functional languages) thuộc họ Lisp (như Scheme và Common Lisp) đều dựa trên giải tích lambda và định nghĩa đệ qui. (Xem thêm trang nhà của giáo sư John McCarthy.) Bản thân tôi có học một năm về logic với giáo sư Wayne Richter ở đại học
3 Comments
Trong bài này sau khi tham khảo trên mathworld, em có một số câu hỏi:
+) Tại sao hàm Ackermann lại không là primitive recursive ? Có phải do nó không tồn tại một hàm chặn trên tường minh hay lý do gì khác ?
+) Tại sao ta không biểu diễn được hàm Ackermann qua vòng lặp while-do mà chỉ biểu diễn được qua vòng lặp do-while ? (vì theo em biết thì hai vòng lặp này chỉ hơn kém nhau tối đa một lần lặp).
Mong anh trả lời giúp em thắc mắc này ^^
Hồi trước khi sang Mỹ, nhóm chúng tôi gồm 3 người, nhờ một anh giảng viên khoa toán ĐH sư phạm đến giảng khoảng 2 tháng, để bổ túc kiến thức. Anh ấy cũng giảng về lý thuyết tập hợp, giải thuật đường chéo này. Ngoài ra còn một số môn khác nữa.
Điều tôi muốn nói ở đây là ở VN, một số giảng viên có thể bổ sung kiến thức cho các sinh viên Phd trước khi đi du học. Và họ giảng rất hay. Tôi nghĩ là nghiên cứu toán ở VN kém, nhưng giảng dạy kiến thức cơ bản kể cả bậc sau đại học, cho các ngành ứng dụng, không tồi chút nào.
Nhiều professor có thể tự đọc, tự nghiên cứu được. Nhưng đối với các sinh viên Phd bình thường, trong quá trình học ở nước ngoài ít thời gian tự nghiên cứu các kiến thức bổ trợ, thì có thể tận dụng những nguồn cung cấp kiến thức ngay từ khi ở trong nước. Nhiều giảng viên trong có nhu cầu đi dạy thêm, trong khi người cần học, thì lại chẳng chịu đi tìm.
Thậm chí sau đó có thể hợp tác làm paper. Ngành khác thì tôi không biết, nhưng ngành kinh tế, tài chính, tôi thấy có một số paper hợp tác giữa sinh viên Phd ở Mỹ và sinh viên ở nước bản địa từng được đăng trên top journal.
Xin lỗi vì tôi post nhầm, đáng lẽ phải post ở mục Chỉ tại Cantor (3) bên kia.