Blog Khoa Học Máy Tính

1. Từ một ước mơ

Ngày 25 tháng 10 năm 2003, giáo sư Donald Knuth gửi một lá thư đến ban biên tập của tạp chí chuyên ngành thuật toán (Journal of Algorithms). Trong thư, ông phân tích giá cả xuất bản của các tạp chí chuyên ngành trong ngành lý thuyết khoa học máy tính.

Giá xuất bản của các bài báo chuyên ngành tính theo từng trang đã tăng quá nhanh. Ông so sánh giá tính theo lạm phát và giá tăng thực tế. So sánh cho thấy một số nhà xuất bản chuyên nghiệp đã lợi dụng các nghiên cứu khoa học, vốn bản chất là miễn phí và tự nguyên, để kiếm lợi quá đáng. Các ban biên tập và các người phê bình (review) các bài báo chuyên ngành đều nói chung là làm việc tự nguyện và miễn phí. (Đôi khi người trong ban biên tập có thể nhận một số tiền tượng trưng hoàn toàn không đáng kể.) Trong khi đó các thư viện phải trả một giá rất đắt để nhận các tạp chí chuyên ngành này. Ông đặc biệt nghiêm khắc với nhà xuất bản Elsevier, kẻ kiếm lợi quá đáng nhất.

Khi xưa thì các nhà xuất bản phải làm việc khá nhiều để có thể đăng một số báo. Nay thì nhờ có phần mềm miễn phí TeX của chính Don Knuth, các tác giả đều tự soạn thảo lấy bài báo của mình với chất lượng rất cao. Nói chung một nhà xuất bản chỉ là người đứng giữa, thu bài (đã soạn thảo) và làm việc in ấn và phát hành.

Lá thư này đã làm cho cả ban biên tập của Journal of Algorithms từ chức và tự thành lập một journal mới. Một online journal miễn phí khác cho ngành lý thuyết tính toán cũng đã được thành lập. Online Journal of Combinatorics đã bắt đầu hành trình này khoảng năm 1995, và đã rất thành công. Giá trị khoa học và danh tiếng của một journal hoàn toàn nằm ở danh tiếng của ban biên tập, cho nên các online journal này, dù mới, đều là các journal đỉnh cao trong ngành.

Online journal trong thời đại chúng ta là đường đi cực kỳ hữu lý, nhất là đối với các nghiên cứu khoa học. Bất kỳ nhà khoa học chân chính nào cũng muốn công trình, ý tưởng của mình đến với người đọc nhanh chóng nhất, tiện lợi nhất, và ít tốn kém nhất (trong trường hợp này là miễn phí). Các nhà khoa học máy tính đều để các bài báo của mình ở homepage của họ, và có thống kê ở tạp chí Nature cho thấy các bài báo online được đọc và tham chiếu (referred/cited) đến nhiều hơn các bài khác. Với một webserver đơn giản và ít công bảo trì là phần cơ học của một journal đã được đảm bảo. Các công việc còn lại là biên tập và phê bình, chọn bài, thì các nhà khoa học đằng nào cũng đang làm.

Một vụ tương tự cũng đã xảy ra ở Machine Learning Journal vài năm trước, và toàn bộ ban biên tập của tạp chí này cũng đã thoái vị và thành lập online journal miễn phí Journal of Machine Learning Research.

Bản thân tôi tin tưởng tuyệt đối rằng tri thức của nhân loại thì cần phải được đến với càng nhiều người càng tốt, giá càng rẻ càng tốt, miễn phí là lý tưởng. Hành động giấu giấu diếm diếm tri thức và kiếm lợi trên tri thức của người khác là hành động hèn nhát đáng lên án. Có lẽ phải làm rõ điểm này. Tri thức được khám phá khác với các công trình sáng tạo mà chủ nhân hoàn toàn có quyền giữ bản quyền và thu lợi nhuận. Không ai có quyền mua bán phương trình sóng Maxwell, nhưng có thể bán thuốc chữa SIDA mới nhất. Điểm này dài dòng ta để khi khác. Hy vọng là qua ngữ cảnh của bài viết, các bạn hiểu tôi muốn nói gì.

Internet đã thay đổi cơ bản sự xuất bản, nhất là xuất bản khoa học.

Nghĩ đến đây, tôi có một mơ ước, rằng một ngày nào đó các sách giáo khoa của chúng đa được để trong một trang web nào đó, cho học trò tải xuống miễn phí, để người nghèo nhất cũng có thể nhờ ai đó tải xuống và in ra [và trả ít phí cho việc này], copy lại cho nhiều học sinh khác cùng dùng. Theo cách này, nhiều người có thể đọc sách giáo khoa, phê bình những chỗ sai đúng online, sách giáo khoa có gì sai thì có thể chữa ngay lập tức thay vì phải đi qua quá trình xuất bản và phân phối sách hiện nay. Ta vẫn có thể in một số ấn bản nhất định để phục vụ bạn đọc vùng sâu vùng xa trong khi chờ phổ cập Internet. Mô hình vừa cho miễn phí trên mạng vừa bán bản in đã được làm rất phổ biến và thành công ở Mỹ và cả Việt Nam (báo chí online là một ví dụ rất tốt).

Bộ giáo dục nói riêng và nhà nước ta nói chung đã tốn bao nhiêu tiền của cho việc soạn thảo sách giáo khoa, thì cách này sẽ có thể dùng tiền đó trả cho người viết sách và trả tiền thuê server và bảo trì server. Tại sao lại thêm một lớp cản kiếm lợi giữa tri thức và công chúng, trong khi phổ cập tri thức là chiến lược sống còn của Việt Nam?

2. Đến các vấn đề thực tế

Mơ ước trên phải chăng là lấy trăng đáy nước. Bạn có thể hỏi:

• Trong tình trạng Internet chưa được phổ cập, người không có Internet thì làm thế nào? Có khá nhiều cách giải quyết vấn đề này. Ta thử nghĩ vài giải pháp “đơn giản”.

• Ta vẫn có thể in một số ấn bản nhất định để phục vụ các nơi chưa có Internet. Ý tưởng này giống như các báo chí vừa có bản in vừa có bản online.
• Ở các chỗ có Internet nhưng chưa phổ biến lắm, thì có thể lập các dịch vụ in ấn và copy địa phương. Việc phân phối này giống như phân phối/đóng gói phần mềm mã nguồn mở. Thậm chí có thể áp dụng luôn Gnu public lisence (GPL) vào sách. Chẳng phải ta dang có quốc sách phát triển mã nguồn mở hay sao?
• Điều này hoàn toàn có thể tiến hành song song với việc phổ cập Internet, cho đến khi Internet đến mọi nơi thì cũng đã có nhiều sách online rồi.

• Với nhiều triệu truy cập liên tục trên các trang sách online này, tiền quảng cáo là một nguồn lợi không nhỏ.
• Giống như phần mềm mã nguồn mở, các tác giả cũng có thể có tiền từ đóng góp của phụ huynh, các công ty, và nhà nước.

• Một hệ điều hành phức tạp như GNU/Linux mà còn có thể mở toanh hoanh cho người ta đọc nguồn, chê bai, sửa chữa, thì không có lý do gì một quyển sách không quản lý được.
• Thời gian trước có vụ một ông nhà thơ nào đó phê bình các tác giả viết sách giáo khoa Văn Học. Tôi thấy người ta trích dẫn lẫn nhau trên mặt báo, nhưng có khi trích dẫn thiếu ngữ cảnh, người đọc không có ai có thời gian đi kiểm chứng. Phê bình online thì năm năm rõ mười, mọi thứ rành rành ra đó.

Cái lợi của sách giáo khoa miễn phí thì vô cùng tận

• Dần dần tiết kiệm công lao động và tiền bạc chuyên chở, phân phối, quan liêu, tham nhũng liên quan đến xuất bản đăng đầy trên mặt báo mỗi năm.
• Các tác giả sẽ có trách nhiệm hơn khi bàn dân thiên hạ chủ động “soi mói” vào công trình của mình.
• Sách có thể được viết nháp, cho mọi người phê bình trước khi cho vào chương trình. Vài triệu đôi mắt thì tốt hơn một hội đồng vài chục người, dù là chuyên gia đi nữa. Các lỗi thô thiển sẽ khó mà thoát khỏi quá trình này. Đây chính là cách mà các giáo sư viết sách ở nước ngoài vẫn làm. Thông thường họ giao bản nháp cho bạn bè, đồng nghiệp, dùng để dạy qua vài năm, cho đồng nghiệp và biết bao sinh viên góp ý, sửa chữa, trước khi in.
• Các tài liệu, bài tập, hình ảnh, liên kết, thông tin có liên quan đến nội dung sách có thể được để online. Cả học sinh, sinh viên, lẫn thầy cô đều truy cập được. Tác giả có thể làm rõ điểm này, người dùng thắc mắc điểm kia. Cách học này cực kỳ pro-active và là phương pháp học tiên tiến. Học trò và phụ huynh có thể kiểm tra nếu thầy cô giáo dạy sai. Thầy cô giáo có thể dùng các thông tin liên quan làm cho phòng học sinh động hơn. Người ta có thể chia xẻ lẫn nhau kinh nghiệm học tập, giảng dạy đề tài đó.
• Sách có thể được cập nhật thường xuyên hơn, ví dụ như thêm/sửa một chương cho phù hợp với tình tình hiện tại. Nếu dùng sách offline thì phải chờ rất lâu mới có thể phân phối đến người dùng.
• Đây cũng là cách cực tốt để thanh thiếu niên và cả phụ huynh có động cơ dùng Internet theo hướng tích cực, thay vì chỉ vào chat-room tán gẫu. Người chưa có Internet thì có động cơ để kết nối Internet, để mua máy tính mới, thúc đẩy thị trường công nghệ cao.
• Với từng cá nhân thì một máy tính, một máy in, qua mười mấy năm học, sẽ rẻ hơn đi mua cả trăm quyển sách giáo khoa.

Còn một lý do tối quan trọng nữa.

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

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?

Tất cả có thể bắt đầu bằng một ước mơ.

Chuyên mục: Giáo dục & Xuất bản | Bình luận (1) »

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

Chuyên mục: CNTT các nước và VN & Mạng máy tính | Bình luận »

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

Chuyên mục: Chính trị trong ngành & Dành cho du học sinh | Bình luận »

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

Chuyên mục: Lý thuyết tính toán | Bình luận »

Lần đầu tiên tôi được nghe Eva Cassidy qua một album loại jazz/pop collection tình cờ sục sạo ra được khi đi tìm đĩa của Norah Jones ở Hong Kong. Chị hát “Yesterday” của Paul McCartney với một góc cảm xúc và rearrangement rất độc đáo. Tuy vậy, ấn tượng đọng lại sâu sắc nhất không phải cách chị thể hiện Yesterday (dù xuất sắc) mà là giọng soprano tuyệt đối quyến rũ, khỏe, và cực kỳ truyền cảm! Giọng ca mà bất kỳ ai, dù đang làm gì, nghe qua lần đầu cũng phải dừng lại lắng nghe cho hết ca khúc. Giọng ca làm ta có cảm giác không gian xung quanh đặc lại, giao động theo từng tiếng ngân.

Tôi đã liên tưởng đến Aretha Franklin khi nghe Eva Cassidy để rồi đi từ ngạc nhiên đến ngưỡng mộ khi tìm hiểu thêm về cô gái da trắng tóc vàng đầy tài năng này. (Ngạc nhiên vì tôi đã không thể tưởng tượng được đây lại không phải là một chất giọng nữ da đen.)

Tiểu sử và câu chuyện cảm động của Eva Cassidy đầy rẫy trên Internet. Tôi tóm tắt lại đây vài nét đặc trưng rất Eva Cassidỵ

Eva sinh ngày 2/2/1963, mất ngày 2/11/1996. Chị ghét trường học, áo đầm, lái xe hung hăng; yêu thích vẽ, điêu khắc, chơi guitar và hát.

Chị học guitar từ cha, Hugh Cassidy, từ thủa còn rất nhỏ, và chơi guitar trong ban nhạc gia đình với cha (bass) và anh trai Donny (violin). Chị là thiên tài bẩm sinh về hát harmony. Trẻ con nghe nhạc trên radio hát theo đúng giai điệu đã là giỏi, Eva thì luôn hát bè theo một cách tuyệt hảo – bất kể bè cao thấp kiểu gì!

Các record companies và cả các clubs không chịu làm việc với chị vì Eva chỉ muốn hát những gì mình thích, từ chối bị liệt vào một dạng nhạc nhất định. Khi hát demo, chị luôn hát mẫu một bài Blues, một bài Jazz, một bài Pop, một bản dân ca Celtic lạ hoắc nào đó, và cả Gospel.

Không chỉ có thế, chị luôn arrange lại theo ý mình. Góc nhìn của chị đến nhạc phẩm folk kinh điển “over the rainbow” cực kỳ độc đáo, và có lẽ là rearrangement nổi tiếng nhất của Eva. Khi bị yêu cầu hát một số bài này bài nọ để ra album, chị trả lời: “Just don’t have me sing that pop-crap!”

Xin trích một đoạn từ bài báo của Jefferson Morley (ngày 3/8/1998) trên tờ Washinton Post:

“In June she went with Jackie Fletcher to see Odetta, who was performing in Baltimore. ‘ This is what I want to do,’ Eva told her friend, gesturing to the venerable folk singer onstagẹ ‘A woman getting older and better, playing her guitar in haunts and clubs and quiet auditoriums, places where people really listen.’”

Sau khi đọc câu này và nghe Cassidy đến xuất thần, tôi đã không kìm được liên tưởng đến Britney Spears, JLo, … và một sự phỉ báng âm nhạc oái oăm nào đó.

Chị không thích kiếm nhiều tiền (đến năm 30 tuổi – 1993 – chị mới có tài khoản ngân hàng), và dù giọng ca tuyệt hảo, chị lại thích làm backup vocal, không thích xuất hiện trước đám đông. Ước mơ tuổi thơ của chị là được hát backup cho Steve Wonder.

Đầu năm 1996, chị bị đau xương hông. Eva nghĩ là hậu quả của việc vẽ tranh tường ba ngày liên tục cho một trường trung học ở Annapolis, nơi chị chuyển đến từ DC. Không ngờ khám nghiệm cho thấy chị bị ung thư xương. Eva không có bảo hiểm, các bạn ca/nhạc sĩ đã làm vài buổi trình diễn kiếm viện phí cho chị.

Chị nhập viện John Hopkins mùa xuân 1996. Bao nhiêu bè bạn đến thăm và tặng hoa. Không thể gặp hết mọi người, chị nhờ mua một đống giấy và bút vẽ để ở hành lang bệnh viện. Mọi người ngồi la liệt vẽ ở hành lang. Chị treo tất cả các bức tranh này trong phòng bệnh, xem như đã gặp bạn.

Tháng 9/1996, người ta tổ chức một tribute concert. Eva đã rất yếu, nhưng cũng đến. Không ai mong đợi chị phải trình diễn nặng nhọc gì, mọi việc đã được sắp xếp thỏa đáng để chị song ca sơ sài với bạn hát Chuck Brown. Nhưng, với một sức mạnh huyền bí, chị đã chơi guitar và hát “What a wonderful world” (dĩ nhiên là với rearrangement rất Eva Cassidy) tặng cha mẹ mình. Tôi tìm được recording này – không cần phải nói – rất xúc động! Đây cũng là lần cuối cùng Eva biểu diễn trước công chúng. Chị ra đi tháng 11 năm 1996, chỉ mới hơn 33 tuổi, làm ngẩn ngơ tất cả những ai đã từng nghe qua giọng hát có một không hai này, dù là nghe lần đầu sau khi chị mất.

Eva Cassidy chỉ released hai CDs, đều do các hãng labels nho nhỏ địa phương xuất bản. Nhờ BBC Radio 2, một trong hai albums này gần đây đã bán được bản thứ một triệu, tin rằng chị đang mỉm cười ở đâu đó, và vẫn ôm guitar dịu dàng hát.

Dù chị hát nhiều loại nhạc, tôi thích nhất chị hát Blues (At Last, Ain’t No Sunshine, …), sau đo đến Folk (Bridge over trouble water, Over the Rainbow, …). Các takes của chị cho các nhạc phẩm pop nổi tiếng cũng rất thú vị (Yesterday, Imagine, Time after time, Fields of Gold, …). Gần đây, cô ca sĩ 19 tuổi Katie Melua người Anh (sinh ở Georgia) vừa bán được album thứ một triệu; album này tên là Call off the search, có nhạc phẩm khá hay “Faraway Voice” do Katie viết tặng Eva. Katie có thể được xem là Norah Jones của Anh. Cô cho biết một trong những người cô chịu ảnh hưởng lớn nhất chính là Eva Cassidy.

Chuyên mục: Âm Nhạc | Bình luận (1) »

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

Chuyên mục: Lý thuyết tính toán | Bình luận »

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

Chuyên mục: Lý thuyết tính toán | Bình luận (3) »

“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.)

Chuyên mục: Lý thuyết tính toán | Bình luận »

“Nếu tôi có một số thành công nhất định trong toán học thì đó là vì tôi luôn thấy nó rất khó.”

[Trích lời Hilbert nói với Harald Bohr (1887-1951)]

Năm 1900, tại hội nghị các nhà toán học thế giới ở Paris (International Congress of Mathematicians), David Hilbert đề nghị 23 bài toán làm kim chỉ nam cho nghiên cứu toán học của thế kỷ 20. Các bài toán của Hilbert đã truyền cảm hứng cho biết bao thế hệ các nhà toán học, đã thiết lập các nhánh mới của toán học, thậm chí định hình cả cơ sở của lý thuyết tính toán trong khoa học máy tính hiện đại. Nếu các bạn muốn tìm hiểu thêm về các bài toán Hilbert và lịch sử xung quanh chúng thì tôi giới thiệu quyển “The Honors Class” của Benjamin Yandell.

Trong hành trình của chúng ta thì ba bài toán Hilbert sau đây có liên quan mật thiết:

• Bài toán Hilbert số 1: chính là continuum hypothesis như ta đã thảo luận trong bài trước.
• Bài toán Hilbert số 2: có thể nào chứng minh rằng các tiên đề của số học (arithmetic) không dẫn đến các mệnh đề mâu thuẫn nhau?
• Bài toán Hilbert số 10: thiết kế một quá trình, một thủ tục mà nhờ đó sau một số hữu hạn các bước ta có thể biết một phương trình Diophantine (tìm nghiệm nguyên của các đa thức hệ số nguyên) có nghiệm hay không?

Một bài toán có liên quan nữa mà Hilbert đề nghị năm 1928 là bài toán quyết định (Entscheidungsproblem trong tiếng Đức, hay decision problem trong tiếng Anh). Một cách nôm na, bài toán này hỏi “có một thủ tục nào để quyết định xem một phát biểu toán học là đúng hay sai?” (dĩ nhiên là cho trước một tập các tiên đề và các luật suy luận). Gottfried Leibniz (1646-1716) đã hỏi câu hỏi này dưới một dạng hơi khác một chút. Leibniz sáng chế ra một máy tính cơ học, và ông mơ một ngày nào đó sẽ chế được một máy tính thao tác các biểu tượng toán học, và máy tính này sẽ có thể dùng để chứng minh hoặc phản chứng minh các phát biểu toán học.

Bài toán số 1 và số 2 liên quan đến nền tảng logic của lý thuyết tập hợp và của toán học nói chung. Lời giải cho các bài toán này có ý nghĩ to lớn về triết học, đặc biệt là bài số 2. Bài toán số 10 và entscheidungsproblem lại có ý nghĩa tuyệt đối quan trọng trong sự hình thành khái niệm giải thuật và lý thuyết tính toán. Các “thủ tục” tính toán mà Hilbert đề cập đều là các giải thuật, mặc dù lúc đó ông không dùng ngôn ngữ này. Để giải các bài toán này, ta cần định nghĩa rõ ràng thế nào là một giải thuật. Quá trình đi tìm định nghĩa giải thuật đã dẫn đến các mô hình máy tính hiện đại như máy Turing và phép tính lambda (lambda calculus) mà chúng ta sẽ bàn tới trong các bài sau.

Chuyên mục: Lý thuyết tính toán | Bình luận »

Trong bài trước, ta đã chứng minh |S|< |2^S| với mọi tập S bằng lý luận đường chéo. Cantor không dừng lại ở đó, ông xét một chuỗi vô hạn các lực lượng của các tập vô hạn được tạo ra theo cách này: |N|, |2^N|, |2^{2^N}|, …, và ông dùng Aleph không, Aleph một, Aleph hai, vân vân để chỉ lực lượng của các tập này. Như vậy, Aleph không là lực lượng của N, câu hỏi tự nhiên là: thế lực lượng của R nằm đâu trong chuỗi này? Cantor tin rằng |R| = Aleph không nhưng ông không chứng minh được điều này. Đây là một trong những bài toán nổi tiếng nhất của thế kỷ 20, thường được gọi là giả thuyết liên tục (continuum hypothesis).

Giả thuyết liên tục, các va chạm với Leopod Kronecker (người không chấp nhận lý thuyết tập hợp này), cùng với vài nghịch lý đau đầu của lý thuyết của mình (xem dưới đây) làm Cantor bị suy nhược thần kinh liên tục trong hơn hai mươi năm cuối đời mình. Ông ra đi trong một viện an dưỡng sau một cơn đau tim.

Ta thử xem xét một nghịch lý nảy sinh từ lý thuyết Cantor, gọi là nghịch lý Russell. Bertrand Russell (1872-1970) xét tập hợp sau đây:

S = { X | X không phải là phần tử của X}.

Ví dụ, nếu X là tập hợp các khái niệm hiểu được, thì X là phần tử của chính nó, vì rõ ràng khái niệm này có thể hiểu được. Nhưng nếu X là tập hợp các quán nhậu ở Sài Gòn, thì X không phải là phần tử của chính nó. Russell đặt câu hỏi: “thế S có phải là phần tử của chính nó không?” Dễ thấy đây là nghịch lý. Rất oái oăm là nghịch lý này có ý tưởng tương tự như lý luận đường chéo của Cantor. Trước đó, người ta cũng đã biết các nghịch lý khác có tư tưởng tương tự, nhưng vì không phát biểu bằng ngôn ngữ hình thức của toán học nên chúng bị bỏ qua, bị cho là sản phẩm của tính mù mờ của văn nói, văn viết. Ví dụ, nghịch lý kẻ nói dối có thể tả như sau: anh A nói “cái tôi đang nói là sai”. Nghịch lý chàng cắt tóc thì nằm ở câu: “trong một làng nọ, có một chàng cắt tóc cắt tóc cho tất cả những ai trong làng không tự cắt tóc lấy” (câu hỏi là, thế anh ta có tự cắt không?). Vấn đề của các nghịch lý này là lối tham chiếu vào bản thân (self-reference) mà sau này Gödel cũng dùng để chứng minh định lý không toàn vẹn (incompleteness theorem) lừng danh của ông. Để dịp khác ta sẽ bàn thêm về định lý này.

Các nghịch lý kiểu như trên khuấy động một cuộc tranh luận lớn có một không hai trong lịch sử về nền tảng của toán học. Bạn thử tưởng tượng, nếu có một nghịch lý không giải quyết được trong bất kỳ ngành học nào, thì nền tảng logic của ngành đó có nguy cơ sụp đổ hoàn toàn! Các nhà toán học hoặc ủng hộ Cantor, hoặc chống đối hoàn toàn lý thuyết tập hợp này. David Hilbert nói: “không ai có thể đuổi chúng ta ra khỏi thiên đàng mà Cantor đã tạo cho chúng ta”. Henri Poincaré bảo: “các thế hệ sau sẽ xem lý thuyết tập hợp như một thứ bệnh”.

Các nhà toán học và logic học thời đó đề cử vài phương pháp để giải quyết các nghịch lý này:

• Trường phái logic (logicism) đề nghị dùng logic hình thức (formal logic) để làm toán, với hy vọng là logic hình thức sẽ xóa bỏ được sự mù mờ của ngôn ngữ phổ thông. Bộ sách Principia Mathematica của Alfred North Whitehead và Bertrand Russell là một trong những công trình đại diện cho trường phái này. Các tác giả đã phải dùng đến hai quyển để có thể chứng minh 1+1=2.
• Trường phái trực quan (intuitionism) được khởi xướng khoảng năm 1908 bởi nhà toán học Hà Lan Luitzen Egbertus Jan Brouwer (1881-1966). Trường phái này là cả một hệ thống triết học. Một trong những luận điểm cơ bản nhất của trường phái trực quan về toán học là: ta phải làm toán mang tính xây dựng (constructive mathematics). Các khái niệm như các số tự nhiên 1, 2, 3 có thể “xây dựng” được từ trực quan con người. Khi định nghĩa một khái niệm mới, nó phải được xây dựng được bằng một số hữu hạn các bước. Như vậy, các chứng minh bằng phản chứng không thể chấp nhận được trong trường phái này, và vì thế các nghịch lý trên không mang ý nghĩa gì cả. Kể cũng thú vị là một định lý cực kỳ nổi tiếng của Brouwer trong hình học tô-pô (fixed point theorem) lại được chứng minh bằng phản chứng!
• Trường phái hình thức (formalism) do Hilbert khởi xướng. Về căn bản, Hilbert tin rằng các nhánh của toán học có thể được mô tả bằng một hệ thống tiên đề và một ngôn ngữ hình thức bậc nhất (first order language) với cú pháp cụ thể. Ngôn ngữ này có thể được nghiên cứu như một đối tượng toán học, và nhờ đó ta có thể trả lời chắc chắn các câu hỏi kiểu như: “có thể nào nhánh toán học này có nghịch lý không?” (Dĩ nhiên nghịch lý đó phải được phát biểu bằng ngôn ngữ hình thức ấy.) Hilbert đề nghị là hình thức hóa tất cả các nhánh của toán học, sau đó chứng minh rằng tất cả các nhánh này đều không có nghịch lý. Đây là nội dung chính của chương trình Hilbert (Hilbert’s program).

Hiện nay, chúng ta nói chung đều theo trường phái hình thức của Hilbert. Các ngành như hình học Euclid, lý thuyết số, đại số, vân vân đều được tiên đề hóa và hình thức hóa khá cụ thể. Các sách giáo khoa đều dạy học sinh theo kiểu này.

Ảnh hưởng của Hilbert vào sự phát triển của toán học hơn 100 năm qua là vô cùng to lớn. Khoa học máy tính cũng không ngoại lệ.

Chuyên mục: Lý thuyết tính toán | Bình luận »

Tôi thấy, nhưng tôi không tin.

[Trích một bức thư Cantor gửi Dedekind năm 1878]

Trở lại với hành trình lịch sử của ta: trong các thập niên cuối cùng cùng của thế kỷ 19, nhà toán học vĩ đại Georg Cantor (Georg Ferdinand Ludwig Philipp Cantor, 1845-1918) đề ra một trong những tư tưởng táo bạo nhất trong lịch sử toán học, khuấy đảo toàn bộ thế giới toán học lúc bấy giờ, làm cho các nhà toán học xuất sắc nhất thế giới thời kỳ đó như Henri Poincaré (1854-1912) và David Hilbert (1862-1943) phải nhảy vào “tham chiến”. Cá nhân tôi có cảm tình đặc biệt với Cantor, và cho rằng ông là nhà toán học có tư tưởng độc đáo nhất mọi thời đại. Chữ độc đáo không đủ để diễn tả điều tôi muốn nói về Cantor. Tiếng Anh họ dùng chữ original, mang nghĩa là nguyên gốc, độc đáo, đầu tiên, …

Lý thuyết tập hợp của Cantor không chỉ làm lung lay nền tảng toán học, đặt ra các vấn đề mấu chốt của triết học và logic, là tiền thân của lý thuyết tập hợp hiện đại, mà còn mang một trong những tư tưởng tiên phong của lý thuyết tính toán hiện đại. Sinh viên học máy tính nên biết và đọc về lý thuyết Cantor.

Lý thuyết tập hợp Cantor có hai đối tượng chính: các tập hợp, và lực lượng (cardinality) của các tập hợp. Tập {a,b,c} có lực lượng là 3. Ta dùng |S| để chỉ lực lượng của tập S. Có tất cả 2³=8 tập con của tập {a,b,c}. Nói chung, nếu S là tập hữu hạn thì có tất cả 2^|S| tập con của tập S. Ta dùng 2^S để chỉ tập tất cả các tập con của S. Nếu S hữu hạn, thì rõ ràng |2^S| = 2^|S| > |S|.

Dĩ nhiên những điều này người ta đã biết từ lâu. Cantor bắt đầu lý thuyết của ông bằng một câu hỏi cực kỳ khó chịu: thế nếu S là tập vô hạn thì thế nào? Quan hệ |S| < |2^S| có còn đúng nữa không? Thế nào là lực lượng của tập vô hạn?

Hai tập {a,b,c} và {x,y,z} có lực lượng bằng nhau. Điều này có thể hiểu theo hai cách: (1) đếm các phần tử trong từng tập, và cho kết quả là 3. Thế là chúng bằng nhau. Nhưng đối với Cantor, lý do chúng bằng nhau sâu sắc hơn nhiều. Chúng có lực lượng bằng nhau là vì ta có thể ghép cặp một-một giữa chúng: (a,y), (b,x), (c,z). Dĩ nhiên có nhiều song ánh (bijection – hoặc ánh xạ một-một) giữa hai tập này (3! = 6), nhưng miễn có một song ánh là chúng bằng nhau. Theo dòng lý luận này, nếu có một đơn ánh (injection) từ tập A vào tập B thì |A|≤|B|. Ví dụ: từ {a,b} vào {x,y,z} thì có đơn ánh {(a,z),(b,x)}, cho nên |{a,b|}≤|{x,y,z}|. Nếu có đơn ánh từ A vào B, nhưng không có song ánh từ A vào B, thì |A|< |B|.

Để làm ví dụ, ta thử xét các tập hợp sau: N là tập các số tự nhiên, E là tập các số tự nhiên chẵn, và R là tập các số thực. Dễ thấy |E|≤|N|≤|R|. Về mặt trực quan, ta có thể nghĩ rằng tập E bằng khoảng một nửa tập N, nhưng thực ra |N|=|E| vì ta có song ánh f: N –> E định nghĩa bởi f(x) = 2x. Ví dụ này minh họa sự tinh tế khi ta xét các tập vô hạn.

Với căn bản như trên, ta có thể chứng minh |S|< |2^S| bằng một lý luận đơn giản nhưng có uy lực cực kỳ gọi là lý luận đường chéo (diagonal argument). Lý luận này cũng là nền tảng của các kết quả nổi tiếng của Gödel và Turing mà ta sẽ đề cập sau. Đại khái, để chứng minh |S|< |2^S| (dù S là vô hạn) ta có thể làm như sau:

• Dễ thấy |S|≤|2^S| (bạn nên tự tìm vài đơn ánh chứng minh điều này).
• Giả sử |S|=|2^S|, nghĩa là có một song ánh f: S –> 2^S. Gọi T là tập tất cả các phần tử x thuộc S sao cho x không thuộc f(x). Gọi b là phần tử của S mà f(b) = T. Bây giờ ta thử hỏi: b có nằm trong T hay không? Nếu b thuộc T thì, theo định nghĩa của T, b không thuộc f(b=T), vô lý. Nếu b không thuộc T, thì cũng theo định nghĩa của T, b thuộc f(b)=T.
• Tóm lại, |S|< |2^S|.

Nhà toán học nổi tiếng Paul Erdos thường ví von rằng một chứng minh tuyệt đẹp như vậy phải là một chứng minh trong quyển sách của thượng đế (xem “Proofs from the book”). Không biết các bạn thế nào chứ lần đầu tiên tôi thấy chứng minh này, tôi cảm thấy ná thở vì cái đẹp! Sau này tôi mới khám phá ra rằng lúc đó, dù hiểu về mặt kỹ thuật và cảm nhận được một ít cái đẹp của ý tưởng này, tôi thật sự chưa hiểu vấn đề!

Bài tập 1: chứng minh rằng |N|< |R|.

Ta sẽ còn gặp lại lý luận đường chéo vài lần trên hành trình xuôi dòng lịch sử này.

Chuyên mục: Lý thuyết tính toán | Bình luận (5) »

Giả sử bạn đi làm cho một công ty nào đó, xếp giao nhiệm vụ viết một chương trình tốt, chạy nhanh, để giải một bài toán loại rất khó này, bạn sẽ làm gì? Ta thử ghi ra đây vài khả năng:

1. Hỏi giáo sư dạy giải thuật (và ông ta bí)
2. Bảo với xếp là “tôi chịu thôi” (và mất việc)
3. Ném vào sọt rác 6 tháng cuộc đời tìm giải thuật hiệu quả, và sau đó quay lại khả năng 2
4. Tìm giải thuật cơ bắp (brute-force) tốn khoảng vài chục thế kỷ chạy mới xong (mất việc và mất mặt)
5. Chứng minh cho xếp thấy là bài toán xếp cho không có giải thuật hiệu quả (cận dưới thời gian chạy là một hàm mũ chẳng hạn)
• Khả năng này rất khó xảy ra, kinh nghiệm cho thấy chứng minh những điều tương tự là cực kỳ khó. Với tất cả các bài toán loại này, cận dưới tốt nhất người ta biết là O(n), vô dụng.
6. Chứng minh rằng bài toán xếp cho cũng khó như chục ngàn bài toán khác chưa ai biết giải.

A ha, khả năng số 6 nghe có vẻ được, nhưng cũng có vẻ lừa phỉnh vì ta thật ra không giải quyết vấn đề, mà bán cái nó cho nửa thế kỷ nghiên cứu của vô vàn người khác!

Nhưng làm thế nào ta chứng minh một điều như vậy? Thế nào gọi là khó? Thế nào là cái này khó tương đương cái kia? Về mặt trực quan thì có thể hiểu như sau: một bài toán khó là bài toán không giải được trong thời gian đa thức; hai bài toán khó tương đương nhau nếu giải bài này một cách hiệu quả thì cũng giải được bài kia một cách hiệu quả và ngược lại. Còn để trả lời nghiêm túc về mặt toán học, thì ta phải xem lại định nghĩa lại khái niệm giải thuật và các thứ liên quan.

Ta sẽ phải quay lại bánh xe lịch sử. Hành trình này đưa ta đến với Cantor, Russell, Hilbert, Gödel, Church, Turing, Cook/Levin, Karp và các ý tưởng tuyệt vời của họ.

Chuyên mục: Lý thuyết tính toán | Bình luận (3) »

Trong loạt bài này, tôi sẽ duyệt qua các ý tưởng lớn và lịch sử xoay quanh một trong những bài toán quan trọng nhất của thế kỷ 21: bài toán “P chọi NP” (P versus NP). Câu trả lời đáng giá 1 triệu USD và danh tiếng đi vào lịch sử khoa học. Cũng như bài toán Fermat lớn, bản thân câu trả lời cho bài “P chọi NP” không quan trọng bằng các kỹ thuật, hướng nghiên cứu, ngành nghiên cứu mới mà người ta khám phá ra để đi đến câu trả lời. (Kiểu ngón tay và mặt trăng của Phật Giáo.)

Quan trọng hơn hết, tôi hy vọng loạt bài này đóng vai trò giới thiệu và khích lệ các bạn đến với một nhánh trung tâm của khoa học máy tính: lý thuyết tính toán và sự phức tạp (computational and complexity theory). Hành trình của ta sẽ ghé qua những vấn đề mà máy tính không giải quyết được, như đã hứa.

In P or not in P, that’s the question!

Đọc các quyển sách về phân tích và thiết kế giải thuật (như CRLS), ta thấy rất nhiều các bài toán thú vị, cực kỳ hữu dụng và đẹp, mà lại có thể giải được trong thời gian đa thức. Ví dụ: xếp thứ tự (sort) n số cần thời gian O(n lg n), tìm đường đi ngắn nhất (shortest path) trong một đồ thị G=(V,E) cần khoảng O(|V|lg|V|+|E|), biến đổi Fourier (FFT) cần O(n lg n), vân vân.

Các vấn đề này đều là các vấn đề then chốt và tự nhiên của các ngành khoa học kỹ thuật như mạng máy tính (bài toán tìm đường), điện/điện tử và xử lý tín hiệu (FFT), cơ sở dữ liệu (xếp thứ tự các records), vân vân. (Các ví dụ nêu ra chỉ mang tính minh họa, các vấn đề tìm đường, xếp thứ tự, FFT, … có cực kỳ nhiều ứng dụng!)

Có lẽ phải giải thích một chút tôi muốn nói gì bằng chữ tự nhiên. Có các vấn đề không tự nhiên. Đó là các vấn đề mà người ta tạo ra chỉ để chứng minh một mệnh đề nào đó hoặc giải quyết một ứng dụng nho nhỏ nào đó, mà không có ứng dụng ở chỗ nào khác. Khi một nhánh nghiên cứu còn non trẻ, sẽ có nhiều vấn đề không tự nhiên kiểu này. Có rất nhiều các bài báo chuyên ngành giải quyết các bài toán đi vào quên lãng ngay sau khi bài báo được đăng. Khi nào có thời gian ta sẽ nói thêm về đề tài này, bản thân tôi nghĩ là nó rất quan trọng cho những ai bắt đầu làm nghiên cứu. Trong giới hạn của bài này, ta cứ nghĩ về “vấn đề tự nhiên” như một vấn đề có nhiều ứng dụng các nơi.

Đến đây nảy ra câu hỏi thú vị: “có thể nào tất cả các vấn đề tự nhiên đều giải được trong thời gian đa thức?” Sau hơn nửa thế kỷ của nghiên cứu giải thuật, về căn bản là ta vẫn chưa trả lời được câu hỏi này. Dường như có rất nhiều bài toán tự nhiên rất khó (theo nghĩa là không có giải thuật hiệu quả để giải). Có khoảng một chục nghìn bài toán tự nhiên kiểu này, thách đố hơn nửa thế kỷ nghiên cứu của các kỹ sư và khoa học gia hàng đầu. Ngược lại, cũng không ai chứng minh được bất kỳ bài nào trong số đó là không có giải thuật hiệu quả để giải.

Ta hãy xem thử một vài bài toán kiểu này:

• Vertex Cover: môt vertex cover của một đồ thị G=(V,E) là một tập S các đỉnh sao cho tất cả các cạnh của G đều kề với một đỉnh trong S. Bài toán này cần tìm vertex cover với kích thước nhỏ nhất.
• 01-Knapsack: một anh ăn trộm tìm được n vật quý, vật quý thứ i nặng w_i cân và đáng giá v_i đồng. Anh ta lại chỉ có thể vác tối đa là W cân. Hỏi: anh ta phải lấy những vật nào để có được tổng giá trị lớn nhất.
• Euclidean Travelling Salesman (Euclidean TSP): tìm đường ngắn nhất cho một anh bán hàng đi qua n thành phố, mỗi thành phố một lần và trở về thành phố đầu tiên.

Chuyên mục: Lý thuyết tính toán | Bình luận (1) »

Ảo thị là đối tượng nghiên cứu thú vị của các bác sĩ mắt và họa sĩ (xem thêm ở đây). Hiện tượng ảo giác nói chung, mà ảo thị là một ví dụ, làm ta đôi khi phải tự hỏi: “làm sao ta biết khi nào ta đang bị ảo giác, khi nào ta đang cảm nhận thực tại?”

Thế kỷ thứ 4 trước công nguyên, Trang Tử đã đặt câu hỏi: “đêm qua ta là Trang Tử mơ làm bướm, hay sáng nay ta là bướm đang mơ làm Trang Tử?” Câu hỏi thật thú vị! Chắc các bạn cũng đã từng tỉnh dậy sau một giấc mơ nào đó và tự hỏi mình đang tỉnh hay đang mơ. Ảo giác chăng? Hay thực tại?

Thế kỷ 17, René Descartes (1596-1650) cũng đặt vấn đề tương tự với thí nghiệm tưởng tượng lừng danh “brains in the vats” (các bộ não trong chum) của ông. Ông lý luận rằng: ta chỉ biết được thực tại qua các trải nghiệm phản ánh bằng các xung trong não, vì thế ta không thể nào biết được cái ta đang nhìn, đang nghe, đang sờ là cái có thật hay không. Vì thế, hoàn toàn có khả năng chúng ta chỉ thuần túy là các bộ não đặt trong một chum thí nghiệm nào đó mà ta không biết.

Nhà toán học John Nash (giải Nobel kinh tế năm 1994), như được miêu tả qua bộ phim tuyệt hay A Beautiful Mind, đã từng bị chứng schizophrenia nhiều chục năm liền, thường xuyên có ảo giác và tưởng tượng những thứ không có thực.

Bộ phim Matrix khai thác ý tưởng này đến đỉnh cao, lồng vào đó các biểu tượng triết học và tôn giáo từ Đông sang Tây. Morpheus hỏi Neo: “thực tại là gì? Nếu anh hiểu thực tại là những thứ anh nhìn thấy, nếm, ngửi, sờ được, thì thực tại chỉ là các xung điện được biên dịch bởi não bộ?” Toàn bộ cái Matrix là một hệ thống ảo giác khổng lồ.

Thế những thứ này có liên quan gì đến khoa học máy tính? Máy tính cũng có các “giác quan” của nó: bàn phím, con chuột, camera là mắt, micro là tai. Thậm chí có cả các nghiên cứu làm thế nào ta có thể điều khiển máy tính bằng ý nghĩ. Thí nghiệm của Descartes đã thành sự thật: các máy tính là các bộ não, mạng Internet là cái chum thí nghiệm của ông.

Một ngày kia, khi máy tính trở nên có ý thức, chúng nó sẽ tự hỏi: “tôi có đang bị ảo giác không nhỉ?”

Chuyên mục: KHMT và triết học | Bình luận (2) »

1. Sơ lược lịch sử

Nếu có một Y2K Bug thật sự thì nó phải là lỗi tràn bộ đệm (buffer overflow bug). Đây là lỗi phổ biến nhất trong các chương trình quan trọng của hệ điều hành và mạng máy tính, bao gồm cả các cơ sở dữ liệu. Lỗi này, trong nhiều trường hợp, cho phép kẻ xâm nhập (intruder) truy cập vào hệ thống nội bộ với đặc quyền của root, hoặc ít nhất là có thể phá hoại rất nguy hiểm (xem các ví dụ dưới đây).

Có hai loại lỗi tràn bộ đệm chính: loại tràn stack (stack-based) và loại tràn heap (heap-based). Gần đây còn có lọai tràn số nguyên (integer overflow) cũng tương tự về nguyên tắc của sự tràn. Ý tưởng căn bản là làm cho dữ liệu tràn vào vùng nhớ chứa thông tin hệ thống. Ví dụ: khi dữ liệu tràn xuống stack của một hàm (function) đang chạy thì dữ liệu có thể đè vào địa chỉ trả về (return address) của hàm làm cho nó trỏ đi chỗ khác. Intruder có thể bỏ một đoạn mã vào “chỗ khác” này để phá phách, truy cập dữ liệu, vân vân. (Chỗ khác này thường là nằm ở chính bộ đệm đang bị tràn.)

Khi mà một quá trình (process) của hệ thống chạy với đặc quyền root, thì lỗi tràn bộ đệm của process này có thể cho phép intruder chạy chương trình với đặc quyền root. Vì thế lỗi này cực kỳ nguy hiểm.

Các khuyến cáo bảo mật của CERT từ 1988 đến nay đã báo hơn 60 lỗi tràn bộ đệm trong các chương trình quan trọng nhất của các hệ thống Windows, Unix, Linux, như MS SQL Server, IIS, Sendmail, httpd, syslogd (nhiều phiên bản và implementations khác nhau đều bị), vân vân. Con số 60 là khá lạc quan, các diễn đàn bảo mật trên Internet báo ra nhiều lỗi hơn nhiều. Bạn có thể tham khảo các websites như SecuriTeam, Security Focus, @stake, hoặc BugTraq mailing list để thấy các ví dụ về các cảnh báo này. Bài viết ở đây có thu thập tổng quan tương đối đầy đủ về lỗi tràn bộ đệm cho đến năm 2000.

Lần đầu tiên lỗi tràn bộ đệm nổi đình nổi đám trên báo chí là ngày 2 tháng 11 năm 1988, khi Robert Tappan Morris (Robert Morris Jr.) – đang học sau đại học ở đại học Cornell – viết thí nghiệm một chương trình có thể tự động “tiêm” bản thân vào Internet. Robert không có ý định làm cho nó lây lan ra nhiều lắm, nhưng bản thân con sâu (worm) của anh ta lại có bug, làm cho nó lan nhanh hơn anh tưởng nhiều lần. Về căn bản, con sâu Internet của Robert tận dụng lỗi tràn bộ đệm trong deamon fingerd của Unix. Một điểm thú vị ít được biết hơn là thời điểm đó cha đẻ của Robert – ông Robert Morris Sr. – đang là khoa học gia đứng đầu của national security agency (NSA).

Sự kiện thứ hai đánh dấu sự lan tràn của kiến thức về lỗi tràn bộ đệm là sự xuất hiện của bài viết “phá stack cho vui và kiếm lợi” của Aleph One năm 1996 trong tạp chí Phrack, tạp chí “ngầm” (underground) có truyền thống nhất trong giới hackers. Aleph One (dĩ nhiên là bí danh) đã viết nhiều ví dụ mã vỏ (shellcodes) và vài phương pháp tổng quát để lợi dụng lỗi này trong các hệ thống máy tính khác nhau. Bài viết này của Aleph One, dù bây giờ đã hơi lỗi thời, vẫn được xem là bửu kíp kinh điển của các lọai khai thác lỗi tràn bộ đệm.

(Aleph Naught – trong lý thuyết tập hợp của Cantor – là lực lượng của tập số tự nhiên, còn Aleph One là lực lượng của tập tất cả các tập con của tập số tự nhiên: bậc vô hạn kế tiếp. Tôi không biết Aleph One có đặt tên mình theo nghĩa này hay không, nhưng tôi không biết nghĩa nào khác của chữ Aleph One. Tạp chí Phrack năm nay sẽ ra bộ cuối cùng rồi đóng cửa, tiếc thật.)

Sau bài của Aleph One, nhiều bài khác cũng được đăng hoặc phát tán trên Internet, mô tả chi tiết các cách tấn công vào nhiều hệ điều hành khác nhau, chạy trên nhiều cấu trúc máy khác nhau. (Xem bài 1, bài 2, bài 3, bài 4, bài 5, bài 6.)

Con sâu Code-Red (và biến thể Code-Red 2) xuất hiện khoảng tháng 7 năm 2001 đã tận dụng một lỗi tràn bộ đệm trong dịch vụ đánh chỉ số (indexing service) của Microsoft IIS server. Con sâu Nimda, xuất hiện chừng một tuần sau sự kiện 9/11 đã tận dụng vài kẽ hở của hệ thống, trong đó có cổng sau (backdoor) do Code-Red để lại.

Gần đây hơn, con sâu W32/Blaster và các biến thể của nó, xuất hiện cỡ tháng 7 năm 2003, gây thiệt hại lớn cho người dùng, cũng đã tận dụng một lỗi tràn bộ đệm trong một bộ phận gọi thủ tục từ xa (remote procedure call – RPC) của Windows. Trên thực tế, nếu kẻ phá họai là lập trình viên tốt hơn thì tai họa đã không dừng ở con số 120 nghìn máy tính bị nhiễm sau 24 giờ.

Tại hội nghị bảo mật mũ đen (black hat security conference) ở Las Vegas ngày 27 tháng 7 năm 2005, Michael Lynn (một nhân viên cũ của công ty Internet Security Systems) trình bày một phương thức tấn công các routers của Cisco chạy hệ điều hành Internetwork (IOS). Bài báo cáo của anh có tên gọi: “Cisco IOS Security Architecture”. Lỗi chính của IOS vẫn là một lỗi tràn bộ đệm kinh điển (cả stack lẫn heap). Nếu bọn phá phách dùng phương pháp này thì có thể nói không ngoa là đa phần Internet sẽ chết ngoẻo củ tỏi. Cisco tìm cách kiện ngay Michael, và cuối cùng Michael và hội nghị này đồng ý không phát tán rộng rãi bài trình bày của Michael và bỏ nó ra khỏi proceedings của hội nghị. Trong thời gian đó, dĩ nhiên Cisco sẽ cố hết sức lấp lỗ hổng này càng nhanh càng tốt.

Đến đây thì có lẽ các bạn đã hiểu tại sao khẳng định buffer overflow bug = Y2K bug là có lý. (Y2K hay năm 2000 thường được dùng với ý nghĩa là bug của thế kỷ, nhưng cái Y2K bug mà người ta hay nói thì tôi cho rằng ngành công nghệ máy tính đã thổi phồng quá đáng để kiếm lợi.)

Chuyên mục: Bảo mật và mật mã học | Bình luận »