Chung qui chỉ tại Cantor (5)

 

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

Chung qui chỉ tại Cantor (4)

 

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

Chung qui chỉ tại Cantor (3)

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.

Chung qui chỉ tại Cantor (2)

 

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ọ

Chung qui chỉ tại Cantor (1)

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(VlgV+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

Ảo giác

 

Ả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ỉ?"

Blog cầu (Blogosphere)

Năm 2004, ABC bầu các bloggers (dân viết blog) là các nhân vật trong năm. Theo bài báo thì có nhiều triệu blogs trên Internet, cứ 7 giây rưỡi thì có một blog mới xuất hiện. Hơn 10 nghi`n blogs được thêm vào "blog cầu" (blogosphere) mỗi ngày.

Blogger trẻ nhất chỉ có 11 tuổi. Người ta viết blog từ mọi nơi, về mọi đề tài. Hồi lính Mỹ sắp vào Iraq thì có blog từ Baghdad ( Dear Raed). Về vụ sóng thần thì có Tsunami blog (có đến vài tá blogs viết liên tục từ các vùng bị nạn). Người ta viết blog về chính trị và sex; tình yêu và chủ nghĩa phát xít mới; cảm xúc cá nhân hàng ngày và khoa học máy tính.

Cái gì làm cho nhiều người thích viết blog và nhiều người thích đọc blog? Nhiều lý do lắm. Người viết thích chia sẻ suy nghĩ của mình, và thấy vui khi có người quan tâm. Các đề tài không bị giới hạn bởi một "ban biên tập" nào đó hay kinh tế thị trường. Người đọc cảm thấy có liên hệ cá nhân chặt chẽ hơn sự khô khan của các trang web nói chung. Ta có thể ghi ra một tỉ lý do.

Blogging sẽ còn sống lâu.

Lỗi tràn bộ đệm

 

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

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

Chứng minh kiểm tra được bằng xác suất

 

Các chứng minh kiểm tra được bằng xác suất (Probabilistically Checkable Proofs - PCP) là một trong những đề tài trung tâm của lý thuyết máy tính hiện đại, với rất nhiều ứng dụng trong mật mã học ( cryptography), lý thuyết độ phức tạp tính toán ( computational complexity theory), độ khó của các giải thuật xấp xỉ (hardness of approximation ), vân vân.

Để hiểu sơ bộ về PCP, ta thử xét một trò chơi đơn giản với hai người chơi: người chứng minh (prover), và người xác minh (verifier). Prover có nhiệm vụ thuyết phục verifier về một mệnh đề nào đó mà prover biết cách chứng minh. Ví dụ: giả thuyết Goldbach (Goldbach conjecture) nói rằng các số chẵn lớn hơn 2 đều là tổng của hai số nguyên tố (giả thuyết này chưa ai chứng minh được). Nếu prover biết rằng giả thuyết Goldbach sai, thì prover có thể trình ra cho verifier thấy một số chẵn (> 2). Verifier thử tất cả các cặp số nguyên dương với tổng đã cho, và kiểm tra xem có cặp nguyên tố nào không. Quá trình kiểm tra này có thể rất mất thì giờ (dù là với máy tính), nhưng rõ là làm được trong khoảng thời gian hữu hạn.

Tuy nhiên, nếu tổng số phép tính verifer phải làm quá lớn (10⁸⁰ chẳng hạn), thì "thời gian hữu hạn" cũng bằng vô hạn. (Tổng số nguyên tử trong vũ trụ nhỏ hơn 10⁸⁰. Từ Big Bang đến nay chỉ có khoảng 10 ¹⁷ giây.) Thế có thể nào thiết lập được một nghi thức giao tiếp (interaction protocol) giữa prover và verifier sao cho verifier phải làm ít việc hơn mà vẫn tin chắc (với xác suất cực lớn) là prover có chứng minh đúng? Nếu có nghi thức như vậy thì tổng số bit thông tin verifier phải hỏi prover là bao nhiêu để có độ tin cậy cho trước? Các câu hỏi này là đối tượng của ngành nghiên cứu PCP. Ví dụ: giáo sư Johan Håstad gần đây đã chứng minh được rằng chỉ cần 3 bít nhị phân là verifier có thể có xác suất đúng hơn 1/2. Nếu lập lại nghi thức này 200 lần độc lập nhau thì xác suất đúng là 1 - 1/2 ²⁰⁰, coi như là bằng 1. (Lưu ý: 2²⁰⁰ > 10⁸⁰.)

Tiến sĩ Laci Lovász (thầy của giáo sư Vũ Hà Văn) có một bài viết nho nhỏ với các ví dụ đời thường về các phép chứng minh kiểm tra được bằng xác suất. Một ví dụ thú vị ông đưa ra là: làm thế nào ta thuyết phục nhân viên nhà băng (máy tính) là ta có mật khẩu tài khoản của mình mà không đưa mật khẩu ra. Trong trường hợp này, ta là prover, còn đối phương là verifier!

Khoa học máy tính hay công nghệ thông tin?

 

Cụm từ "công nghệ thông tin" (information technology - IT) có khi được dùng đồng nghĩa với "khoa học máy tính" ( computer science - CS). Không nên đánh đồng IT và CS.

Theo tự điển Wikipedia thì IT là công nghệ dùng để xử lý thông tin, thường dùng theo nghĩa là công nghệ ứng dụng máy điện toán và phần mềm để chuyển đổi, bảo vệ, xử lý, truyền, lưu giữ và truy cập thông tin. Nhưng rõ ràng là các phương tiện thông tin đại chúng như báo chí, đài phát thanh, đài truyền hình, đã dùng các công nghệ khác (trước cả khi có máy tính) để xử lý, phân phối, truyền, lưu trữ và truy cập thông tin! Như vậy, bản thân chữ IT theo định nghĩa này đã có lấn cấn.

CS mang nghĩa rộng hơn IT rất nhiều. Theo tự điển thì CS bao gồm IT cộng thêm một khái niệm rất sâu sắc gọi là sự tính toán ( computation). Giáo sư Don Knuth (giải Turing năm 1974) trong bài "Khoa học máy tính và quan hệ của nó với toán học" (xem một tuyển tập có bài này) viết: "có lẽ hai khoa học gia máy tính sẽ cho bạn hai định nghĩa khác nhau về CS ... Định nghĩa của tôi là: CS là sự nghiên cứu khái niệm giải thuật".

Ta thử lấy ví dụ một đối tượng nghiên cứu của CS không nằm trong IT: lý thuyết tính toán (theory of computation). Đây là một ngành của CS nhằm vào câu hỏi: "cái gì có thể tính được?" Câu hỏi này ngoài ý nghĩa thực tiễn còn mang đậm tính triết học và liên quan mật thiết đến logic. Máy tính đã làm được nhiều việc tuyệt vời, từ đánh cờ thắng Kasparov, mô phỏng Big Bang, đến hiện thực mạng thông tin toàn cầu. Vậy khả năng giới hạn của máy tính là gì? Nó có giới hạn không, hay là vài chục năm nữa sẽ có máy tính thông minh hơn người? Biên giới của các giới hạn, nếu có, là ra sao về mặt thời gian (time) và bộ nhớ (space)? Để trả lời các câu hỏi loại này, ta cần nhiều hơn cái gọi là công nghệ thông tin.

Khi khác ta sẽ trở lại với các vấn đề mà máy tính không giải quyết được. (Không nhất thiết phải là các vấn đề tình cảm đâu nhé.)

Post thôi cũng là một vấn đề rồi

If you typed the page address in the Address bar, make sure that it is spelled correctly.
To check your connection settings, click the Tools menu, and then click Internet Options. On the Connections tab, click Settings. The settings should match those provided by your local area network (LAN) administrator or Internet service provider (ISP).
If your Network Administrator has enabled it, Microsoft Windows can examine your network and automatically discover network connection settings.If you would like Windows to try and discover them

Tiến hóa số

 

Gần đây, bài báo
The Evolutionary Origin of Complex Features; R.E. Lenski, C. Ofria, R.T. Pennock, and C. Adami, Nature 423 (2003) 139-145.

mô tả một nghiên cứu thú vị ở phòng nghiên cứu sự sống số (Digital Life Lab) của trường CalTech về việc mô phỏng tiến hóa sinh học (evolution) bằng máy tính.

Đại khái, ta có thể nghĩ về một quá trình máy tính (process) như một vi khuẩn. Các processes "ăn" các số nguyên (integers) và thực hiện một vài tác vụ ngẫu nhiên trên các integers mà nó ăn bằng một bộ lệnh ngẫu nhiên cho trước. Các processes có thể tự tái sinh và thay đổi tập lệnh của nó một cách ngẫu nhiên (random mutation) giống như quá trình tiến hóa sinh học. Nếu một process "tiến hóa" đến mức có thể làm một số tác vụ nhất định với các integers, như "so sánh hai integers", "cộng hai integers", vân vân, thì nó sẽ được "thưởng" bằng cách cho tăng tần suất tái sinh của process.

Khá nhiều các giả thuyết về tiến hóa sinh học được khẳng định bởi tiến hóa trong môi trường số này. Ví dụ như sau vài chục ngàn thế hệ, bọn vi khuẩn số này đều có thể cộng hoặc so sánh các integers. Điểm thú vị là bọn chúng không nhất thiết có tập lệnh giống nhau!

Giáo sư Manuel Blum

 

Học kỳ trước giáo sư Manuel Blum (giải thưởng Turing năm 1995) đến chỗ tôi nói chuyện về dự án CONSCS của ông. CONSCS vừa là viết tắt của cụm từ CONceptualizing Strategizing Control Systems, vừa chơi chữ vì CONSCS đọc giống từ conscious (ý thức). Khi đó dự án này còn chưa được viết và nộp cho NSF. Đại khái là ông muốn lý thuyết hóa khái niệm "ý thức" để có thể tạo các hệ thống máy tính "có ý thức". Đây là một trong các vấn đề then chốt của trí tuệ nhân tạo. Không chỉ liên quan đến khoa học máy tính, đề tài này liên quan mật thiết đến cả triết học và khoa học về não bộ.

Ý thức là gì? Theo tự điển Wikipedia thì đại lọai ý thức là một nhân tố tinh thần bao gồm các khả năng như tự biết mình (self-awareness), nhận thức được liên hệ giữa bản thân và môi trường, vân vân. Cái máy tính Deep Blue đánh thắng Kasparov, dù rất phức tạp và "thông minh", nhưng ta tin rằng nó không ý thức được sự tồn tại của nó và việc nó đang làm. Con kiến, con sâu thì lại có (vẻ có) ý thức.

Mô hình hóa và mô phỏng ý thức, nếu "thành công", thì sẽ là một bước tiến nhảy vọt trong nhận thức của chúng ta về máy tính và về quá trình suy nghĩ của chính mình.

Một điểm thú vị về giáo sư Blum là cả vợ ông ( Lenore BLum) và con trai (Avrim Blum) đều là các khoa học gia xuất sắc và đều ở khoa máy tính của CMU.

Ông hay cho sinh viên lời khuyên về viết lách như sau: 1. Có gì đó để viết, 2. Viết, 3. Viết xong thì dừng, 4. Đặt tựa bài cho hay (John Shaw Billings [1838-1913]). Giáo sư Blum đã hướng dẫn và tốt nghiệp rất nhiều các nhà khoa học đầu ngành máy tính như Gary Miller (CMU), Michael Sipser (MIT), Vijay Vazirani (Georgia Tech), Umesh Vazirani (Berkeley), vân vân. Danh sách học trò ông quả thực là đáng ngưỡng mộ

Đế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.
• Thế các tác giả sách thì sống thế nào? Dĩ nhiên tác giả phải được trả công xứng đáng.
• 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.
• Khi nội dung sách được “mở” cho mọi người phê bình, làm thế nào quản lý được sự hỗn độn này?
• 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 mà lần tới tôi sẽ đề cập.

 

 

---

Start your day with Yahoo! - make it your home page

Từ một giấc mơ

Những bài viết này tôi copy của GS Ngô Quang Hưng, Pro.CSE of Buffalo.

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 AIDS 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 ta đượ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?

Các bài báo kinh điển của KHMT (1)

Giáo sư Christo H. Papadimitriou dạy một lớp với nội dung dựa trên các bài báo kinh điển của KHMT. Lấy cảm hứng từ lớp này, tôi sẽ bắt đầu một series mới các bài về đề tài này.Mỗi post sẽ giới thiệu một bài báo kinh điển, không theo một trật tự nhất định nào. "Kinh điển" cũng không đồng nghĩa với "cổ điển". Tôi sẽ giới thiệu cả các bài báo gần đây mà vẫn có thể xếp vào loại kinh điển. Hy vọng các bloggers khác của blog này sẽ thêm vào các bài báo kinh điển mà họ thích.Mặc dù tựa đề của post là "các bài báo kinh điển trong KHMT", các bài báo sẽ được trình bày trong series này không nhất thiết là chỉ thuộc về "KHMT". Có rất nhiều các bài báo có ảnh hưởng sâu sắc đến KHMT nhưng đã được viết trong một ngữ cảnh khác.Bài hôm nay là của Claude E. Shannon: C. E. Shannon, ``A mathematical theory of communication,'' Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948. Bài báo này đánh dấu sự ra đời của lý thuyết thông tin. Để nói về ảnh hưởng sâu sắc của bài báo này nói riêng và của Shannon nói chung đến KHMT hiện đại thì ta cần vài quyển sách. Ta tóm tắt ở đây vài khái niệm và kết quả kinh điển từ bài báo này: Lần đầu tiên xác suất được áp dụng vào phân tích truyền thông. Ngày nay thì các phân tích và mô hình hóa bằng xác suất trong KHMT và truyền thông phổ dụng đến mức ta khó có thể tưởng tượng ý tưởng này mới như thế nào khi Shannon viết bài này. Ý tưởng đột phá là "thông tin" (bất kể nguồn loại gì) về căn bản là mang tính số (digital). Dấu ấn của ý tưởng này trên các ngành công nghệ hiện đại nằm ở mọi nơi: lưu trữ thông tin (CD, đĩa cứng), truyền thông tin (mạng máy tính), vân vân. Khái niệm "bit" thông tin được giới thiệu lần đầu tiên. Khái niệm "entropy" thông tin ra đời, dùng để đo "độ phức tạp" hay "độ ngẫu nhiên" của nguồn thông tin. Nói nôm na thì entropy của một tín hiệu thông tin đại diện cho "tổng số thông tin" mà tín hiệu này mang. Các kênh thông tin có một dung tích (channel capacity) mà nếu ta truyền tín hiệu với tốc độ nhỏ hơn nó thì tồn tại một cách mã hóa (code) tín hiệu mà nhờ đó ta có thể đạt được xác suất lỗi nhỏ tùy ý. Phát biểu này đại khái là nội dung của định lý noisy channel coding lừng danh. Bài báo cũng đặt nền tảng cho ngành nén dữ liệu (data compression), mã hóa và giải mã tín hiệu với khả năng phát hiện lỗi (error-detection code) và sửa lỗi (error-correction code). Xem thêm quyển sách kinh điển này. Nhờ bài báo này, truyền thông có thể hiểu nôm na là bao gồm 3 bước chính: mã hóa tín hiệu, truyền tín hiệu qua kênh thông tin, và giải mã tín hiệu. Nhà toán học vĩ đại Kolmogorov từng nói về Shannon như sau Trong thời buổi mà kiến thức nhân loại càng lúc càng đuợc chuyên môn hóa, Claude Shannon là một nhà khoa học ngoại lệ. Shannon kết hợp các ý tưởng toán học sâu sắc với các hiểu biết rộng và cụ thể của các vấn đề quan trọng bậc nhất của công nghệ. Shannon là một trong những nhà toán học vĩ đại nhất đồng thời là một trong những kỹ sư giỏi nhất trong vài thập niên qua.