Kurt Gödel is considered the Progenitor of Computer Software Science. Why? The answer lies in the book “Gödel’s Proof, Revised Edition” by E. Nagel and J. Newman. Here is a brief introduction to that book, written by Engineer Anh Dung Le, and I would like to introduce it to the readers …

Kurt Gödel được coi là Ông tổ của khoa học phần mềm computer. Tại sao? Câu trả lời nằm trong cuốn sách “Chứng minh của Gödel, Phiên bản sửa đổi” của E. Nagel và J. Newman. Sau đây là một giới thiệu tóm tắt cuốn sách đó, do Kỹ sư Lê Anh Dũng thực hiện. Xin trân trong giới thiệu cùng độc giả … 

LỜI GIỚI THIỆU

Lê Anh Dũng là một kỹ sư điện tử – viễn thông rất năng động, hiện là Phó Giám đốc Trung tâm Hạ tầng Số, Tổng Công ty Truyền thông Đa Phương tiện.

Kỹ sư Lê Anh Dũng là một trong những người say mê Định lý Gödel mà tôi quen biết. Chúng tôi thảo luận với nhau nhiều đề tài khoa học, nhưng chủ đề được quan tâm nhiều nhất vẫn là Định lý Gödel, đặc biệt là vai trò nền tảng của định lý này trong khoa học máy tính.

Khi biết tôi quan tâm đến bài báo của Natalie Wolchover trên tạp chí Quanta Magazine ngày 14/07/2020, kỹ sư Lê Anh Dũng liền gửi ngay cho tôi một giới thiệu tóm tắt về một tài liệu quan trọng liên quan với bài báo này. Đó là cuốn sách “Gödel’s Proof, Revised Edition” của Ernest Nagel and James Newman. Cuốn sách này là một “cẩm nang” trình bày một cách hệ thống mạch lạc từng bước chứng minh của Gödel, tương đối dễ hiểu đối với một người có trình độ toán đại học và chăm chỉ nghiên cứu. Bản tóm tắt của kỹ sư Lê Anh Dũng đặc biệt nhấn mạnh đến ba kỹ thuật tài tình trong chứng minh của Gödel – những kỹ thuật đã trở thành công cụ nền tảng của khoa học lập trình – qua đó giải thích tại sao Gödel được tôn vinh là Ông tổ của ngôn ngữ lập trình và cấu trúc dữ liệu.

Sau đây, xin trân trọng giới thiệu với độc giả lời giới thiệu tóm tắt của kỹ sư Lê Anh Dũng.

    

TÓM TẮT CỦA KS LÊ ANH DŨNG

Trong cuốn “Gödel’s Proof, Revised Edition” (Chứng minh của Gödel, Phiên bản sửa đổi) của Ernest Nagel và James R. Newman, được biên tập và bổ sung “Lời nói đầu mới” bởi Douglas Hofstadter, Giáo sư về khoa học nhận thức tại Đại học Indiana ở Mỹ, các tác giả đã đưa ra những đánh giá chính xác về vai trò của Định lý Gödel đối với sự ra đời của khoa học máy tính. Những đánh giá này có thể tóm tắt cô đọng như sau:

“Đối với sự phát triển của khoa học máy tính, chứng minh định lý bất toàn quan trọng hơn chính các định lý. Ba khía cạnh của chứng minh có ý nghĩa đặc biệt là:

1/ Phương pháp mã hóa:

Phương pháp mã hóa hay còn gọi là phương pháp đánh số Gödel (Gödel numbering), biến các mệnh đề logic hình thức thành các con số duy nhất, gợi ý cho các nhà phát triển ngôn ngữ lập trình máy tính bậc thấp và ngôn ngữ lập trình bậc cao thiết kế ngôn ngữ lập trình của mình. Các tác giả đánh giá: Đột phá thiên tài vĩ đại của Gödel là nhận ra rằng các con số là một phương tiện phổ quát truyền tải các kiểu mẫu thông tin thuộc bất kỳ loại nào, và vì lý do đó, các phát biểu dường như chỉ nói về các con số trên thực tế có thể mã hóa các phát biểu về các lĩnh vực khác nhau của diễn ngôn. Nói cách khác, Gödel đã nhìn xa hơn cấp độ bề mặt của lý thuyết số, nhận ra rằng các con số có thể biểu diễn bất kỳ loại cấu trúc nào. Bước nhảy vọt của Gödel đối với [lĩnh vực khoa học] máy tính là vì máy tính về cơ bản thao tác với các con số và vì các con số là phương tiện phổ quát để truyền tải các mẫu thông tin thuộc bất kỳ loại nào, nên máy tính có thể xử lý các mẫu tùy ý, cho dù chúng logic hoặc phi logic, nhất quán hoặc không nhất quán.

2/ Định nghĩa về khái niệm lớp:

Trong lập trình hướng đối tượng, lớp (class) là một chương trình-mã-khuôn mẫu có thể mở rộng được để tạo các đối tượng, cung cấp giá trị khởi tạo cho trạng thái (biến thành viên) và hiện thực của hành vi. Một cách giản lược, lớp là khái niệm và là một nỗ lực nhằm giảm nhẹ các thao tác viết mã cho người lập trình. Lớp là một trong những lý thuyết quan trọng bậc nhất của lập trình hướng đối tượng. Và chính Gödel là người đã định nghĩa chính xác về lớp (hiện được gọi là) các hàm đệ quy nguyên thủy, khởi đầu cho việc ứng dụng lý thuyết lớp vào ngôn ngữ lập trình bậc cao. Ngày nay, các giải thuật đệ quy vẫn được sử dụng phổ biến trong lập trình. Nhờ vào việc cài đặt đơn giản, ngắn gọn nên giải thuật đệ quy được áp dụng trong nhiều bài toán mà nếu sử dụng lời giải lặp thì rất khó để lập trình, tiêu biểu như giải thuật “sắp xếp nhanh” (quick sort). Ở một số bài toán phức tạp, việc chuyển giải thuật đệ quy sang giải thuật không đệ quy là việc không đơn giản, cần có sự am hiểu về thuật toán và sự tinh tế nhất định, nên giải thuật đệ quy mặc dù có nhược điểm là thời gian thực hiện lớn vẫn luôn luôn có chỗ đứng của nó.

3/ Sự phân biệt của Gödel giữa ngôn ngữ đối tượng và siêu ngôn ngữ:

Trong một chương trình, ngôn ngữ lập trình đơn giản là tập hợp các hướng dẫn hoặc dòng lệnh giúp cho máy tính biết những gì nó cần làm. Ngôn ngữ đánh dấu được sử dụng để chuẩn bị cấu trúc cho dữ liệu hoặc chuẩn bị cho giao diện hoặc thiết kế của trang web. Việc Gödel phân biệt giữa ngôn ngữ đối tượng và siêu ngôn ngữ cũng là gợi ý cho các nhà thiết kế ngôn ngữ lập trình, đặc biệt là ngôn ngữ lập trình web tham khảo trong quá trình thiết kế ngôn ngữ. Ngoài ra, như Martin Davis đã nhận xét, cấu trúc tổng thể của việc chứng minh định lý của Gödel trông rất giống một chương trình máy tính. Đối với bất kỳ ai quen thuộc với các ngôn ngữ lập trình hiện đại thì không có gì đáng ngạc nhiên, vì mặc dù “một máy tính lập trình thực sự… có mục đích chung… vẫn còn là tương lai hàng thập kỷ”. Gödel đã phải đối mặt với nhiều vấn đề tương tự như những gì những người thiết kế ngôn ngữ lập trình và… viết chương trình bằng các ngôn ngữ đó phải đối mặt ngày nay. Cụ thể: Khi bắt đầu trình bày chứng minh, Godel cũng tiến hành đặt các biến số của chương trình, bao gồm đặt tên biến, lựa chọn kiểu dữ liệu của biến: biến hằng số, biến hàm, biến vị ngữ, sau đó ông cũng định nghĩa lớp các hàm đệ quy nguyên thủy rồi sau đó xây dựng các hàm từ các phát biểu logic hình thức để giải quyết các bước chứng minh. Quá trình này rất giống với các bước một nguời lập trình phần mềm thực hiện việc viết một chương trình máy tính”. [hết tóm tắt]

………

Xin chân thành cảm ơn KS Lê Anh Dũng và chúc độc giả thành công trong việc tìm hiểu vài trò nền tảng của Định lý Gödel đối với khoa học máy tính.

PVHg, Ngày 06/06/2024