“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.)
2 Comments
Ôi, trường phái hình thức và chương trình Hilbert! Thuở còn học PT, tôi cũng từng mơ “sẽ dùng logic để giải quyết hết mọi việc”. Lên đại học, tôi theo đuổi ước mơ của mình bằng logic hình thức, nhưng sớm nhận ra nó chỉ là những trò chơi giữa các ký hiệu. Và đến lần đầu tiên gặp bài toán dừng thì tôi hoàn toàn bỏ qua ý tưởng ngày xưa. Học lên Đại số Trừu tượng thì tôi thấy rõ ý nghĩa của 2 chữ “hình thức” – một cái vỏ bọc – một cái cỗ máy làm việc không độc lập với ý nghĩa bên trong mà con người gán cho nó.
Sau này, khi nghiên cứu về các giới hạn lý thuyết, tôi cho rằng: Giới hạn của các lý thuyết hình thức là N – hệ thống số tự nhiên. Nên Định lý Bất toàn của bác Gödel tuy theo nghĩa hẹp (phát biểu 1) chỉ đụng đến số tự nhiên (và số học), nhưng cũng đủ để nói lên nghĩa rộng (phát biểu 2) của nó, đó là bất kỳ lý thuyết hình thức nào cũng không thể “phán xét” được chính nó một cách hoàn toàn. Tổng quát hơn nữa, ta có thể nói “Không có một hệ thống lý thuyết nào có thể phán xét được chính nó một cách hình thức hoàn hoàn! ” Nghĩa là ta phải biết “hi sinh” cái này để được cái kia, chứ không thể cầu toàn được:
- Hoặc đừng phán xét về chính nó, như hệ thống hình học Euclid;
- Hoặc dùng một hệ thống lý thuyết “mạnh hơn” nó để phán xét nó (như dùng số thực R hay quy nạp trên ordinal chứ không phải trên N để phán xét N), và hiển nhiên trong hệ thống “mạnh đó” ta phải chấp nhận (hay tin tưởng) vào những tiên đề mạnh hơn;
- Hoặc bỏ đi 1 trong cách tính chất: Không cần toàn vẹn (complete) / Không cần nhất quán (consistent) / Không cần hình thức (formal)!
Rốt cuộc, cái ta cần là cái hệ thống lý thuyết đó nó thể hiện đúng cái nội dung mà ta cần. Mà nội dung ta cần thì là không hình thức rồi. Ta không thể nào gạt gỏ hoàn toàn “niềm tin” ra khỏi khoa học được. Chẳng qua là khoa học hiện đại thích “tin vào những cỗ máy (hình thức)” hơn thôi!
Chúng ta nên nghĩ (bên trong) không hình thức, và nói ra (bên ngoài) bằng ngôn ngữ hình thức. Định lý bất toàn cho chúng ta nguồn công việc vô tận, chẳng bao giờ chúng ta phải thất nghiệp cả!
Bằng con đường hình thức, chúng ta chẳng bao giờ đạt được “chân lý tối thượng” mà chúng ta vẫn tham lam muốn có, nhưng với mục tiêu đó thì chúng ta cứ tiệm tiến mãi, gần hơn và ngày càng gần hơn nữa tới chân lý.
- Không có một máy Turing (và chương trình máy tính) nào có thể phán xét được bài toán dừng (cũng như tất cả những bài toán không qua hiển nhiên về chính máy Turing), nhưng không ai cản chúng ta chia mịn và càng mịn hơn độ phức tạp của bài toán ra, thay vì chỉ 0/1 (không dừng, hoặc dừng). Nếu dừng thì dừng trong bao lâu, nếu không biết chắc dừng thì bao nhiêu phần trăm (xác suất) là dừng, v.v.
- Có thể bài toán P chọi NP có độ phức tạp ngang hoặc hơn hệ thống logic hình thức của con người (nghĩa là độc lập với mọi lý thuyết hình thức), nhưng không ai cản chúng ta tìm những heuristic đưa NP về P và chia NP ra thành nhiều “dạng” khác nhau để áp dụng những kỹ thuật tối ưu hoá khác nhau.
Theo cái nhìn của riêng tôi, thì ranh giới giữa P và NP nó cũng phức tạp như ranh giới trong các hình fractal trên mặt phẳng số phức vậy (vd tập Mandelbrot), chỉ cần “nhích” một tí là từ P nhảy sang NP và ngược lại. Nhưng trong cái hỗn loạn có cái trật tự (quy luật), nếu ta nắm được những quy luật của nó (vd dạng fractal của một tập hợp, dạng heuristic của một lớp bài toán) thì ta vẫn có thể tiến bước trên con đường tiếp cận chân lý.
Đính chính:
> ý nghĩa của 2 chữ “hình thức” – một cái vỏ bọc – một cái cỗ máy làm việc
khôngđộc lập với ý nghĩa bên trong mà con người gán cho nó.(Đọc tới đọc lui rồi mà sao vẫn không phát hiện ra lỗi typo ngớ ngẩn đó nhỉ?!)