Hướng đến tương lai

Những bài viết này tôi sử dụng lại từ GS. Ngô Quang Hưng, CSE of Buffalo.

Người truyền cảm hứng cho ước mơ trên là tiến sĩ Richard M. Stallman (thường được gọi là RMS), cha đẻ của phong trào phần mềm miễn phí của thế giới. Tôi không thể nghĩ ra một lập trình viên, một hacker nào giỏi hơn RMS (kể cả Linus Torvalds và Bill Gates). Hệ điều hành Linux đáng lẽ phải được gọi là hệ điều hành GNU với lõi Linux (như kiểu máy tính Dell với bộ vi xử lý Intel). Coi Linux như một hệ điều hành đứng riêng là một trong những hiểu lầm cực kỳ đáng tiếc, rất tiếc là khá phổ biến. GNU là công trình con đẻ của RMS. Nhưng thôi, chuyện này ta để dịp khác.

Không chỉ là bậc thầy về kỹ thuật máy tính, RMS có ước mơ làm cho cả thế giới có thể dùng, sửa đổi, phân phối, thậm chí buôn bán, các phần mềm miễn phí. Theo nhiều nghĩa, triết lý này của ông tương đồng với ý tưởng rằng tri thức của nhân loại phải đến với chúng ta nhanh chóng và không tốn kém. Việc các nước chậm phát triển mua phần mềm của các tập đoàn lớn, đối với RMS, là một dạng thuộc địa hóa hiện đại. Người ta sẽ bị ràng buộc một cách rất khó chịu vào các phần mềm đắt tiền này, mà lại không biết trong chúng thật sự viết gì (ví dụ có thể có phần gián điệp cài đặt vào). RMS cũng đứng đầu phong trào chống software patents, một trong những loại patent vô lý nhất trên đời.

Rồi tôi nghĩ đến một viễn cảnh lớn hơn, khi mà các bài giảng, sách vở ở tất cả các bậc học ở Việt Nam cũng đều miễn phí. Ta sẽ có một thư viện online khổng lồ. Kiến thức sẽ đến với bất kỳ ai sau một cái click con chuột. Chẳng phải đấy là mục đích tối hậu của phổ cập giáo dục? Tôi đi tìm lòng vòng trên Internet và đã tìm ra bốn dự án có chung chí hướng này.

Dự án thứ nhất là của nhà xuất bản kỹ thuật máy tính số một thế giới: nhà xuất bản O'Reilly với "dự án sách mở" ( Openbook Project). Các quyển sách ở đây được đăng ký với vài loại lisence khác nhau, như GNU Free Documentation Lisence, Open Publication Lisence, GNU General Public Lisence , và bản thân O'Reilly cũng có rất nhiều sách theo Creative Commons Founders' Copyright. Về tinh thần, các lisences/copyright này đều giống ước mơ của RMS.

Dự án thứ hai là tự điển bách khoa toàn thư miễn phí Wikipedia. Với khoảng 300,000 đề mục, Wikipedia là tự điển bách khoa toàn thư lớn nhất thế giới. (Quyển bách khoa toàn thư của Britanica có khoảng 85,000 đề mục – số liệu tháng 7/2004.) Chất lượng của Wikipedia rất cao, và tôi dùng nó thường xuyên. Mô hình nhiều người đóng góp mang tính phân bố (distributed contribution) của Wikipedia là mô hình đáng học tập cho việc phổ cập kiến thức.

Dự án thứ ba là dự án gnowledge của trung tâm giáo dục khoa học Homi Bhabha của Ấn do giáo sư Nagarjuna chủ xướng. Tinh thần của dự án này cũng là kiến thức miễn phí.

Dự án cuối cùng là dự án Open Courseware của viện công nghệ Massachusetts. Ở đây rất nhiều bài giảng của các giáo sư hàng đầu thế giới được để mở cho mọi người cùng truy cập.

Một thư viện online khổng lồ bằng tiếng Việt (dĩ nhiên không phải chỉ có sách giáo khoa). Sách vở, bài giảng, trao đổi miễn phí. Học sinh nghèo nhất cũng có khả năng liên lạc với bậc thầy nổi tiếng nhất. Một môi trường học tập, tham khảo, mà ai cũng có cơ hội tham gia, bổ túc cho nhau, học hỏi lẫn nhau. Hay cũng chỉ là một mơ ước, và chúng ta lại đi chậm hơn thế giới?

Cá nhân tôi thì khi nào rảnh rỗi đều viết vài trang sách và bài giảng tiếng Việt. Bạn sẽ thấy một quyển sách, vài bài giảng miễn phí về một nhánh nhỏ của khoa học máy tính trong một ngày không xa. Tất cả có thể bắt đầu bằng một ước mơ

 

 

Các câu hỏi phỏng vấn (4)

 

10. Cho một mảnh giấy hình chữ nhật với một lỗ hổng hình chữ nhật ở giữa.
    Hỏi: Dùng dao cắt mảnh giấy một nhát như thế nào để có hai nửa có diện tích bằng nhau?
11. Có 500 cái cửa nằm dọc theo một hành lang đánh số từ 1 đến 100. Lúc đầu các cửa đều đóng. Có 500 người xếp hàng đi dọc hành lang. Anh thứ nhất mở tất cả các cửa; anh thứ hai chuyển trạng thái (mở thành đóng, đóng thành mở) các cửa 2, 4, 6, ...; anh thứ ba chuyển trạng thái các cửa 3, 6, 9, ...; cứ như vậy đến anh thứ 500 chuyển trạng thái cửa 500.
    Hỏi: cuối cùng có bao nhiêu cửa đóng?
12. Có hai căn phòng nằm cạnh nhau nhưng không thông nhau, và đứng bên này không thấy bên kia. Phòng 1 có ba cái đèn bóng tròn. Phòng 2 có ba công tắc của ba đèn ở phòng 1. Bạn là người lạ, được dẫn vào phòng 2 trước, được quyền nghịch ngợm tắt mở công tắc tùy ý. Sau đó bạn được sang phòng 1 kiểm tra đèn.
    Hỏi: nghịch thế nào ở phòng 2 để biết công tắc nào tương ứng với đèn nào?

Các câu hỏi phỏng vấn (3)

 

7. Cho hai sợi dây dài, làm bằng các vật liệu khác nhau, có mật độ vật chất khác nhau ở các điểm khác nhau của từng sợi. Cho biết mỗi sợi dây cháy trong đúng một giờ thì hết. Dùng hai sợi dây (và diêm) để đo 45 phút.
8. Cho hai hình lập phương. Ta phải gán các chữ số 0-9 (mỗi mặt một số) ra sao để có thể dùng hai hình lập phương biểu diễn được tất cả các ngày trong tháng.

Những điểm nào trên quả địa cầu (giả sử là đúng hình cầu) có tính chất sau đây: đi về phía Nam 1km, sau đó về phía Tây 1km, sau đó về phía Bắc 1km thì quay lại điểm cũ.

Các câu hỏi phỏng vấn (2)

4. Chỉ với các phép tính cộng, trừ, nhân, chia, các hàm lượng giác, phép lũy thừa, và phép lấy căn, cùng với ba số 2, làm thế nào để viết một biểu thức định trị ra 2005? (Gợi ý: 2005 không có gì đặc biệt, số nguyên dương nào cũng được.) [Câu này tôi biết qua chị Hà Dương, lúc giải ra rất thích! Đơn giản và độc đáo]
5. Bụt, diêm vương, và Tèo đứng trước mặt bạn. Bụt và diêm vương cái gì cũng biết. Tèo thì cái biết cái không. Bụt luôn nói thật, diêm vương luôn nói dối. Với 3 câu hỏi có/không, mỗi câu chỉ hỏi một trong ba đối tượng, xác định ai là ai.

Cho a và b là các số nguyên dương, nguyên tố cùng nhau. Tìm công thức tính số nguyên lớn nhất không thể viết dưới dạng ax+by, trong đó x và y là các số nguyên không âm.

Các câu hỏi phỏng vấn (1)

Microsoft nổi tiếng là có các câu hỏi phỏng vấn nhân viên mới mang tính kỹ thuật theo dạng đố "mẹo" (đa số là về thuật toán hoặc lập trình C/C++). Có nhiều bộ sưu tập các câu hỏi dạng này đã từng được hỏi ở các cuộc phỏng vấn ở Microsoft. Gần đây Google cũng phỏng vấn theo kiểu tương tự. Mỗi câu trả lời chỉ được cho khoảng 5-10 phút suy nghĩ. Đôi khi người ta quan tâm đến quá trình suy nghĩ của bạn hơn là bản thân câu trả lời.

Trong chuỗi bài này tôi sẽ nêu chọn lọc một số câu hỏi tôi thích nhất. Các câu hỏi được chọn không nhất thiết là khó nhất, tiêu chuẩn là gọn gàng và đẹp.

1. Cho một danh sách liên kết đơn (simple linked list) hữu hạn. Có hai trường hợp: một là cuối danh sách trỏ về NULL, hai là trỏ về một phần tử đã gặp - tạo nên một vòng tròn trong danh sách.
   Ví dụ trường hợp 1: A --> B --> C --> D --> NULL .
   Ví dụ trường hợp 2: A --> B --> C --> D --> E --> F --> C.
   Cho trước một con trỏ vào một danh sách liên kết đơn L nào đó, hữu hạn nhưng có thể có độ dài tùy ý. Làm thế nào để kiểm tra nhanh nhất nếu danh sách L thuộc trường hợp 1 hay trường hợp 2, với điều kiện là ta chỉ được dùng vài chục bytes bộ nhớ.
2. Cho một chuỗi ký tự s bao gồm nhiều từ. Viết một đoạn chương trình C đảo thứ tự các từ.
   Ví dụ: với input là "this is a nice blog" thì output là "blog nice a is this".
3. Cho hai dãy số đã xếp thứ tự tăng dần A và B, mỗi dãy có n phần tử. Xét tập hợp sau:

S = { A[i] + B[j] | 1 <= i, j <= n }.

Chú ý rằng S có thể có đến n² phần tử. Viết một chương trình in ra n số lớn nhất trong S. Chương trình phải chạy trong thời gian O(n).

Tính toán tràn khắp

 

Tính toán tràn khắp (pervasive computing) là một trong các nhánh nghiên cứu đang được phát triển rất nhanh trong giới làm khoa học máy tính. Ý tưởng chính là làm sao cho ta "quên" rằng có máy tính tồn tại xung quanh ta. Lái ô tô, dùng tủ lạnh, TV, và người dùng bình thường không quan tâm đến việc chúng vận hành như thế nào, coi chúng như những thứ hiển nhiên có (take them for granted). Đây là một trong những mục tiêu chính của tính toán tràn khắp: làm cho máy tính "tan" vào môi trường làm việc, học tập của nhân loại.

Hiện nay, người dùng luôn có ý thức cụ thể và phiền toái về cơ/điện của họat động máy tính: thay ổ cứng mới, tải xuống phần mềm quét virus mới, chạy các security patch, vân vân. Máy tính vẫn thường được dùng như một kiểu máy đánh chữ, máy fax, và máy điện tín công nghệ cao. Làm gì cũng phải ngồi đó với máy. Người dùng mới phải học khá nhiều để có thể dùng các chức năng đơn giản của máy tính. Một lượng công lao động đáng kể bị tiêu tốn vào các thứ bất tiện đi kèm với việc sử dụng máy tính.

Ta cần tính toán tràn khắp để thay đổi hiện trạng này (Bill Gates đồng tình). Các thiết bị bé nhỏ sẽ phải liên kết với nhau, thông minh hơn, đơn giản hơn về giao diện, tiện lợi hơn, và biến dần vào hậu trường. Có khá nhiều các đề tài nghiên cứu liên quan đến lĩnh vực này: iRoom ở Stanford, BlueBoards ở IBM Almaden, AMBIENTE ở Fraunhofer IPSI.

Nhiều điểm trong kế hoạch này có thể làm được trong thời gian không xa. Một ngày gần đây, bạn có thể bảo (bằng lời) bức tường trong phòng ngủ chuyển sang kênh MTV, pha ly cà phê lúc 7 giờ sáng mai, và nhắc cho bạn khỏi quên ngày Valentine.

Các ngành nghiên cứu quan trọng để hiện thực tính toán chan hòa là: mạng máy tính (computer networking), đồ họa máy tính (computer graphics), giao diện (computer human interaction), và bảo mật (computer security).

Vấn đề nhị thể

 

Bài toán ba vật thể (3-body problem) là một bài toán nổi tiếng khó trong Vật Lý (cho ba vật thể hút đẩy nhau, tính quĩ đạo). Người ta thường chơi chữ, và dùng "vấn đề nhị thể" (2-body problem) để chỉ một vấn đề khác.

Khi một người đi tìm việc ở một thành phố, bạn đời cũng phải đi theo vào ngược lại - và ta có vấn đề nhị thể. Một trong hai người có thể phải hy sinh cho người kia (tìm việc làm kém thỏa mãn hơn, hoặc không làm, hoặc làm việc khác nghề). Một công ty hoặc một khoa nào đó trong trường đại học, khi phỏng vấn nhân viên hay giáo sư mới, cũng phải xét đến vấn đề nhị thể của họ.

Nếu người xin việc không phải là giỏi xuất chúng, mà lại có vấn đề nhị thể, thì công ty hoặc khoa đó sẽ phải nghĩ rất kỹ trước khi nhận họ vào. Quá trình phỏng vấn và chi phí nhận người mới quá nhiều. Người ta không muốn người mới làm một năm rồi bỏ đi chỗ khác vì vấn đề nhị thể. Ngược lại, nếu người xin việc là xuất sắc, thì thông thường người ta sẽ tìm cách tìm việc làm cho cả nửa còn lại.

Khoa tôi đang phỏng vấn các ứng viên giáo sư mới. Hai phần ba số này có vấn đề nhị thể. Thậm chí có 2 ứng viên đều có bạn đời học Ph.D khoa học máy tính sắp ra trường, và các bạn đời này cũng muốn xin làm assistant professor. Có nghĩa là nếu muốn giữ một người thì phải thuê cả hai.

Việc nhận người mới kể cũng phức tạp. Ngoài việc đánh giá chuyên môn, lại còn phải tính thêm vấn đề nhị thể (liên quan nhiều đến các cấp cao hơn trong trường và tài chính của khoa).

Chung qui chỉ tại Cantor (9)

"Các bài toán có và không có các giải thuật tốt để giải đều rất đáng quan tâm … Tôi giả định (conjecture) rằng không có giải thuật tốt nào để giải bài toán chàng bán hàng rong (traveling salesman). Các lý do của tôi cũng giống như lý do cho các giả định toán học khác: (1) chuyện đó có khả năng xảy ra, và (2) tôi không biết."

[Jack Edmonds, 1966]

Trong bài trước, ta đã nói đến bài toán dừng của Turing và bài toán trong giải tích lambda của Church, các bài toán không có giải thuật nào giải được. Đây là một trong những kết quả cực kỳ quan trọng của khoa học máy tính lý thuyết, nhất là về mặt triết học. Khả năng của máy tính đúng là có giới hạn! Khẳng định này dường như có vẻ tầm thường, ai chẳng nghĩ là khả năng của một cái máy chỉ có một giới hạn nhất định nào đó.

Không hẳn như thế. Thứ nhất, bài toán dừng là một bài toán rất cụ thể, vạch một ranh giới cụ thể cho giới hạn của máy tính. Kỹ thuật chứng minh này sẽ được dùng đi dùng lại cho các bài toán không quyết định được (undecidable problems) khác. Thứ hai, khi biết cái gì làm cho máy Turing có giới hạn, việc tìm một mô hình mạnh hơn mô hình máy Turing sẽ có đường đi rõ ràng hơn. Thứ ba, kể cả vũ trụ cũng có giới hạn, cho nên một giới hạn về mặt lý thuyết không hẳn là liên quan gì đến giới hạn thực tế. Bằng chứng là sự bùng nổ của khoa học máy tính và các công nghệ đi kèm trong vài chục năm qua và vài trăm, có lẽ vài ngàn năm tới. Điều này cho thấy ta cần phải nghiên cứu kỹ hơn bên trong cái giới hạn lý thuyết đó: nghiên cứu các bài toán có giải thuật để giải, và phân lớp chúng ra, xem giới hạn thực tế của máy tính là đến đâu.

Đầu những năm 60, các kỹ sư và khoa học gia bắt đầu chú ý rằng có các bài toán mà giải thuật cho chúng đòi hỏi rất nhiều thời gian chạy. Thời đó, thời gian chạy máy khá đắt tiền, tài nguyên tính toán thì ít ỏi. Người ta mới nghĩ đến việc nghiên cứu giải thuật bằng tổng số bước nó cần để giải một bài toán nhất định ( Micheal O. Rabin [5], Juris Hartmanis và Richard E. Stearns [6], Manuel Blum [7]). Ở Nga, năm 1959 Yablonski cũng đã có hơi hướng đề cập đến độ phức tạp giải thuật [8,9]. Trước đó, Kurt Gödel đã chú ý đến vấn đề này trong một lá thư gửi Jon von Neumann (khi đó đang dưỡng bệnh ung thư).

Ngành nghiên cứu giải thuật và độ phức tạp của chúng thật sự bắt đầu với Jack Edmonds và bài báo năm 1965 của ông với tựa đề "đường đi, cây, và hoa" [1]. Đóng góp chính của bài báo là một giải thuật thời gian đa thức cho bài toán maximum matching. Bài báo đó của Edmonds, và một bài khác của Alan Cobham [2] bắt đầu định nghĩa lớp P là lớp các bài toán có thể giải được trong thời gian đa thức. Bài toán nào nằm trong P được xem là bài toán "dễ".

[1] Edmonds, Jack, 1965, "Paths, Trees and Flowers", Canadian Journal of Mathematics, 17, Toronto, 449-467.

[2] Cobham, Alan, 1964, "The Intrinsic Computational Difficulty of Functions," Proceedings of the 1964 Congress for Logic, Mathematics, and Philosophy of Science, North-Holland, Amsterdam, 24-30.

[3] Levin, Leonid, 1973, "Universal search problems," Problemy Peredachi Informatsii, 9(3), 265-266; partial English translation in: B.A.Trakhtenbrot, 1984, "A Survey of Russian Approaches to Perebor (Brute-force Search) Algorithms," IEEE Annals of the History of Computing , 6(4), Los Alamitos, CA, 384-400.

[4] Cook, Stephen, 1971, "The Complexity of Theorem Proving Procedures," Proceedings of the Third Annual ACM STOC Symposium, Shaker Heights, Ohio, 151-158.

[5] M.O. Rabin, Degree of diflieutly of computing a function and a partial ordering of reeursive sets, Teeh. Rep. No. 2, Hebrew University, 1960.

[6] J. Hartmanis and Ẹ Stearns, On the computational complexity of algorithms, Transactions of the AMS 117, 285-306, 1965.

[7] Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967

[8] S. Yablonski, The algorithmic difficulties of synthesizing minimal switching circuits, Prob. lemy Kibernetiki 2, Moscow, Fizmatgiz, 75- 121, 1959; translation in Problems of Cybernetics 2, Pergamon Press, 401-457, 1961.

[9] S. Yablonski, On the impossibility of eliminating brute force search in solving some problems of circuit theory, Doklady, AN SSSR 124, 44-47, 1959

Chung qui chỉ tại Cantor (8)

 

"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.

Chung qui chỉ tại Cantor (7)

 

"Không. Hồi đó khoa Triết Học không có ai quan tâm đến mấy thứ ấy."

[Alonzo Church trả lời khi được hỏi có quan hệ gì giữa khoa Toán và khoa Triết ở Princeton thời cuối 1920, đầu 1930.]

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 của Church thiếu động cơ triết học. Church thách thức Gödel sáng tạo ra hệ thống tạo hàm khác mạnh hơn giải tích lambda. Vài tháng sau Gödel nghĩ ra cách cải tiến một ý tưởng của Jacques Herbrand (1908-1931) để tạo nên các hàm đệ qui Herbrand-Gödel, hay gọi ngắn gọi là các hàm đệ qui ( recursive functions). Hóa ra là hai hệ thống này tương đương nhau, nhờ vào các nghiên cứu của Stephen C. Kleene (1909-1994), một học trò của Church. Với kết quả này, Church tin rằng các hàm tính toán được đều là các hàm đệ qui. Niềm tin này thường được gọi là luận đề Church (Church thesis).

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 Minnesota và dự vài buổi họp nhóm của ông. Một hôm ông tiết lộ rằng ông là một trong các học trò của Alonzo Church! Trong trang nhà của Richter có để cụm từ tiếng Việt: "nhất sư nhì phụ". Hồi đó tôi gặm nhấm các chi tiết thú vị này mất vài hôm.

Chung qui chỉ tại Cantor (6)

 

"Tôi đã khám phá ra một khả năng logic và hợp pháp mà hợp chủng quốc Hoa Kỳ có thể biến thành một nước độc tài."

[Trích lời Gödel nói với Oskar Morgenstern năm 1952]

Đầu thế kỷ 20, Hilbert dành rất nhiều thời gian phát triển "chương trình Hilbert" như đã đề cập. Tại đại hội các nhà toán học thế giới năm 1928 ở Bologna, Hilbert tuyên bố là Wilhelm Ackermann (1896-1962) và John von Neumann (1903-1957) đã chứng minh được tính nhất quán (consistent – nghĩa là không dẫn đến các mệnh đề mâu thuẫn nhau) của lý thuyết số. Dĩ nhiên nếu tuyên bố này là đúng, thì chương trình Hilbert đã tiến được một bước dài. Hilbert còn tuyên bố là Ackermann gần kết thúc được cả chứng minh rằng số học của các số thực cũng nhất quán. Ông liệt kê bốn bài toán để hoàn tất chứng minh này của Ackermann. Đến năm 1931 thì cả bốn vấn đề này cùng với bài toán số 2 của Hilbert đều được giải quyết thỏa đáng. Kurt Gödel phủ định tất cả! Và nói chung là ông phá tan tành chương trình Hilbert. Năm ấy Gödel mới có 25 tuổi.

Bài tập 2 : chúng ta đều biết là các dữ liệu trong máy tính đều được lưu trữ theo dạng nhị phân. Mã ASCII gán 8 bits nhị phân (0 hoặc 1) cho mỗi chữ cái và chỉ cần cách này ta có thể mã hóa các văn tự tiếng Anh. Thế có thể nào mã hóa các văn tự tiếng Anh với chỉ một ký tự 1 thôi hay không? (Thay vì có cả 0 lẫn 1.)

Gödel có ba định lý rất nổi tiếng: (1) định lý toàn vẹn ( completeness theorem), (2) định lý không toàn vẹn thứ nhất ( first incompleteness theorem), và (3) định lý không toàn vẹn thứ hai.(second incompleness theorem ).

Để giới thiệu về định lý toàn vẹn, hãy xét một bộ tiên đề của một trường (field) số, như trường số thực, trường số hữu tỉ, trường số phức, vân vân. Với một bộ tiên đề như vậy, có nhiều cấu trúc toán học thỏa mãn bộ này (các cấu trúc thực, phức, hữu tỉ, vectors, …). Nếu có một mệnh đề nào đó có thể suy ra được từ hệ tiên đề này (ví dụ "nếu a+a=a, thì a=0"), thì mệnh đề này đúng cho tất cả các cấu trúc toán trên hệ tiên đề này. Tính chất này gọi là tính hợp lý (soundness) của hệ thống. Ngược lại, nếu một mệnh đề nào đó đúng cho tất cả các cấu trúc toán học trên hệ tiên đề, thì có chắc rằng ta sẽ chứng minh được mệnh đề đó không? Câu trả lời là có, và đó chính là nội dung của định lý toàn vẹn Gödel. Theo một nghĩa nào đó, định lý này ủng hộ chương trình Hilbert.

Định lý không toàn vẹn thứ nhất đại khái nói rằng: nếu ta lấy hệ tiên đề cho số học các số tự nhiên (bao gồm cộng trừ nhân chia), thì sẽ có một phát biểu (bằng ngôn ngữ logic) không thể chứng minh được là đúng hay sai. Điều cực kỳ thú vị là Gödel dùng "nghịch lý kẻ nói dối" để xây dựng một phát biểu trong hệ logic này. Phát biểu đó nói rằng: "mệnh đề này không chứng minh được", sau đó dùng lập luận đường chéo của Cantor để hoàn tất chứng minh.

Ta thử nghĩ thêm một chút về ý nghĩa to lớn của định lý này. Thứ nhất, nó hủy tan chương trình Hilbert. Không cần biết hệ tiên đề tốt đến đâu (kể cả khi có một số vô hạn – nhưng đếm được – các tiên đề), luôn luôn có các mệnh đề "độc lập" với hệ thống. Ta có thể lấy mệnh đề mới này làm một tiên đề và mở rộng hệ thống. Như vậy, toán học là tuyệt đối vô hạn! Bạn có thể tưởng tượng một cái "cây tri thức", bắt đầu bằng một số tiên đề và phân nhánh ra nhờ suy luận logic. Các tiên đề có thể là các nguyên tắc sống (không giết người, cướp của) chẳng hạn, và ta sống theo luật logic cùng các nguyên tắc của mình, ai cũng hy vọng là có thể làm thế được. Không may là, sẽ luôn có các tình huống trong cuộc sống nằm ngoài hệ thống giá trị của bản thân ta. Như vậy, định lý này của Gödel theo nghĩa nào đó đã dạy cho chúng ta phải sống với một tâm hồn mở, không thể theo một nguyên tắc bất di bất dịch nào đó. Ít nhất là nếu ta sống có logic.

Định lý không toàn vẹn thứ hai của Gödel phá hủy hoàn toàn những gì còn lại của chương trình Hilbert. Định lý này nói rằng không thể chứng minh rằng số học có tính nhất quán. Chỉ số học đã "phức tạp" đến thế, ta không có hy vọng gì vào chương trình chứng minh tính nhất quán của toàn bộ toán học.

Sự độc lập (independence) của một mệnh đề trong hệ thống (như mệnh đề Gödel dựng nên để chứng minh định lý không toàn vẹn thứ nhất) là một ý tưởng rất quan trọng trong lịch sử toán học. Tiên đề số 5 của Euclid là một ví dụ kinh điển. Bỏ nó vào thì ta có hình học Euclid, thay đổi nó một chút theo vài kiểu khác nhau là ta có vài loại hình học phi Euclid với các công trình của Carl Friedrich Gauss, Nikolai Ivanovich Lobachevsky, János Bolyai, và Bernhard Riemann. Giả thuyết liên tục (bài toán số 1 của Hilbert) được Paul Cohen chứng minh tính độc lập năm 1963. Câu hỏi P chọi NP của chúng ta cũng có khả năng là nó độc lập với hệ thống suy luận hiện hành, ta sẽ quay lại khả năng này sau.

Các nghiên cứu về các hệ thống chứnh minh và các tiên đề có giá trị to lớn trong khoa học máy tính. Nhiều nhà khoa học máy tính nổi tiếng (như Edsger Wybe Dijkstra) đã bỏ nhiều năm nghiên cứu để làm thế nào "chứng minh" được là một chương trình máy tính chạy đúng với dự định thiết kế (specification), mà trong ngữ cảnh của chúng ta là các tiên đề! Một công trình khác của Gödel về "độ dài" của các chứng minh đã nuôi mầm cho các định lý "tăng tốc" của lý thuyết tính toán hiện đại.

John von Neumann từng nói là Kurt Gödel là nhà logic học lỗi lạc nhất thế giới sau Aristotle. Ta không thể không đồng ý với Neumann. (Bản thân Neumann cũng là một thiên tài tuyệt đỉnh có ảnh hưởng cực lớn đến khoa học máy tính mà ta sẽ "gặp" ông vào dịp khác.)