Gödel, the Progenitor of Computer Science / Gödel, ông tổ của khoa học computer

Henri Poincaré, the greatest mathematician in the late 19th century and early 20th century, once said “the history of science must be our guide”. Today, computer science is one of the most important sciences, but many people don’t know where it comes from. This is a gap of knowledge which will be filled by the following story.

Henri Poincaré, nhà toán học vĩ đại nhất cuối thế kỷ 19 đầu thế kỷ 20, từng nói “lịch sử khoa học phải là người hướng dẫn cho chúng ta”. Ngày nay, khoa học computer là một khoa học quan trọng bậc nhất, nhưng rất nhiều người không biết nó bắt nguồn từ đâu. Đó là một lỗ hổng về kiến thức sẽ được lấp đầy bởi câu chuyện sau đây.

Chú thích ảnh trên: Từ Gödel  đến khoa học computer. Tháng 09/1930, ở tuổi 25, Kurt Gödel  lần đầu tiên đã trình bày Định lý Bất toàn của mình trước các nhà toán học hàng đầu đương thời, tại một hội nghị ở Königsberg. Trong số thính giả có John von Neumann, nhưng David Hilbert vắng mặt…

Như chúng ta đã biết, Định lý Gödel là một định lý của logic toán học, nhưng ý nghĩa của nó đã vượt khỏi phạm vi toán học để tác động lên hết thảy mọi lĩnh vực của khoa học và triết học về nhận thức.

Computer là một cỗ máy logic tiêu biểu, vì thế tác động của Định lý Gödel đối với computer cũng biểu lộ rõ ràng và tiêu biểu đến mức mọi người đều có thể nhận thấy.

Thí dụ điển hình là “Sự cố Dừng” (The Halting Problem) − một sự cố do Alan Turing khám phá ra từ năm 1936, khi ông phác thảo thiết kế một chiếc máy tính hoạt động theo chương trình, được gọi là “máy Turing”, thực chất là một chiếc computer. Sự cố dừng khẳng định rằng không thể đoán trước một chương trình computer sẽ chạy mãi mãi hay ngẫu nhiên sẽ bị dừng. Sự cố này nói lên tính bất toàn của computer, và là một biểu hiện cụ thể của Định lý Bất toàn trong khoa học computer, như bây giờ chúng ta đã biết rõ. Tuy nhiên, vào thời điểm nó ra đời, sự cố dừng không làm ai chú ý. Mãi cho tới những thập kỷ cuối thế kỷ 20, khi khoa học computer phát triển mạnh mẽ, sự cố dừng mới trở thành một hiện tượng phổ biến đến mức ai cũng có thể gặp. Đó là lúc nhân loại mới thực sự bừng tỉnh để nhận ra ý nghĩa và vài trò cực kỳ quan trọng của Định lý Bất toàn đối với khoa học computer nói riêng và khoa học về nhận thức nói chung. Sự thức tỉnh này lộ rõ qua hiện tượng “bùng nổ” sách báo giới thiệu về Định lý Gödel trong các hiệu sách và trên các diễn đàn học thuật tại các quốc giả phát triển trong những năm cuối thế kỷ 20, mặc dù định lý này đã ra đời từ năm 1931.

Đọc những sách báo đó, chúng ta sẽ thấy rõ mối quan hệ gắn bó chặt chẽ giữa Định lý Gödel với khoa học computer. Điều này rất dễ hiểu, vì Định lý Bất toàn nói về tính bất toàn của một hệ logic, và computer chính là hệ logic điển hình! Quan hệ đó được thể hiện trong sơ đồ dưới đây:

Sơ đồ trên cho thấy Định lý Bất toàn có 2 tác động lớn đến khoa học computer:  

  1. Tác động thể hiện nguyên lý bất toàn của các hệ logic: Định lý Gödel là cơ sở khoa học để chứng minh tính bất toàn của computer. 
  2. Tác động về mặt kỹ thuật: Chứng minh của Định lý Gödel là nguồn gốc dẫn tới khoa học phần mềm của computer. 

Trong câu chuyện hôm nay, chúng ta sẽ thảo luận về tác động thứ hai, để hiểu tại sao Định lý Gödel được xem như nguồn gốc của khoa học computer, và tại sao Gödel được xem như ông tổ của khoa học này.

Henri Poincaré, nhà toán học vĩ đại nhất cuối thế kỷ 19 đầu thế kỷ 20, từng khuyên các nhà giáo dục rằng một nền giáo dục khôn ngoan phải dẫn dắt người học đi qua những chặng đường mà khoa học đã trải qua, với thời gian rút ngắn nhưng không được bỏ qua một chặng nào cả. Với cách nhìn đó, “lịch sử khoa học phải là người hướng dẫn cho chúng ta”[1].  

Vậy muốn hiểu bản chất của khoa học computer, phải nắm được lịch sử của khoa học computer. Lịch sử ấy đã được trình bày ngắn gọn những rất sáng sủa, rõ ràng trong một bài giảng nhan đề “Kurt Gödel and the origins of computer science”[2] (Kurt Gödel và nguồn gốc của khoa học computer) của John Dawson, Giáo sư toán học tại Đại học Tiểu bang Pennsylvania ở Mỹ.

Ngay trong lời mở đầu, Dawson khẳng định:

Được xem như nhà toán học logic vĩ đại nhất thế kỷ 20, Gödel là một trong những nhà sáng lập của lý thuyết hàm đệ quy[3] (recursion theory). Là một đồng nghiệp của Alonzo Church và John von Neumann tại Viện nghiên cứu cao cấp Princeton, ảnh hưởng của ông đối với khoa học computer tuy ở bước phôi thai, nhưng tác động gián tiếp rất rộng”.  

Nhận định của Dawson xuất phát từ một thực tế là những kỹ thuật do Gödel sáng tạo ra để chứng minh Định lý Bất toàn đã trở thành những mẫu mực để các nhà lập trình sau này noi theo áp dụng. Vì thế, Douglas Hofstadter, Giáo sư về khoa học nhận thức của Đại học Idiana và nhiều  đại học lớn khác ở Mỹ, nhận định “Gödel là nhà phát minh thực sự của ngôn ngữ lập trình và cấu trúc dữ liệu”[4]. Tất nhiên Gödel không đoán trước được điều đó, vì ông không phải là nhà tiên tri. Nhưng những gì ông phát minh ra để chứng minh Định lý Bất toàn đã trở thành những “cẩm nang” chủ yếu cho khoa học về phần mềm của computer sau này áp dụng. Vì thế Gödel được xem như ông tổ của khoa học computer. Vì computer là một cỗ máy thông tin (cỗ máy lưu trữ, xử lý và chế biến thông tin), các khái niệm cơ bản của thông tin ra đời từ khoa học computer, nên Gödel  cũng được coi là ông tổ của lý thuyết thông tin, đúng như nhận định của George Gilder, rằng: “Gödel là ông tổ của Lý thuyết Thông tin và là gương mặt chủ yếu của lịch sử tư tưởng hiện đại”[5].

Chú ý rằng Gödel không chỉ khám phá ra Định lý Bất toàn, mà còn khám phá ra nhiều định lý khác, chứng minh được nhiều bài toán khác, và tất cả đều là những định lý lớn, những bài toán lớn của toán học và logic toán trong thế kỷ 20. Hơn nữa, không chỉ Định lý Bất toàn đóng góp vào việc xây dựng nền tảng cho khoa học phần mềm của computer, mà hầu như toàn bộ các công trình về logic toán học của Gödel đều đóng góp cho khoa học phần mềm của computer. Cụ thể là những công trình sau đây:

  1. Định lý về tính đầy đủ (Completeness Theorem), công bố năm 1930 (luận án tiến sĩ của Gödel).  
  2. Định lý Bất toàn (Incompleteness Theorem), 1931.
  3. Công trình về những bài toán quyết định (Paper on Decision Problems), 1932-1933.
  4. Định nghĩa khái niệm hàm đệ quy tổng quát (Definition of the notion of general recursive function), bài giảng năm 1934, công bố năm 1965.
  5. “Về độ dài của chứng minh” (On the lengths of proofs), 1936
  6. “Một số định lý cơ bản về nền tảng toán học, và ý nghĩa triết học của nó” (Some basic theorems on the foundations of mathematics, and their philosophical implications), bài giảng tại Gibbs, 1951.
  7. “Thư gửi John von Neumann” (Letter to von Neumann), 1956.
  8. “Một sai lầm triết học trong công trình của Turing” (A philosophical error in Turing’s work), 1972, công bố lần đầu năm 1974.

Tuy nhiên, trong tất cả các công trình nói trên, công trình chứng minh Định lý Bất toàn đóng góp nhiều nhất và quan trọng nhất cho sự hình thành của khoa học phần mềm của computer. Đóng góp này lớn đến mức Định lý Bất toàn được coi như nguồn gốc của khoa học computer. Tất cả các nhà khoa học phần mềm của computer có thể tự hào rằng ông tổ nghề nghiệp của mình không phải ai khác, mà chính là Kurt Gödel, tác giả của Định lý Bất toàn nổi tiếng!

Đó là lý do để John Dawson nhấn mạnh:

Đối với sự phát triển của khoa học computer, chứng minh của Định lý Bất toàn mà Gödel đã áp dụng còn quan trọng hơn chính bản thân Định lý Bất toàn!

Nhận định này không có ý hạ thấp ý nghĩa toán học và triết học của Định lý Bất toàn, mà chỉ cốt nhấn mạnh vai trò quyết định của định lý này trong việc tạo ra nền tảng ngôn ngữ cho khoa học computer.

Cụ thể, công trình chứng minh Định lý Bất toàn của Gödel chứa đựng 3 kỹ thuật đóng vai trò đặc biệt quan trọng đối với khoa học computer:

  1. Định nghĩa của Gödel về lớp các hàm mà ngày nay ta gọi là “hàm đệ quy nguyên thuỷ” (primitive recursive functions).
  2. Việc Gödel phân biệt toán học (ngôn ngữ toán học) với các mệnh đề nói về toán học (siêu ngôn ngữ của toán học).
  3. Phương pháp mã hoá (hoặc số hoá) do Gödel sáng tạo cho phép biến các mệnh đề tự quy chiếu thành các mệnh đề toán học, từ đó chỉ ra sự tồn tại của các mệnh đề toán học mâu thuẫn hoặc các mệnh đề đúng nhưng không thể chứng minh.

Ai có thể hiểu thấu đáo ý nghĩa của 3 kỹ thuật độc đáo nói trên? Đó là những nhà khoa học computer có đủ kiến thức về logic toán để hiểu rõ các chi tiết chứng minh Định lý Gödel. Tuy nhiên những thảo luận sau đây có thể cung cấp cho mọi người một vài khái niệm tối thiểu về 3 kỹ thuật đó.

Phương pháp số hoá, sáng tạo thiên tài của Gödel 

Trong chương 4, chúng ta đã biết rằng tiếng Việt là một siêu ngôn ngữ của tiếng Anh nếu nó được sử dụng để giải thích ý nghĩa của tiếng Anh. Đó là trường hợp tiếng Việt được sử dụng trong từ điển Anh-Việt. Tương tự, siêu toán học là một siêu ngôn ngữ của toán học, vì siêu toán học là một lý thuyết giải thích về toán học. Cụ thể, siêu toán học muốn chứng minh rằng toán học là một hệ logic đầy đủ và nhất quán. Tóm lại, siêu toán học là một tầng ngôn ngữ bên trên toán học, hoặc bên ngoài toán học. Nhưng điều trớ trêu là siêu toán học, trong khi muốn chứng minh rằng toán học là đầy đủ và phi mâu thuẫn, lại sử dụng chính toán học để làm việc đó. Có nghĩa là siêu toán học bị rơi vào cái bẫy của nghịch lý tự quy chiếu. Đó là lý do để siêu toán học thất bại.

Thí dụ, khi Hilbert xây dựng Hệ tiên đề của Hình học Euclid, trong nhiều chứng minh ông đã phải sử dụng đến số học, tức là phải sử dụng đến một siêu ngôn ngữ của hình học. Do đó, bài toán về hệ tiên đề hình học quy về bài toán hệ tiên đề số học. Nhưng làm thế nào để chứng minh tính đầy đủ và nhất quán của hệ tiên đề số học? Đây chính là Bài toán số 2 do Hilbert nêu lên trong Hội nghị Toán học Quốc tế ở Paris năm 1900. Muốn giải bài toán này, ắt phải nhờ cậy đến một siêu ngôn ngữ của số học. Nhưng siêu ngôn ngữ của số học là cái gì? Nếu lại dùng hình học để phán xét số học thì sẽ thành một vòng logic luẩn quẩn. Vậy không tồn tại một siêu ngôn ngữ nào của số học để giải Bài toán số 2. Nói cách khác, Bài toán số 2 không giải được (unsolvable), tham vọng của Bài toán số 2 là bất khả thi (impossible). Đó chính là hệ quả của Định lý Gödel.

Thực ra tham vọng xây dựng hệ tiên đề cho hình học (Hệ tiên đề Hilbert) hoặc cho số học (Bài toán số 2) chỉ là những biểu hiện cụ thể của một tham vọng tổng quát của Hilbert, đó là xây dựng một hệ tiên đề đầy đủ và nhất quán cho toàn bộ toán học, để khẳng định rằng:

“Toán học là một hệ logic đầy đủ và nhất quán, tức là hoàn hảo” (*)

Dễ thấy mệnh đề (*) là một mệnh đề siêu ngôn ngữ của toán học, tức là một mệnh đề của siêu toán học, thay vì của toán học. Để chứng minh (*) đúng, lại phải nhờ cậy đến một siêu ngôn ngữ của siêu toán học, tức là một siêu ngôn ngữ bậc 2 của toán học! Nhưng siêu ngôn ngữ bậc 2 của toán học là gì? Giả sử tồn tại siêu ngôn ngữ bậc 2 của toán học, thì đến lượt nó, lại cần đến siêu ngôn ngữ bậc 3 của toán học. Quá trình ấy tiếp diễn vô hạn, không có điểm dừng. Do đó, việc chứng minh mệnh đề (*) là bất khả thi.

Với con mắt logic sắc sảo, Gödel đã nhận ra tính bất khả thi của chương trình Hilbert. Do đó, thay vì chạy theo Hilbert như phần lớn các nhà logic đầu thế kỷ 20, Gödel định hướng nghiên cứu của mình theo chiều ngược lại, tức là chứng minh rằng:

“Toán học hoặc không đầy đủ hoặc không nhất quán, tức là bất toàn” (**)

Chú ý rằng (**) cũng là một mệnh đề nằm trong siêu toán học, bởi vì đó là một nhận định về toán học. Để tránh rơi vào cạm bẫy của việc chứng minh siêu toán học, Gödel đã tìm ra một con đường hoàn toàn khác với con đường mà các nhà toán học khác đã đi. Và đây chính là chỗ và là lúc thiên tài của Gödel lộ rõ:

Thật vậy, Gödel đã sáng tạo ra một phương pháp tài tình có một không hai, đó là phương pháp mã hoá hoặc số hoá, cho phép biến một mệnh đề tự quy chiếu thành một mệnh đề toán học, cuối cùng ông đã chỉ ra sự tồn tại của một mệnh đề toán học đúng, nhưng không thể chứng minh. Đó chính là nội dung của định lý 1 của Định lý Bất toàn, rằng trong toán học luôn luôn tồn tại những mệnh đề không thể quyết định được, tức là không thể chứng minh và cũng không thể bác bỏ. . 

Ý tưởng số hoá của Gödel quả thật là một phát minh thiên tài, bởi lẽ nó đã biến một mệnh đề bên ngoài toán học, tức một mệnh đề siêu ngôn ngữ của toán học, thành một mệnh đề toán học, mà tính đúng/sai của nó đã được xác định từ trước, không cần phải nhờ cậy đến siêu ngôn ngữ bậc 2 của toán học nữa. Điều kỳ lạ hơn nữa là phương pháp số hoá này lại trở thành một kỹ thuật đắc dụng cho khoa học lập trình sau này. Và không chỉ phương pháp số hoá, kể cả việc xây dựng các hàm đệ quy trong chứng minh của Định lý Gödel cũng trở thành một “bí quyết” của khoa học lập trình. Không ai có thể đoán trước điều đó, kể cả bản thân Gödel. Câu chuyện về “Tháp Hà-nội” sau đây sẽ làm sáng tỏ điều đó.

Tháp Hà-nội

Nhiều người Hà-nội có thể không biết Tháp Hà-nội, nhưng rất nhiều người trên thế giới lại biết rõ. Ấy là vì Tháp Hà-nội là một bài toán rất nổi tiếng trong chương trình khoa học computer dành cho sinh viên những năm đầu tại các trường đại học ở nhiều nơi trên thế giới.

Tương truyền rằng ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi tận viễn đông, tại thành phố Hà-nội của Việt Nam, vị quân sư của hoàng đế vừa qua đời, hoàng đế cần một vị quân sư thay thế. Bản thân hoàng đế cũng là một nhà thông thái nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư.

Bài toán của hoàng đế gồm n cái đĩa (ngài không nói rõ chính xác là bao nhiêu) và 3 cái trục: A là trục nguồn, B là trục đích, và C là trục trung chuyển. Các đĩa có kích thước khác nhau và có lỗ ở giữa để có thể lồng vào các trục theo quy định nhỏ trên lớn dưới. Đầu tiên các đĩa được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục B, với điều kiện chuyển từng cái một và luôn luôn phải đảm bảo quy định nhỏ trên lớn dưới, biết rằng trục C được phép sử dụng làm trung chuyển.

Vì địa vị quân sư được coi là vinh hiển nên có rất nhiều người dự thi. Từ vị học giả đến bác nông phu, họ đua nhau trình lên hoàng đế lời giải của mình. Nhiều lời giải dài tới hàng nghìn bước, và nhiều lời giải có chữ “chuyển sang bước tiếp theo”. Nhưng hoàng đế thấy mệt mỏi vì những lời giải đó quá rắc rối, nên cuối cùng ngài hạ chiếu: “Ta không hiểu những lời giải này. Phải có một cách giải nào khác dễ hiểu và nhanh chóng hơn”. May mắn thay, cuối cùng đã có một cách giải như thế.

Thật vậy, ngay sau khi vua ban chiếu, một nhà hiền triết trông bề ngoài giống như một kỳ nhân đã hạ sơn tới triều đình xin yết kiến hoàng đế. Nhà hiền triết nói: “Thưa bệ hạ, bài toán đố đó dễ quá, hầu như nó tự giải cho nó”. Quan trùm cấm vệ đứng hầu ngay bên cạnh vua quắc mắt nhìn gã kỳ nhân, muốn quẳng gã ra ngoài, nhưng hoàng đế vẫn kiên nhẫn tiếp tục lắng nghe. “Nếu chỉ có 1 đĩa thì …, nếu có nhiều hơn 1 đĩa ( n > 1 ) thì …”, cứ thế vị cao tăng bình tĩnh giảng giải. Im lặng được một lát, cuối cùng hoàng đế sốt ruột gắt lên: “Được, thế nhà hiền triết có định nói cho ta hiểu rõ lời giải hay không đây?”. Thay vì giải thích tiếp, gã kỳ nhân mỉm cười thâm thuý rồi biến mất, bởi vì gã nhận thấy hoàng đế tuy rất giỏi nhưng rõ ràng là không hiểu ý nghĩa của phép truy hồi (recursion), hay còn gọi là phép đệ quy. Nhưng các bạn sinh viên ngành khoa học computer ngày nay có thể hiểu, và sẽ thấy lời giải của vị cao tăng là hoàn toàn đúng.

Toàn bộ câu chuyện trên được trích từ cuốn “Giải toán nâng cao và cấu trúc dữ liệu” (Intermediate problem solving and data structures) do Paul Henman và Robert Veroff, hai giáo sư Đại học New Mexico, cùng biên soạn với Frank Carrano, giáo sư Đại học Rhode Island. Đây là sách giao khoa dành cho sinh viên năm thứ hai ngành thuật toán và lập trình tại Mỹ, Úc,…

Bạn nào chưa từng biết Tháp Hà-nội tưởng cũng nên “thử sức” một lần xem sao, vì đây là một trò chơi rất thú vị. Bạn có thể bắt đầu bằng bài toán 3 đĩa, rồi nâng lên 4 đĩa. Với 4 đĩa chắc bạn bắt đầu thấy rắc rối. Nâng tiếp lên 5 và cao hơn nữa, chẳng hạn n = 1.000.000, bài toán sẽ rắc rối đến mức không ai đủ kiên trì và đủ thì giờ để thử từng đĩa một. Vậy mà gã kỳ nhân dám nói là dễ quá! Xin tiết lộ, ấy là vì gã đó đã sử dụng phép truy hồi – một quy tắc toán học cho phép xác định số hạng thứ n từ số hạng đứng trước nó, tức số hạng thứ (n 1) . Cái giỏi của nhà hiền triết là ở chỗ tìm ra một quy tắc chung, tức một thuật toán chung cho tất cả các bước chuyển đĩa. Vậy thay vì mô tả toàn bộ quá trình chuyển đĩa từng cái một như mọi thí sinh trước đó đã làm, đến nỗi làm cho hoàng đế mỏi mệt vì phải nghe quá nhiều bước chuyển, nhà hiền triết chỉ mô tả một quy tắc chung đó mà thôi. Cứ làm theo quy tắc đó lặp đi lặp lại chẳng cần suy nghĩ gì rồi cuối cùng tự nhiên sẽ đạt tới đích. Vì thế nhà hiền triết mới nói rằng bài toán này “tự nó giải nó”. Tiếc rằng nhà vua không được học kỹ thuật lập trình, nên ngài không hiểu.

Trong khoa học tính toán ngày nay, phép truy hồi là thuật toán cơ bản để lập trình. Ưu điểm của phương pháp truy hồi là ở chỗ nó dùng một công thức nhất định để diễn tả những phép tính lặp đi lặp lại bất chấp số lần lặp lại là bao nhiêu. Nếu số lần lặp lại lên đến con số hàng triệu hàng tỷ thì con người không đủ sức và thời gian để làm, nhưng máy tính thì có thể giải quyết trong chớp mắt. Sự thần thánh của computer chính là ở chỗ nó không hề biết e ngại và mệt mỏi trước những công việc lặp đi lặp lại nhàm chán như thế. Vì thế, sự cộng tác giữa con người với computer là mô hình lý tưởng của lao động trí óc trong cuộc sống hiện tại và tương lai. Trong sự cộng tác này, việc gì computer không thể làm thì con người phải làm. Việc lập trình là việc của con người. Việc thực hiện chương trình là việc của computer.

Có người đặt câu hỏi, rằng trong toán học có rất nhiều công thức truy hồi, và tất cả mọi người đều biết điều này, vậy việc Gödel sử dụng công thức truy hồi để chứng minh định lý của ông đâu phải là một sáng tạo đặc biệt?

Quả thật là toán học có rất nhiều công thức truy hồi, chẳng hạn:

  • Công thức cấp số cộng: Un = Un-1 + d
  • Công thức cấp số nhân: Un = (Un-1).q

Nhưng việc phát hiện ra khả năng áp dụng công thức truy hồi vào một bài toán lại là một vấn đề hoàn toàn khác. Cụ thể, đứng trước một nhiệm vụ cần giải quyết, bạn có nhận ra cách giải quyết nào là tiện lợi nhất và đơn giản nhất hay không, điều này đòi hỏi một tầm nhìn sáng tạo. Thí dụ, hãy thử giải bài toán hình học sau đây:

Cho một đường tròn tâm O, và hai đường kính vuông góc với nhau là AB và CD. Gọi E và F lần lượt là trung điểm của OA và OB. Gọi giao điểm của đường thẳng CE với đường tròn là G. Chứng minh GF vuông góc với FC

Đây là một bài toán đánh lừa nhiều học trò, vì thực ra GF không vuông góc với FC, mà chỉ gần vuông. Tất nhiên có nhiều cách giải bài toán này. Bằng hình học thuần tuý, có thể chứng minh rằng GF không vuông với FC, mặc dù nhìn bằng mắt, ai cũng có cảm giác GF vuông với FC. Tuy nhiên, chứng minh hình học đòi hỏi trực giác hình học rất sắc sảo. Trong khi Hình học Giải tích cho phép chứng minh một cách nhanh chóng, đơn giản và dễ dàng rằng GF gần vuông với FC. Vậy, đứng trước bài toán nói trên, vấn đề là bạn có nhìn thấy khả năng giải bài toán này một cách nhanh chóng, tiện lợi bằng cách áp dụng Hình học Giải tích hay không?

Trước khi René Descartes và Pierre de Fermat nghĩ ra Hình học Giải tích, bài toán hình học nói trên là bài toán rất khó. Nhưng từ khi có Hình học Giải tích ra đời, bài toán ấy trở nên vô cùng đơn giản, ai cũng làm được, nếu đã học môn học này.

Trong thời đại computer, hình học giải tích càng tỏ ra hữu hiệu hơn, bởi nó cho phép chương trình hoá các bài toán hình học thành một chuỗi các phép toán số học, do đó có thể giao cho computer – những chiếc máy “ngu ngốc” – làm thay con người!

Hoàn toàn tương tự, trong cuộc sống, khi phải đối mặt với rất nhiều bài toán khác nhau, bạn có nhận ra những bài toán nào có thể chương trình hoá bằng cách áp dụng công thức truy hồi để tính toán hay không. Một nhà lập trình tồi có thể không nghĩ tới điều này. Nhưng một nhà lập trình giỏi, nhất là giỏi toán, sẽ nghĩ tới điều đó, vì công thức truy hồi, như câu chuyện Tháp Hà-nội đã mách bảo, là một công cụ tuyệt vời, cho phép thay thế những mạch logic rất phức tạp thành một công việc đơn giản lặp đi lặp lại để cho những chiếc máy “ngu ngốc” như computer có thể giải quyết. Người đầu tiên nhận thấy sự kỳ diệu của các hàm đệ quy, tức các công thức truy hồi, như một “phép mầu” để giải quyết những nhiệm vụ phức tạp, chính là Kurt Gödel!

Tất nhiên ông không khám phá ra “phép mầu” đó trong công việc lập trình, mà trong công việc chứng minh Định lý Bất toàn năm 1930, khi chưa hề có computer. Thật vậy, việc chứng minh Định lý Bất toàn dẫn Gödel tới những tình huống rất giống với những tình huống mà các chuyên gia lập trình ngày nay gặp phải:  

Những gì Gödel phải đối mặt trong khi chứng minh Định lý Bất toàn rất giống với những gì mà các chuyên gia thiết kế ngôn ngữ lập trình và viết chương trình ngày nay phải đối mặt”.

Đó là nhận định của Martin Davis, Giáo sư toán học và khoa học computer tại Đại học New York, một trong những nhà khoa học computer lớn nhất hiện nay. Davis còn nói rõ hơn rằng:

Bất kỳ ai đã quen thuộc với ngôn ngữ lập trình hiện đại đều nhận thấy toàn bộ cấu trúc chứng minh của Định lý Gödel trông rất giống như một chương trình computer”.

Vậy điều khác nhau giữa Gödel và các nhà khoa học computer ngày nay là ở chỗ nào?

Đó là sự khác nhau về chỗ đứng của con người trong lịch sử:

Công trình của Gödel ra đời năm 1931, khi chưa có computer. Do đó Gödel là một nhà phát minh, một nhà sáng tạo, một ông tổ của khoa học computer, một ngành khoa học mới làm thay đổi triệt để bộ mặt của nền văn minh. Dù ông không đoán trước được sự ra đời của ngành khoa học này, ông vẫn là ông tổ của nó. Đây là nhận định rất quan trọng, cần phải được nhắc đi nhắc lại nhiều lần, bởi lẽ khoa học computer là một khoa học then chốt trong nền văn minh hiện đại, vậy mà đến nay nhiều người vẫn chưa biết rõ nguồn gốc của nó. Đã 88 năm trôi qua, đã quá muộn để biết điều đó. Nhưng muộn còn hơn không bao giờ. Vậy xin nhắc lại một lần nữa:

“Gödel là nhà phát mình thực sự của ngôn ngữ lập trình và cấu trúc dữ liệu” (Douglas Hofstadter)

“Gödel là ông tổ của Lý thuyết Thông tin và là gương mặt chủ yếu của lịch sử tư tưởng hiện đại” (George Gilder)

Câu chuyện không dừng lại ở đó.

Thật vậy, sự phát triển của khoa học computer, đến lượt nó, lại dẫn tới sự bùng nổ của một loạt các ngành khoa học mũi nhọn khác, như khoa học về trí thông minh nhân tạo, tức AI (Artificial Intelligence), khoa học thần kinh hiện đại (modern neurology), khoa học về nhận thức (cognitive science),… Tất cả những lĩnh vực nghiên cứu này đều xoay quanh chủ đề con người. Vì thế, Định lý Gödel cũng đóng một vai trò to lớn trong các khoa học về con người. Đó là một hệ quả rất bất ngờ nhưng vô cùng thú vị.

Thực tế, từ những thập kỷ cuối thế kỷ 20 đến nay, vấn đề nghiên cứu bản chất con người dưới ánh sáng của khoa học computer và lý thuyết thông tin ngày càng trở thành một chủ đề trung tâm của khoa học hiện đại, được thảo luận sôi nổi qua nhiều lăng kính: toán học, vật lý học, y học, sinh học, tâm lý học, triết học,… Trong những thảo luận này, có hai luồng tư tưởng xuất hiện, tranh chấp với nhau: Trong khi các chuyên gia về trí thông minh nhân tạo khẳng định computer sẽ thông minh như con người, “trường phái Gödel ” khẳng định đó là tham vọng không tưởng!

Định lý Gödel sẽ đóng vai trò quan toà để phán xử ai đúng!

 

PVHg, Sydney 19.03.2019 (Mừng sinh nhật KMy)


[1] La tâche de l’éducateur est de faire repasser l’esprit de l’enfant par où a passé celui de ses pères, en passant rapidement par certaines étapes mais en n’en supprimant aucune. À ce compte, l’histoire de la science doit être notre guide. https://en.wikiquote.org/wiki/Henri_Poincar%C3%A9

[2] https://slideplayer.com/slide/3614792/

[3] Còn gọi là “công thức truy hồi” (công thức tính toán theo kiểu lặp đi lặp lại). Một phương pháp cơ bản của các chương trình tính toán tự động là thiết lập các công thức truy hồi.

[4] Đã dẫn trong Lời Nói Đầu.

[5] Đã dẫn trong Lời Nói Đầu

Advertisements

12 thoughts on “Gödel, the Progenitor of Computer Science / Gödel, ông tổ của khoa học computer

  1. Đề nghị anh Hưng không nên đề tặng bài viết của mình cho một ai đó khi đã quảng bá bài viết, nhất lại là một cái tên có vẻ như của một phụ nữ. Người đọc sẽ cảm thấy như không phải để dành cho mình. Tất nhiên người ta vẫn đọc nhưng hiệu ứng tôi nghĩ là không như những bài viết khác. Có nhiều cách để tặng ai đó nhân ngày sinh nhật một cái gì đó, nhưng chắc chắn không phải là vật phẩm mà mọi người khác cũng sử dụng.

    Số lượt thích

    • “Đây là một bài toán đánh lừa nhiều học trò, vì thực ra GF không vuông góc với FA, mà chỉ gần vuông.” Mạo muội kính thưa Giáo sư, rằng có vẻ như có lỗi chính tả trong câu trên; cụ thể là FC có vẻ như bị viết nhầm thành FA!?

      Số lượt thích

  2. “Đây là một bài toán đánh lừa nhiều học trò, vì thực ra GF không vuông góc với FA, mà chỉ gần vuông”.
    Mạo muội kính thưa Giáo sư, rằng câu trên có vẻ như có một lỗi chính tả; cụ thể, FC có thể bị viết nhầm thành FA chăng?
    Cảm ơn Giáo sư đã đọc phản hồi này!

    Số lượt thích

  3. Xin lỗi anh Hưng,tôi muốn đặt câu hỏi này ở phần hội thảo về nguồn gốc sự sống.Anh cho phép tôi chuyển câu hỏi về phần đấy nhé.Cám ơn anh !

    Số lượt thích

  4. Pingback: Phạm Việt Hưng's Home - Lục Phong writing

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s