Gödel’s Theorem & AI / ĐL Gödel và Trí thông minh nhân tạo
Tôi hân hạnh giới thiệu đến bạn đọc bài viết “Định lý bất toàn của Gödel và sự xuất hiện của AI” của Eberhard Schoneburg, nhà khoa học tiên phong về AI (Trí tuệ nhân tạo), với hy vọng độc giả sẽ tìm thấy ở đây nhiều lợi ích cho khoa học, kỹ thuật và triết học…
Xin trân trọng giới thiệu với độc giả bài báo “Định lý Bất toàn của Gödel và sự xuất hiện của khoa học trí thông minh nhân tạo” của Eberhard Schoneburg, một nhà khoa học tiên phòng về AI (Trí thông minh nhân tạo). Hy vọng độc giả sẽ tìm thấy ở đây nhiều ích lợi cho khoa học, công nghệ và triết học.
Say đây là toàn văn bài báo bằng tiếng Anh:
Vào năm 1931, ở tuổi 25, nhà toán học trẻ người Áo Kurt Goedel đã chứng minh được một định lý toán học đáng kinh ngạc khiến ông ngay lập tức nổi tiếng và nổi tiếng trong giới toán học khắp thế giới (xem hình; trong văn học Anglo-Saxon, Goedel thường được nhắc đến là “Godel” bỏ qua âm Umlaut trong tên tiếng Đức của anh ấy).
Mặc dù có bản chất rất trừu tượng và không có ứng dụng thực tế hàng ngày, định lý Goedel - còn gọi là Định lý Bất toàn - đã có tác động mạnh mẽ và sâu sắc đến bản thân toán học và nền tảng của nó. Nó cũng có tác động đáng kể đến triết lý của thế kỷ 20 và sự hiểu biết của chúng ta về những hạn chế chung của máy tính và thuật toán.
Ở đây tôi sẽ giải thích tại sao định lý Goedel thực sự đã gây ra sự xuất hiện của ngành khoa học mới về Trí tuệ nhân tạo (AI) và khoa học máy tính lý thuyết trong những năm 1940 và 1950 cũng như cách nó thúc đẩy những người tiên phong chủ chốt về AI như Alan Turing tham gia. Sự ra đời của AI và quá trình AI đã thực hiện kể từ đó chỉ có thể được đánh giá cao và hiểu rõ khi người ta tính đến định lý Goedel và tác động của nó. Goedel còn có nhiều khám phá mang tính đột phá khác ngay cả trong Thuyết tương đối tổng quát của Einstein, nơi ông đưa ra lời giải cho các phương trình vi phân của Einstein cho phép du hành thời gian – ít nhất là về mặt lý thuyết (xem hình trên; Einstein và Goedel đã trở thành bạn thân trong thời gian họ cùng học tại Princeton).
Một số nhà khoa học hàng đầu như Ngài Roger Penrose thậm chí còn lập luận rằng Goedel đã chứng minh qua Định lý Bất toàn của mình rằng máy tính ngày nay không bao giờ có thể đạt tới trí thông minh hoặc ý thức ở cấp độ con người, rằng con người sẽ luôn thông minh hơn máy tính hiện tại hoặc bất kỳ thuật toán máy tính nào có thể có và máy tính sẽ không bao giờ có thể đạt được. ý nghĩa thực sự của từ “hiểu” bất cứ điều gì như toán học cấp cao hơn, đặc biệt không phải là toán học liên quan đến các tập hợp và số hữu hạn.
Định lý Goedel thực sự nói một cách chi tiết và cách nó tác động đến AI ngay cả ngày nay sẽ trở nên rõ ràng và dễ hiểu hơn sau khi chúng ta xem nhanh lịch sử toán học và logic cũng như cách thức và lý do tại sao chúng ta đi đến điểm có sự tham gia và định lý của Goedel.
Georg Cantor – Vũ trụ của những điều vô tận
Là hệ quả và sản phẩm phụ của cuộc cách mạng công nghiệp thế kỷ 19, vật lý lý thuyết và toán học có thời kỳ “bùng nổ cumbrian” vào nửa sau và đặc biệt là trong 1/4 cuối thế kỷ 19. Nhiều nhà toán học (và nhà vật lý học) nổi tiếng đã tạo ra những lý thuyết mới hấp dẫn và khám phá ra những kết quả toán học sâu sắc và sâu rộng. Trong số đó có nhà toán học thiên tài người Đức Georg Cantor.
Cantor (ảnh bên trái) đã phát minh ra cái gọi là “lý thuyết tập hợp” mà sau này được chứng minh là có thể xây dựng cơ sở và nền tảng cho tất cả các ngành toán học. Lý thuyết tập hợp hiện nay vẫn được giảng dạy ở các trường tiểu học trên toàn thế giới để dạy cho trẻ em những khái niệm cơ bản về toán học trừu tượng. Tuy nhiên, Cantor ban đầu không được coi là thiên tài (điều đó chỉ xảy ra khoảng 30 năm sau) mà ông bị các đồng nghiệp công kích khá mạnh vào thời điểm những năm 1870 và 1880.
Điều này là do Cantor đã tự tay mở rộng khái niệm của chúng ta về tập hợp hữu hạn thành tập hợp vô hạn và xa hơn nữa. Ông đã phát hiện ra một điều nổi tiếng rằng một khi người ta cho phép các tập hợp vô hạn tồn tại dưới dạng đối tượng toán học, thì người ta có thể tạo ra cả một vũ trụ gồm nhiều tập hợp vô hạn hơn. Ông đặc biệt phát hiện ra rằng vô cực không giống với vô cực. Có thể có nhiều loại vô cực khác nhau. Đó là một kết quả rất đáng ngạc nhiên đối với các nhà toán học ở thời của ông (và vẫn là kết quả như vậy đối với hầu hết mọi người ngày nay).
Ví dụ, ông đã chứng minh rằng các số tự nhiên “N”: 1, 2, 3, 4, 5, 6, 7…, v.v., khi được coi là một tập hợp đầy đủ, là loại tập hợp vô hạn nhỏ nhất có thể có. Tập hợp N này có một số tính chất lạ không thể có đối với các tập hợp hữu hạn, ví dụ: N có chính xác số phần tử bằng một nửa tập hợp N ! Điều này rất dễ nhận thấy. Chỉ lấy tập hợp con các số chẵn từ N: 2, 4, 6, 8, 10…, v.v. và gọi tập hợp này là N2. Khi đó người ta có thể xếp các số của N vào mối quan hệ khớp 1-1 với các phần tử của N2 như sau: 1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, v.v., ánh xạ mọi số n từ N đến 2n từ N2. Do đó, mỗi số N sẽ được ánh xạ chính xác tới một số N2 và ngược lại, nên cả hai tập hợp đều có số phần tử giống hệt nhau. Thực tế, điều đó đúng với bất kỳ tập con vô hạn nào của N, không chỉ riêng N2!
Đặc điểm này của N thực sự có thể được sử dụng để xác định vô cùng. Một tập hợp là vô hạn nếu nó có thể chứng minh được rằng có một ánh xạ 1-1 giữa chính nó và một tập hợp con thực sự của chính nó. Cantor đã đưa ra khái niệm trực quan về ánh xạ 1-1 để xác định và so sánh kích thước của các tập hợp vô hạn (được gọi là lượng số của một tập hợp).
Đây chỉ là một ví dụ tầm thường. Cantor tỏ ra có kết quả thú vị và đáng ngạc nhiên hơn nhiều. Ví dụ, ông đã chứng minh rằng các số hữu tỷ (tập hợp tất cả các thương của các số tự nhiên như 3/4, 9/7 hoặc 145/11) vẫn có thể được tính bằng số tự nhiên N và do đó cũng nhiều như N (xem hình bên trái cho thấy cách đếm các số hữu tỉ). Ông cũng chứng minh rằng tập hợp số vô tỷ là những số không thể biểu diễn dưới dạng phân số của số tự nhiên (như Pi, e hay căn bậc hai của 2), không thể đếm được bằng số tự nhiên. Vì vậy, tập hợp các số vô tỷ (và do đó cũng là tập hợp số thực R) có nhiều phần tử (số lượng phần tử cao hơn) so với N và do đó không thể đếm được.
Ông đã chứng minh điều này bằng cách sử dụng cấu trúc “đường chéo” nổi tiếng của mình (xem hình bên dưới) cho thấy rằng bất kỳ danh sách được liệt kê đầy đủ nào gồm các số vô tỷ hoặc số thực R sẽ luôn bỏ sót một số số vô tỷ, từ đó chứng minh rằng việc liệt kê đầy đủ các số thực theo phương pháp tự nhiên. con số là không thể. Điều này phần nào gây ngạc nhiên vì về mặt trực giác, dường như có ít số vô tỉ hơn số hữu tỉ vì chúng khó tạo ra hơn.
Tính không đếm được của số vô tỷ cũng có nghĩa là trên thực tế có ít nhất hai loại số vô hạn khác nhau: số vô hạn đếm được và số không đếm được. Cantor thực tế đã chỉ ra rằng thậm chí còn có vô số các tập hợp vô hạn lớn hơn bao giờ hết bằng cách chỉ ra rằng tập hợp tất cả các tập con của bất kỳ tập hợp vô hạn đã cho nào luôn lớn hơn đáng kể (không thể đưa vào mối quan hệ 1-1) so với chính tập hợp đó.
Những kết quả này ban đầu khá đáng lo ngại và phản trực giác và khiến các nhà toán học đồng nghiệp của ông cảm thấy rất khó chịu về lĩnh vực toán học mới này. Cantor không có phương pháp nào có thể xây dựng các tập hợp vô hạn bằng các phương pháp hữu hạn mà ít nhất về nguyên tắc có thể được xác minh bằng các phương pháp hiện có vào thời đó. Chưa bao giờ trong lịch sử toán học có vô số vì các vật thể hoàn chỉnh lại được nghiên cứu một cách nghiêm túc. Nhưng Cantor đã chỉ bằng một nét thiên tài đã giới thiệu một vũ trụ toán học hoàn toàn mới gồm những vô hạn khác nhau.
Điều đó khiến các bạn cùng lứa của anh ấy khó nuốt trôi mặc dù họ nhận ra và phải thừa nhận rằng thế giới mới của vô số tập hợp vô hạn thật hấp dẫn và là một công trình tuyệt đẹp với những định luật toán học mới đáng kinh ngạc chi phối chúng. Chúng có vẻ nhất quán về mặt logic và là sự mở rộng của toán học hữu hạn sang thế giới siêu hữu hạn (mặc dù không ai biết làm thế nào điều này có thể được áp dụng vào thế giới thực mà chúng ta đang sống).
Là một người theo đạo, Cantor đã không tạo điều kiện dễ dàng hơn cho những người cùng lứa tuổi đang gặp khó khăn của mình chấp nhận những điều vô hạn mới, những phương pháp mới, những kiểu chứng minh và khái niệm mới của ông bằng cách tuyên bố rằng chính Chúa đã ban cho ông trực giác cho công trình lý thuyết tập hợp của ông và việc khám phá thế giới. của tập hợp vô hạn. Sự “biện minh” này của Cantor cho lý thuyết tập hợp mới của ông và các tập hợp hữu hạn là quá nhiều đối với nhiều đồng nghiệp của ông và không thể chấp nhận được. Một lời biện minh chắc chắn và khách quan hơn là rất cần thiết. Vì không có phương pháp hữu hạn nào để xây dựng và kiểm tra các thuộc tính của các tập hợp hữu hạn, làm thế nào người ta có thể đảm bảo rằng các thuộc tính của các tập hợp này không dẫn đến mâu thuẫn?
Gottlob Frege - Cha đỡ đầu của logic và triết học ngôn ngữ hiện đại
Cuộc chiến và tranh luận giữa Cantor và các đồng nghiệp toán học của ông đã thu hút sự chú ý của một nhà toán học thiên tài người Đức khác tên là Gottlob Frege (xem hình bên dưới). Frege một mặt vui mừng về những tiến bộ to lớn mà toán học đã đạt được trong nhiều lĩnh vực vào thời của ông nhưng cũng kinh hoàng trước sự thiếu chặt chẽ và chính xác rõ ràng cũng như sự thiếu vắng nền tảng khoa học vững chắc của toán học vào thời điểm đó. Sự sáng tạo mà các nhà toán học đã thể hiện trong nhiều lĩnh vực không phù hợp với tính chặt chẽ cần có của một ngành khoa học cơ bản và quan trọng như toán học. Suy cho cùng, chính toán học đã đưa ra khái niệm “chứng minh” và tính chặt chẽ của khoa học kể từ thời Hy Lạp cổ đại.
Ông quan tâm nhất đến khái niệm toán học là thứ được tạo ra và hướng dẫn bởi “trực giác” của một số người như Cantor đã tuyên bố hoặc các hoạt động tinh thần khác. Lập trường của ông rất mạnh mẽ theo chủ nghĩa Platon và chỉ theo hướng ngược lại. Đối với ông, các chân lý toán học phải khách quan và các phát biểu toán học phải đúng hoặc sai độc lập với các hoạt động tinh thần hoặc trực giác của nhà toán học.
Để chứng minh lập trường của mình, Frege đã phát triển triết lý ngôn ngữ và toán học của riêng mình. Ông đã viết một loạt bài báo triết học xuất sắc và có ảnh hưởng về ngôn ngữ và toán học, đặc biệt là về ý nghĩa và ý nghĩa của từ, vị ngữ, câu và khái niệm vẫn được coi là kinh điển và ngày nay phải đọc trong các lớp triết học. Triết lý ngôn ngữ của ông đã gây ấn tượng và ảnh hưởng mạnh mẽ đến cả những triết gia vĩ đại như Ludwig Wittgenstein và Betrand Russell, đồng thời đưa Frege trở thành cha đẻ của triết học ngôn ngữ hiện đại, đặc biệt phổ biến ở thế giới Anglo-Saxon trong thế kỷ 20.
Frege nhận ra rằng có hai vấn đề toán học chính dẫn đến mọi lập luận. Đầu tiên, không có ngôn ngữ khoa học ngắn gọn và chính xác để mô tả các đối tượng và bằng chứng toán học phức tạp. Không có ngôn ngữ chính xác thì không thể có bất kỳ bằng chứng hoặc khái niệm toán học chính xác nào. Các nhà toán học ở thời của ông thường trộn lẫn các biểu thức mơ hồ và không xác định từ ngôn ngữ tự nhiên hàng ngày với ngôn ngữ toán học và các khái niệm toán học phức tạp. Trong mắt ông, điều này là nguyên nhân chính dẫn đến sự nhầm lẫn và sai sót trong các phát biểu và chứng minh toán học.
Thứ hai, ông nhận ra rằng toán học cần một cơ sở sâu sắc hơn để trên đó người ta có thể xây dựng tất cả các khái niệm mới và thậm chí cả các đối tượng siêu hữu hạn của Cantor. Frege xác định logic là nền tảng cơ bản hơn. Xét cho cùng, logic theo một nghĩa nào đó đơn giản hơn nhiều so với toán học và chỉ có một vài quy tắc và khái niệm rõ ràng.
Do đó, ông tin rằng logic dễ hiểu, dễ đồng ý và cơ bản hơn toán học. Ngoài ra, ông tin rằng tất cả các khái niệm và phương pháp toán học thực sự có thể bắt nguồn từ các khái niệm và phương pháp logic cơ bản hơn. Bất cứ khi nào các nhà toán học cần chứng minh một phát biểu toán học, họ cần tuân theo các quy tắc và nguyên tắc logic hợp lệ, nếu không thì bằng chứng có thể và thường sẽ có sai sót.
Tuy nhiên, logic được biết đến vào thời Frege là tầm thường và không có nhiều ứng dụng và về cơ bản vẫn bao gồm những tam đoạn luận hàng nghìn năm tuổi của các triết gia Hy Lạp. Logic của họ không đủ và không đủ biểu cảm để xử lý các cấu trúc và bằng chứng phức tạp của khoa học và toán học hiện đại.
Vì vậy, Frege bắt đầu giải quyết hai vấn đề này và dành phần còn lại của cuộc đời học thuật của mình và vài thập kỷ để phát triển một logic tinh tế hơn, mạnh mẽ hơn cũng như một ngôn ngữ khoa học chính xác có thể mô tả và diễn đạt toàn bộ toán học hiện đại.
Vì điều này, Frege đã tạo ra một ngôn ngữ biểu tượng 2 chiều hoàn toàn mới (xem hình bên phải) mà ông gọi là “Begriffsschrift” trong tiếng Đức hoặc “Ngôn ngữ khái niệm” trong tiếng Anh.
Sau đó, ông cho thấy lý thuyết tập hợp và số học, lý thuyết về số tự nhiên (nằm ở cốt lõi của hầu hết toán học), có thể được mô tả và xây dựng bằng ngôn ngữ khoa học 2 chiều mới của ông kết hợp với các phần mở rộng mới của lý thuyết cổ điển. Hợp lý.
Ông đã làm việc trong nhiều thập kỷ cho nhiệm vụ lớn lao này, hầu như hoàn toàn đơn độc và không có nhà toán học nào khác hợp tác. Trên thực tế, ông đã gặp khó khăn lớn khi xuất bản cuốn sách của mình với Begriffsschrift này vì vào thời điểm đó, việc in và xuất bản một kịch bản 2 chiều độc đáo như vậy rất tốn kém. Cuối cùng anh ấy chỉ xuất bản nó bằng cách tự trả tiền in. Bất chấp mọi nỗ lực của ông, chủ nghĩa biểu tượng 2-D và ngôn ngữ khoa học với tính chặt chẽ độc đáo và không gì sánh được của Frege đã không thể tồn tại được trong ông.
Tuy nhiên, điều khiến ông sống sót là những cách thức mới để mở rộng logic cổ điển và tất cả những cách này vẫn được sử dụng trong toán học và đặc biệt là logic toán học ở khắp mọi nơi ngày nay.
Logic cổ điển được các nhà triết học vĩ đại Hy Lạp cổ đại hình thành đầu tiên chủ yếu là logic mệnh đề. Nó được đưa ra để cho phép đánh giá về tính đúng đắn và giá trị của các lập luận triết học và chủ yếu được sử dụng để xác định các quy tắc về cách rút ra chính xác các mệnh đề từ các mệnh đề khác. Người ta có thể xây dựng các quy tắc đơn giản như: Nếu A đúng và nếu B đúng thì “A và B” cũng vậy. Hay những kết luận như: Nếu A đúng và nếu “A ngụ ý B” đúng thì B đúng. Logic cổ điển cũng cho phép phán đoán đơn giản về các giả định như: Nếu tất cả X là Y và nếu tất cả Y là Z thì tất cả X là Z (ví dụ: nếu tất cả người Hy Lạp là người châu Âu và tất cả người châu Âu đều là con người thì tất cả người Hy Lạp cũng là con người) .
Frege thấy rằng những quy tắc và định luật logic đơn giản này cần được mở rộng và cải tiến để hình thành các cấu trúc toán học thậm chí rất đơn giản (như “2+2=4”) và các đối tượng như các hàm toán học. Để giải quyết vấn đề này, ông đưa ra khái niệm biến logic (thường được ký hiệu là x, y, z) và các vị từ logic là thuộc tính của các biến này (thường được ký hiệu là P(x), Q(y) hoặc R(x,z) ). Ông đã suy nghĩ rất nhiều về câu hỏi ý nghĩa và ngữ nghĩa của các biến và vị ngữ như vậy là gì, làm thế nào chúng có thể được giải thích một cách chính xác (điều này đã trở thành câu hỏi trọng tâm trong triết học ngôn ngữ của ông). Cuối cùng, ông định nghĩa ngữ nghĩa và ý nghĩa của các vị từ logic giống như các tập hợp Cantor, như “phần mở rộng” của chúng như Frege sẽ nói và ý nghĩa của các biến với tư cách là thành viên tiềm năng của các tập hợp đó.
Do đó, phần mở rộng của một vị từ (hoặc ý nghĩa của nó) chỉ đơn giản là tập hợp tất cả các đối tượng đáp ứng vị từ đó. Ví dụ, anh ta có thể định nghĩa một vị từ M với một biến x được viết là M(x). M(x) đúng nếu x thỏa mãn vị từ M. Giả sử M là vị từ “là nam”. Khi đó với mọi x, M(x) đúng khi và chỉ nếu x là nam (và sai nếu x là nữ).
Nếu một vị từ có nhiều hơn một biến thì nó được gọi là quan hệ. Ví dụ, vị từ B được định nghĩa là “lớn hơn” có hai biến x và y với B(x,y) là đúng khi và chỉ khi x lớn hơn y. Vì vậy, nếu B(x,y) đúng thì B(y,x) phải sai. Ông cũng xác định ngữ nghĩa của toàn bộ câu. Một phát biểu toán học được hình thành tốt phải đúng hoặc sai (nguyên tắc thứ ba bị loại trừ).
Ý nghĩa của một câu đối với Frege chỉ đơn giản là giá trị chân lý của nó, đúng hay sai. Để phân biệt giữa ý nghĩa của một biểu thức (nó biểu thị và đại diện cho cái gì) và các khía cạnh tinh tế hơn về cách chúng ta hiểu một biểu thức, ông đã sử dụng thuật ngữ “giác quan”. Vì vậy, ý nghĩa của “4” và “2+2” là cùng một đối tượng, nhưng ý nghĩa của hai cách diễn đạt này là khác nhau. Đó là lý do tại sao đối với các phương trình Frege như “a=a” và “4=2+2” có cùng ý nghĩa, nhưng ý nghĩa và giá trị nhận thức rất khác nhau. “a=a” là một phát biểu đúng cho bất kỳ a nào và không cho chúng ta biết điều gì ngoài sự thật đó. Tuy nhiên, “4=2+2”, tưởng chừng như tầm thường, lại cho chúng ta biết điều gì đó về kết quả của việc áp dụng thao tác “+” cho một số số. “a=a” là một mệnh đề lặp thừa thuần túy, có giá trị phổ quát, trong khi “4=2+2” là một mệnh đề số học cần được chứng minh là đúng.
Với những khái niệm logic mới này về các biến và vị từ, Frege đã giới thiệu các hàm trong toán học tương đương với logic bằng cách sử dụng một ký hiệu tương tự mà chúng ta vẫn sử dụng ngày nay giống như khi chúng ta viết “f(x)” để biểu thị giá trị của hàm khi áp dụng cho một biến x.
Những đổi mới quan trọng khác của ông là các ký hiệu cho cái gọi là bộ định lượng phổ quát và hiện sinh, kết nối các biến logic và vị từ để hình thành các phát biểu lồng nhau phức tạp hơn là chỉ các mệnh đề đơn giản của tam đoạn luận tiếng Hy Lạp. Các bộ định lượng sẽ cho phép các câu lệnh như “với mọi x có thuộc tính P” hoặc “nếu tồn tại bất kỳ x nào có thuộc tính P” (xem hình trên cho thấy các ký hiệu logic một chiều hiện đang được sử dụng so với các ký hiệu Begriffsschrift ban đầu của Frege). Trong ký hiệu logic mở rộng này với các khái niệm mới về vị từ, biến logic và định lượng, bất kỳ phát biểu toán học nào cũng có thể được phát biểu cho đến tận ngày nay như: “Với mọi x tồn tại một y, sao cho: nếu x /=0 thì x*y= 1”.
Bertrand Russel – Tập hợp tất cả các tập hợp không phải là thành viên của chính chúng
Frege khá tự hào về Begriffsschrift của mình cũng như sức mạnh và tính chặt chẽ của nó nên cuối cùng ông đã xuất bản nó vào năm 1879. Sau đó, ông làm việc để xây dựng và rút ra các mệnh đề cơ bản về số học của các số tự nhiên chỉ từ các khái niệm và nguyên tắc logic trong cuốn Begriffsschrift của mình. Ông đã công bố kết quả của mình trong cuốn sách thứ hai về nền tảng của số học vào năm 1893 và mọi thứ dường như diễn ra tốt đẹp đối với ông và dần dần ông được công nhận là người đi đầu trong lĩnh vực của mình.
Tuy nhiên, chỉ khoảng 10 năm sau, vào năm 1902, ngay trước khi ông có thể hoàn thành và xuất bản tập thứ hai của cuốn sách Cơ sở số học, ông nhận được một thông báo ngắn trên một tấm bưu thiếp đơn giản (đối với những độc giả nhỏ tuổi, bưu thiếp tương đương với tin nhắn hoặc trò chuyện). tin nhắn hôm nay) từ nhà toán học trẻ Bertrand Russell (xem hình bên dưới). Russell, một nhà toán học và logic học tài năng, sau này là triết gia nổi tiếng và nhà văn đoạt giải Nobel, đã cảnh báo Frege rằng ông đã xây dựng một tập hợp mâu thuẫn trong khuôn khổ nền tảng của số học của Frege!
Frege hoàn toàn bị sốc. Tuy nhiên, anh đã nhìn thấy và thừa nhận ngay rằng Russell đã đúng. Thông điệp bưu thiếp ngắn của Russell đã phá hủy mục tiêu cuộc đời và công việc gần 30 năm của Frege và sau khi nó được biết đến đã gây ra một cuộc khủng hoảng lớn cho toàn bộ ngành toán học trong nửa đầu thế kỷ 20!
Điều gì đã xảy ra mà một tấm bưu thiếp đơn giản và ngắn gọn lại có thể gây ra tác động mạnh mẽ đến vậy?
Điều trớ trêu là Russell ngưỡng mộ Frege vì công trình vĩ đại mà ông đã thực hiện để mở rộng logic cổ điển cũng như Begriffsschrift và sự làm rõ mà ông đã mang đến cho toán học và triết học ngôn ngữ. Tuy nhiên, trong khi nghiên cứu Begriffsschrift của Frege và nghiên cứu tác phẩm của riêng mình “Principia Mathematica”, Russell đã tìm ra một cách đơn giản để xây dựng mâu thuẫn logic trong khuôn khổ của Frege.
Russell đã xây dựng một tập hợp mà chúng ta sẽ gọi là “R”. Giả sử R được định nghĩa là: tập hợp tất cả các tập hợp không chứa chính chúng làm phần tử.
Mặc dù nghe có vẻ hơi kỳ quặc nhưng đó là một tập hợp hợp lý và dễ xác định trong Begriffsschrift của Frege. Có rất nhiều ví dụ về các tập hợp là thành viên của chính chúng và các tập hợp không phải là thành viên của chính chúng. Ví dụ: gọi X là tập hợp tất cả những thứ là ô tô. Khi đó rõ ràng X không phải là thành viên của chính nó vì X là một tập hợp chứ không phải một chiếc ô tô. Tuy nhiên, nếu chúng ta định nghĩa Y là tập hợp tất cả những thứ không phải là ô tô thì Y là thành viên của chính nó vì nó không phải là ô tô !
Bây giờ khi người ta đặt câu hỏi: “R có phải là một phần tử của chính nó hay không?” thì rắc rối sẽ xảy ra. Đầu tiên giả sử R thực sự là thành viên của chính nó. Khi đó, R không thể là thành viên của chính nó vì R chỉ chứa các tập hợp là thành viên, KHÔNG phải là thành viên của chính chúng! Tuy nhiên, bây giờ, nếu người ta giả định ngược lại rằng R không phải là thành viên của chính nó thì theo định nghĩa R phải thuộc về chính nó vì nó được định nghĩa là tập hợp của tất cả các tập hợp không phải là thành viên của chính nó! Vì vậy, bất cứ điều gì chúng ta giả định, chúng ta đều đưa ra điều ngược lại và do đó mâu thuẫn.
Những mâu thuẫn hay nghịch lý như vậy, như chúng thường được gọi, không có gì mới. Các nhà triết học Hy Lạp đã biết một số người trong số họ giống như nghịch lý người nói dối Cretan (khi một người Cretan nói “tất cả người Crete đều là kẻ nói dối”, anh ta có đúng không?). Bản thân Russell đã đưa ra một ví dụ bằng tiếng Anh đơn giản mà không cần dựa vào toán học gọi là nghịch lý thợ cắt tóc. Giả sử có một ngôi làng có rất nhiều đàn ông cần được cạo râu thường xuyên. Giả sử chỉ có một thợ cắt tóc trong làng có giấy phép cạo râu. Giờ đây, theo giấy phép, thợ cắt tóc phải cạo râu tất cả và chỉ những người đàn ông không tự cạo râu.
Điều gì xảy ra với người thợ cắt tóc khi anh ta cần tự cạo râu trong khi vẫn tuân thủ chính xác các điều khoản trong giấy phép của mình? Câu: “thợ cắt tóc tự cạo râu” đúng hay sai? Nếu đúng thì người thợ cắt tóc sẽ tự cạo râu, nhưng điều đó không thể đúng vì anh ta chỉ có thể cạo cho những người đàn ông không tự cạo râu. Nếu sai thì người thợ cắt tóc không tự cạo râu mà phải tự cạo râu vì nghĩa vụ của anh ta là cạo râu cho tất cả những người không tự cạo râu ! Những nghịch lý tương tự có thể dễ dàng được xây dựng bằng ngôn ngữ tự nhiên nhưng từng bị coi là những điều kỳ quặc và những trò trêu ghẹo não không liên quan chỉ phù hợp với các nhà triết học.
Tuy nhiên, đó không phải là trường hợp những mâu thuẫn, nghịch lý như vậy xảy ra trong logic hay toán học! Bất kỳ mâu thuẫn nào giống như mâu thuẫn mà Russell đã tìm thấy đều gây ra những hậu quả thảm khốc đối với bất kỳ hệ thống và lý thuyết logic và toán học cổ điển nào. Đó là bởi vì người ta có thể dễ dàng chứng minh rằng nếu thực sự một lý thuyết toán học chứa đựng dù chỉ một mâu thuẫn duy nhất hoặc cho phép chứng minh dù chỉ một tuyên bố sai, thì bất kỳ tuyên bố nào khác cũng có thể được chứng minh, bất kể nó đúng hay sai! Điều này làm cho toàn bộ hệ thống trở nên vô dụng ngay lập tức, vì nó không thể phân biệt được nữa giữa các phát biểu và định lý đúng và sai của lý thuyết.
Frege không thể hiểu được điều gì đã xảy ra ở đây mặc dù đã mất hàng thập kỷ suy nghĩ chăm chỉ và tiến bộ mà ông đã đạt được với Begriffsschrift của mình. Mục tiêu chính trong mọi công việc của anh ấy là đảm bảo rằng những điều như thế này không bao giờ có thể xảy ra trong khuôn khổ của anh ấy, nếu không thì mục đích của mọi nỗ lực và sự nghiêm ngặt sẽ là gì nếu nó thậm chí không thể ngăn chặn những mâu thuẫn đơn giản như vậy xảy ra!
Tuy nhiên, Russell không quá sốc và tê liệt như Frege và bắt tay ngay vào việc cố gắng giải quyết vấn đề. Anh ấy sớm nhận ra điều gì đã xảy ra trong hệ thống của Frege – vì vậy anh ấy tin như vậy. Ông đã nhận thấy một cách chính xác rằng trong hệ thống của Frege, bất kỳ vị từ P nào được xác định rõ ràng đều dẫn đến một tập hợp tất cả những thứ x thỏa mãn vị từ P(x) (Phần mở rộng của vị từ Frege). Giả sử P là vị từ “là số nguyên tố” và x bất kỳ số tự nhiên nào, thì P(x) đúng khi và chỉ nếu x là số nguyên tố.
Bây giờ, vai trò của x ở đây như một biến mà vị từ được áp dụng là rất quan trọng theo quan điểm của Russell và cần phải được xác định một cách chính xác và không có bất kỳ sự mơ hồ nào. Nếu x chỉ có thể lấy số làm giá trị thì mọi thứ đều ổn và được xác định rõ ràng. Tuy nhiên, nếu x cũng có thể nhận các giá trị khác của loại đối tượng khác ngoài số thì P(x) có thể không chỉ sai mà còn được coi là đơn giản là không xác định hoặc hoàn toàn vô nghĩa trong những trường hợp như vậy.
Giả sử x biểu thị ô tô cũng như số, thì P(x), với P xác định số nguyên tố, không có ý nghĩa khi x biểu thị ô tô (chẳng hạn như một chiếc BMW nào đó) vì ô tô không thể là số nguyên tố, do đó P(BMW) cũng không phải là số nguyên tố. đúng hay sai nhưng việc sử dụng biến và vị ngữ không phù hợp. Biến x phải được coi là một phần của miền logic khác khi nó biểu thị ô tô thay vì khi x biểu thị số 7.
Kết quả là Russell đã đưa ra lý thuyết nổi tiếng của mình về các loại biến và lý thuyết mô tả các vị từ tránh việc xây dựng các tập hợp là thành viên của chính chúng bằng cách xác định mức độ logic ngày càng tăng của các biến và vị từ sao cho các vị từ chỉ có thể được áp dụng cho các biến. của một số cấp độ thấp hơn chứ không phải cho chính họ. Russell đã viết một số bài báo triết học có ảnh hưởng về những chủ đề này để biện minh cho cách tiếp cận của mình. Ông cũng làm việc chặt chẽ với Ludwig Wittgenstein trẻ tuổi về những chủ đề này, người lúc đầu ủng hộ cách tiếp cận của ông, tuy nhiên đã trở thành người chỉ trích mạnh mẽ quan điểm của Russell và những quan điểm tương tự về toán học và logic trong những năm cuối đời của ông.
Russell đã phát triển lý thuyết này trong khoảng 10 năm và xuất bản nó trong cuốn sách kiệt tác 3 tập hoành tráng và được đánh giá cao Principia Mathematica từ năm 1910 đến 1913, trong đó ông đã định nghĩa và rút ra thành công các định luật cơ bản của số học (tương tự như Frege) nhưng nằm trong lý thuyết logic của mình. của các loại. Không tìm thấy bất kỳ mâu thuẫn nào trong lý thuyết về các loại và Nguyên lý toán học của ông cho đến ngày nay.
David Hilbert – Cứu chương trình Infinite và Hilbert
Cuốn sách Principa Mathematica của Russell được các nhà toán học và logic học cùng thời với ông đánh giá cao và là một sự giải thoát cho những nỗ lực xây dựng nền tảng, nhưng nó vẫn không thực sự giải quyết được vấn đề then chốt là tránh mâu thuẫn. Ngay cả khi không có mâu thuẫn nào được tìm thấy trong Principia Mathematica tương tự như cái mà ông đã xây dựng, thì điều đó cũng không đảm bảo rằng không có những loại mâu thuẫn khác nhau ẩn giấu ở đâu đó có thể bất ngờ xuất hiện bởi một bộ óc thông minh nào đó – giống như nghịch lý của chính Russell đã làm. Không có bằng chứng nào cho thấy bản thân lý thuyết của Russell không có mâu thuẫn - và chừng nào không có bằng chứng như vậy thì bất cứ điều gì vẫn có thể xảy ra bất cứ lúc nào trong tương lai.
Để tránh tình trạng như vậy một lần và mãi mãi trong khi vẫn giữ nguyên vũ trụ siêu hữu hạn của Cantor, một nhà toán học người Đức có ảnh hưởng khác, David Hilbert, đã bước lên đĩa và tham gia. Hilbert đã nổi tiếng thế giới vào thời điểm đó khi ông lần đầu tiên tiên đề hóa hình học cổ điển và xây dựng nền tảng của hình học phi Euclide (hình học của các bề mặt không phẳng - chẳng hạn như nó cần thiết và được giả định trong thuyết tương đối rộng của Einstein). Hilbert là một người có uy tín cao và có lẽ là nhà toán học có ảnh hưởng nhất trong 30 năm đầu thế kỷ 20.
Hilbert nghĩ rằng tình trạng thiếu một nền tảng toán học nhất quán đã được chứng minh là một sự bối rối đối với tất cả các nhà toán học. Ông muốn đảm bảo rằng các nhà toán học có thể định nghĩa và có thể dựa vào một tập hữu hạn các tiên đề cơ bản đã được thống nhất (như đối với lý thuyết tập hợp), điều này sẽ cho phép chứng minh bất kỳ phát biểu toán học thực sự nào tuân theo một cách logic từ các tiên đề cơ bản và sẽ cho phép một kết quả rõ ràng và hoàn hảo. chứng minh tính nhất quán cho toán học nói chung.
Do đó, ông đã xây dựng cái gọi là chương trình Hilbert vào khoảng năm 1920, yêu cầu các nhà toán học đồng nghiệp của ông tập trung vào những vấn đề sau:
1) cung cấp một tiên đề hữu hạn và đầy đủ cho toán học (tương tự như Hilbert đã làm cho hình học trước đây) hoặc ít nhất cho số học vốn là cơ sở cho nhiều lý thuyết toán học có thể tạo ra tất cả các phát biểu toán học số học thực sự;
2) cung cấp chứng minh rằng các tiên đề này chỉ phù hợp với các phương pháp chứng minh hữu hạn (để tránh vòng luẩn quẩn với các tập hợp vô hạn); nhất quán ở đây có nghĩa là không có mệnh đề toán học nào “P” được biết là sai (như 0=1) có thể được chứng minh
3) cung cấp một thủ tục (thuật toán) hữu hạn hiệu quả có thể quyết định xem bất kỳ câu lệnh toán học P nào cho trước là đúng hay sai (phần này của chương trình được gọi là “Bài toán Entscheidungs” hoặc “bài toán quyết định” đã được Alan Turing giải quyết khoảng 15 năm sau - xem bên dưới). Hilbert bổ sung yêu cầu này vào năm 1928.
Bản thân Hilbert đã cống hiến hầu hết các nghiên cứu toán học của mình sau những năm 1920 cho những nhu cầu này. Ông đã tạo ra cái gọi là siêu toán học trên đường đi. Đây là một cách khéo léo để tiếp cận các vấn đề trên: ông coi và nghiên cứu các tiên đề, mệnh đề và chứng minh toán học như chính các đối tượng toán học.
Chẳng hạn, ông xem xét một chứng minh toán học như thể nó chỉ là một chuỗi hữu hạn các ký hiệu bắt đầu bằng một số ký hiệu ban đầu (các tiên đề) và sau đó biến đổi chúng chỉ bằng các quy tắc được xác định rõ ràng có thể chấp nhận được thành các ký hiệu khác trong một số bước hữu hạn - do đó không cho phép và loại bỏ bất kỳ loại “trực giác” nào hoặc thậm chí bất kỳ cách giải thích ngữ nghĩa nào về ý nghĩa của các ký hiệu được sử dụng.
Các ký hiệu và định lý của toán học sẽ giống như những quân cờ trên bàn cờ và các quy tắc logic giống như quy tắc chơi cờ. Việc chứng minh tính nhất quán của một lý thuyết toán học với một tập hợp tiên đề cho trước sẽ tương tự như việc chứng minh rằng với một vị trí ban đầu nhất định của các quân cờ trên bàn cờ, thì không thể đạt được vị trí cuối cùng nhất định (kiểm tra bạn) cho dù có nước đi nào. đã được sử dụng và áp dụng cho các mảnh trên bảng. Mặc dù Hilbert phủ nhận việc coi cách tiếp cận của ông giống với ví dụ cờ vua ở trên, nhưng đó vẫn là cách tốt nhất để mô tả bằng thuật ngữ phi toán học cách tiếp cận mới của ông về siêu toán học.
Nhiều logic, nhiều toán học?
Thực ra, Hilbert bị buộc phải thiết lập chương trình của mình. Ông muốn giữ và bảo vệ lý thuyết tập hợp cũng như tất cả những cái vô hạn đẹp đẽ do Cantor tạo ra. Tuy nhiên, nghịch lý của Russell và những nghịch lý tương tự bắt nguồn từ lý thuyết tập hợp và các phương pháp xuyên hữu hạn được Cantor sử dụng đã dẫn đến sự phản đối của một số nhà toán học chủ chốt vào thời đó (thậm chí một trong những học trò tài năng nhất của ông đã rời trại). Những người phản đối đã cố gắng tạo ra một logic và toán học phi cổ điển sẽ tạo ra các kết quả và định lý mâu thuẫn với toán học và logic thời đó. Chỉ một thập kỷ trước Thế chiến thứ hai, các nhà toán học đã bước vào thời kỳ “chiến tranh lạnh” với nhau về tương lai của toán học.
Nhà phê bình nổi bật và bằng lời nói nhất của Hilbert là nhà tôpô đại số trẻ tuổi người Hà Lan LEJ Brouwer. Ông thành lập cái gọi là toán học Trực giác và triết học toán học. Brouwer tin rằng bất kỳ đối tượng toán học nào (và bằng chứng) đều phải mang tính xây dựng và hữu hạn. Ông tin rằng các số tự nhiên trong đó các khái niệm cơ bản không thể giải thích hay rút gọn thêm và được đưa ra thông qua trực giác, khá giống với các tập hợp vô hạn đối với Cantor. Sự khác biệt duy nhất giữa trực giác của Brouwer và của Cantor là Brouwer đề cập đến trực giác của một “nhà toán học lý tưởng” hơn là Chúa như Cantor đã nói.
Nhưng Brouwer, với tư cách là Cantor, không tin vào các tập hợp vô hạn thực tế – chỉ tin vào các tập hợp có thể được xây dựng bằng các thủ tục toán học hữu hạn được chấp nhận ngay từ đầu. Brouwer (ảnh trên tem bưu điện Hà Lan ở trên) không hề ngại ngùng về quan điểm của mình dù còn trẻ. Ông đã chứng minh một số định lý nổi tiếng trong cấu trúc liên kết đại số nhưng theo thời gian với sự phát triển của chủ nghĩa trực giác, ông thậm chí còn tránh xa các kết quả và chứng minh của chính mình vì chúng không mang tính xây dựng theo nghĩa trực giác.
Brouwer tố cáo một số quy tắc và nguyên tắc logic quan trọng đã được chấp nhận từ hàng ngàn năm nay. Ông lập luận rằng những nghịch lý của Russell và lý thuyết tập hợp xuất hiện bởi vì chúng sử dụng một số quy tắc logic và giáo điều vốn chỉ nhằm mục đích sử dụng cho các đối tượng hữu hạn. Ông cho rằng chúng không còn giá trị khi áp dụng cho các tập hợp vô hạn. Cuộc tấn công nổi tiếng của ông dựa trên nguyên tắc và quy tắc logic của cái gọi là “loại trừ thứ 3”. Quy luật này có nghĩa là đối với bất kỳ mệnh đề toán học nào được xây dựng đúng P, P đều phải đúng hoặc sai, không có lựa chọn thứ 3!
Brouwer cho biết điều này không đúng khi áp dụng cho một số phát biểu toán học nhất định mà không có bằng chứng mang tính xây dựng hoặc bác bỏ nào được biết đến. Do đó, đối với những phát biểu A như vậy, phép đồng nghĩa cổ điển “A hay không phải A” là không đúng. Nếu một tuyên bố không thể được chứng minh hoặc bác bỏ thì chúng ta không có cơ sở để khẳng định rằng tuyên bố này đúng hay không đúng – đó là điều tốt nhất chúng ta có thể nói, nhưng không đúng hay sai !
Do đó, chân lý toán học đối với Brouwer gần với khái niệm chứng minh hơn nhiều so với toán học cổ điển, nơi có sự phân biệt rõ ràng giữa “chân lý” và “chứng minh”. Trên thực tế, toàn bộ mục đích của siêu toán học Hilbert là phân tích mối quan hệ giữa chân lý và khái niệm chứng minh cho một hệ tiên đề nhất định.
Brouwer cũng cho rằng các phát biểu toán học có thể thay đổi “tình trạng đúng” của chúng theo thời gian. Đó là điều không thể tưởng tượng được trong toán học cổ điển. Một khi một phát biểu đúng thì sau này nó không thể trở thành sai (miễn là nó không liên quan đến thời gian trong các thuật ngữ của nó). Nhưng đối với Brouwer, nếu và khi một tuyên bố chưa quyết định cho đến nay được chứng minh hoặc sự phủ định của nó được chứng minh, thì tuyên bố cuối cùng được quyết định và trở thành đúng hoặc sai. Tuy nhiên, miễn là không tìm thấy bằng chứng thì không thể quyết định được tình trạng sự thật của tuyên bố đó.
Toán học và logic trực giác của Brouwer có tác động mạnh mẽ đến toán học và logic vì nó mang tính xây dựng và có vẻ nhất quán. Chủ nghĩa trực giác đạt đến đỉnh cao vào những năm 1920 và 1930 nhưng cuối cùng không thực sự tìm được nhiều người theo đuổi vì việc áp dụng đã làm giảm đáng kể các phương pháp toán học và logic mà người ta có thể sử dụng. Đó không phải là mối quan tâm của hầu hết các nhà toán học. Ngày nay, các phương pháp theo chủ nghĩa trực giác và kiến tạo đang chứng kiến sự hồi sinh nào đó do vai trò to lớn và ngày càng tăng của công nghệ máy tính vốn dĩ phải hữu hạn và mang tính xây dựng (nhưng vẫn thường sử dụng nguyên tắc logic thứ 3 bị loại trừ).
Định lý Bất toàn của Goedel – Giới hạn của Toán học và Logic
Bây giờ, cuối cùng chúng ta cũng đến với Goedel và Định lý Bất toàn của ông. Geodel không phải là người bạn của chủ nghĩa trực giác. Ông là một người tin tưởng mạnh mẽ vào chủ nghĩa Platon giống như Frege. Đối với ông, làm toán không phải là tạo ra thứ gì đó trong đầu (như Brouwer nghĩ) mà giống như khám phá ra thứ gì đó - những chân lý vĩnh cửu. Đối với ông, các đối tượng toán học tồn tại độc lập với con người. Chúng ta có thể nắm bắt các chân lý toán học bằng trí óc của mình và khám phá các bằng chứng nhưng chúng ta không tạo ra những chân lý này hay bất kỳ đối tượng toán học nào. Do đó, anh ấy cũng không gặp vấn đề gì khi giải quyết các tập hợp vô hạn đã hoàn thành. Ông muốn hỗ trợ chương trình của Hilbert bằng cách cố gắng chứng minh một số mục tiêu mà Hilbert đã đưa ra trước đó và yêu cầu về toán học.
Tuy nhiên, điều này vô tình lại phản tác dụng. Định lý Bất toàn của Goedel thực tế đã chứng minh rằng mục tiêu của Hilbert là không thể đạt được! Nó đã thay đổi sự hiểu biết của chúng ta về các hệ thống logic và toán học tiên đề mãi mãi.
Không đi sâu vào các chi tiết kỹ thuật và các công thức logic chính xác, đây thực chất là những gì Định lý Bất toàn của Goedel nói (thực ra là 2 định lý):
1) Định lý bất toàn 1: Bất kỳ hệ thống tiên đề hình thức nào đủ biểu cảm để hình thức hóa các tiên đề và tính chất cơ bản của số tự nhiên (số học) sẽ không đầy đủ theo nghĩa là sẽ luôn có những câu đúng trong hệ thống này mà không thể được chứng minh trong hệ thống (nghĩa là chỉ với những tiên đề và quy tắc được cho phép trong hệ thống)
2) Định lý bất toàn 2: Tính nhất quán của bất kỳ hệ thống nào như vậy không thể được chứng minh ngay trong chính hệ thống đó!
Định lý quan trọng hơn rõ ràng là định lý 2 vì nó nói về tính không thể chứng minh tính nhất quán, một kết quả mà không ai trước Goedel từng tưởng tượng là đúng.
Tuy nhiên, trước tiên chúng ta hãy thảo luận nhanh định lý 1 và các hệ quả của nó trước khi cố gắng hiểu định lý 2. Định lý 2 là hệ quả của định lý 1.
Định lý 1 nói rằng, cho dù chúng ta xác định các tiên đề và phương pháp của mình trong lý thuyết toán học/logic tốt đến đâu, nếu hệ thống cho phép định nghĩa và mô tả các số tự nhiên và các tính chất của chúng (số học) thì sẽ luôn có những phát biểu không thể chứng minh được nhưng vẫn đúng có thể được hình thành trong hệ thống. Do đó, định lý nói về cơ bản rằng trong một hệ thống số học hình thức mang tính mô tả rõ ràng và nhất quán, các tập hợp con của tất cả các phát biểu có thể có thể được hình thức hóa trong hệ thống xác định các phát biểu có thể chứng minh được và các phát biểu đúng là không giống nhau.
Một hệ thống hoặc lý thuyết hình thức được cho là hoàn chỉnh nếu a) chỉ có thể rút ra được các câu đúng và b) tất cả các câu đúng trong hệ thống thực sự cũng có thể được chứng minh. a) đảm bảo tính nhất quán của các tiên đề và các phương pháp cho phép rút ra các mệnh đề mới từ các tiên đề, đây là điều bắt buộc, nếu không thì toàn bộ hệ thống sẽ vô dụng. b) là yêu cầu về tính đầy đủ thực tế. Nếu b) không được đáp ứng thì hệ thống tiên đề cơ bản không mang lại tất cả sự thật đúng và do đó sẽ không cho phép chúng ta có một bức tranh “hoàn chỉnh” về tất cả những điều mà lý thuyết mô tả và tất cả các phát biểu đúng theo sau các tiên đề.
Vì vậy, định lý 1 của Goedel đã giáng một đòn mạnh vào chương trình của Hilbert. Về cơ bản, nó nói rằng chúng ta sẽ không bao giờ tìm thấy một bộ tiên đề và quy tắc hữu hạn hoàn chỉnh cho toán học (thực ra, ngay cả đối với những phần nhỏ của toán học như số học cơ bản)! Cho dù chúng ta thiết lập một hệ tiên đề cho toán học có chính xác đến đâu đi nữa thì sẽ luôn có một số mệnh đề toán học đúng mà hệ tiên đề này không thể đưa ra và chúng ta không thể chứng minh được. Theo một nghĩa nào đó, định lý 1 nói: không có nền tảng toán học vững chắc và đầy đủ nào cả.
Nhìn nhận lại, hệ quả của định lý đầu tiên của Goedel không quá tệ và thậm chí còn mở ra một số lĩnh vực toán học mới như: giải tích và số học phi tiêu chuẩn, lý thuyết chứng minh, lý thuyết mô hình và lý thuyết tập hợp cấp độ cao hơn. Hóa ra là có thể tìm thấy và xây dựng nhiều phát biểu toán học độc lập với các bộ tiên đề cổ điển (như các tiên đề Peano cho số tự nhiên hoặc các tiên đề Zermelo-Frenkel của lý thuyết tập hợp).
Một phát biểu P độc lập với một tập tiên đề nếu cả P lẫn phủ định phi P của nó đều không thể rút ra được từ các tiên đề đó. Những phát biểu quan trọng của lý thuyết tập hợp như tiên đề lựa chọn hay các giả thuyết liên tục đều độc lập với các tiên đề lý thuyết tập hợp cổ điển (sau này cũng được Goedel chứng minh).
Điều này làm nảy sinh sự cạnh tranh giữa các lý thuyết toán học tiên đề với các tập hợp định lý có thể chứng minh khác nhau – hay người ta có thể nói đơn giản: toán học khác nhau. Điều này là do nếu tìm thấy một mệnh đề P (tiên đề) độc lập, thì P (hoặc không phải P đối với vấn đề đó) có thể được thêm vào các tiên đề cơ bản mà không gây ra bất kỳ mâu thuẫn nào, do đó cho phép các hệ tiên đề khác nhau cho toán học.
Đó đã là một cú sốc lớn đối với Hilbert và toàn bộ thế giới toán học. Nhưng định lý 2 của Goedel còn khiến nó trở nên tồi tệ hơn nhiều. Định lý 2 là trường hợp đặc biệt của định lý 1 và nói rằng việc chứng minh tính nhất quán tuyệt đối cho toán học là không thể. Chưa bao giờ trong lịch sử khoa học có một tuyên bố sâu sắc hơn thế được đưa ra – và thậm chí đã được chứng minh!
Định lý 2 là một bất ngờ lớn vì có vẻ như toán học đã đứng vững trở lại sau khi Russell xuất bản Nguyên tắc của mình và không có sự mâu thuẫn nào được tìm thấy trong hệ thống của ông cho đến tận ngày nay. Russell và cả thế giới cho rằng với việc xây dựng các loại biến và vị từ logic, sự mâu thuẫn sẽ không thể xảy ra và đã là chuyện quá khứ. Nhưng Russell – giống như Frege trước anh – đã giám sát một chi tiết thiết yếu: các số tự nhiên.
Các số tự nhiên 1, 2, 3, 4, 5, 6…, v.v., dường như rất “ngây thơ”, “tự nhiên” và quen thuộc với chúng ta đến mức chúng ta gọi chúng là số tự nhiên. Họ dường như không xứng đáng nhận được bất kỳ lời biện minh nào. Tuy nhiên, hóa ra họ không hề “ngây thơ” như lúc đầu. Cái nhìn sâu sắc thiên tài nhất của Goedel và phần quan trọng trong chứng minh của ông là khám phá và nhận ra rằng người ta thực sự có thể sử dụng các số tự nhiên để mã hóa/mã hóa bất kỳ lý thuyết tiên đề hữu hạn nào và bất kỳ số hữu hạn nào của chuỗi phát biểu về số - do đó thậm chí có thể mã hóa tất cả những gì có thể chứng minh toán học!
Do đó, trong chứng minh định lý 2, Goedel đã xây dựng một hàm G mã hóa mọi phát biểu và các chứng minh có thể có của phát biểu dưới dạng một số tự nhiên cụ thể (thường rất lớn) (được gọi là số Goedel). Một bằng chứng trong hệ thống được định nghĩa là một chuỗi hữu hạn nhất định các câu lệnh của hệ thống bắt đầu bằng một số tiên đề và kết thúc bằng chính câu lệnh đó và bất kỳ hai câu lệnh nào theo sau nhau trong chuỗi chỉ phải được tạo ra bởi các quy tắc cho phép của hệ thống. .
Những số tự nhiên này và số Goedel của chúng hiện có 2 cách giải thích: thứ nhất, chúng có thể được coi là những số tự nhiên lớn bình thường và là đối tượng của lý thuyết và tiên đề toán học cơ bản thông thường (của số học). Mặt khác, ở cấp độ meta, giờ đây mọi số như vậy cũng có thể được đọc và hiểu là biểu diễn và mã hóa một tuyên bố về số tự nhiên hoặc thậm chí là một bằng chứng được mã hóa!
Bằng cách sử dụng một biến thể rất thông minh của nghịch lý Russell và 2 cách giải thích song song có thể có của các số tự nhiên, Goedel sau đó đã có thể xây dựng các câu lệnh tự giới thiệu trong hệ thống và mã hóa chúng lại thành số tự nhiên.
Ông đã định nghĩa một mối quan hệ cụ thể giữa các số tự nhiên n và m, Bằng chứng(n,m), điều này đúng khi và chỉ khi n mã hóa một bằng chứng của phát biểu được mã hóa bởi m. Sau đó, anh ấy sử dụng Proof(n,m) để xây dựng một tuyên bố tự giới thiệu “S” có nội dung ở cấp độ meta: “Tôi không thể chứng minh được”. Goedel sau đó đã chứng minh rằng cả S và phi S đều không thể chứng minh được trong hệ thống. Lập luận diễn ra như sau: Đầu tiên chúng ta giả định rằng hệ tiên đề cơ bản mà chúng ta muốn chứng minh tính nhất quán thực sự là nhất quán. Vì nếu nó không nhất quán thì chúng ta có thể chứng minh bất cứ điều gì. Vì vậy, chúng tôi giả định tính nhất quán và bây giờ muốn chứng minh rằng đây thực sự là trường hợp.
Vì vậy, trước tiên hãy giả sử rằng S có thể chứng minh được trong hệ thống, sau đó S cũng cần phải đúng (vì hệ thống được coi là nhất quán nên không có tuyên bố sai nào có thể được chứng minh), nhưng khi đó S sẽ đúng là S không thể chứng minh được vì đây là điều S nói về chính nó. Do đó, giả định rằng S có thể chứng minh được sẽ dẫn đến một tuyên bố sai, có nghĩa là giả định rằng S có thể chứng minh được là không thể đúng.
Bây giờ, hãy xem liệu phi S, sự phủ định của S, có thể chứng minh được hay không. Giả sử non S thực sự có thể chứng minh được. Vì hệ thống cơ bản là nhất quán nên S cũng không thể chứng minh được. Tuy nhiên, vì S nói “Tôi không thể chứng minh được” nên điều đó đúng. Nhưng bây giờ chúng ta sẽ có cả S đúng và không S, điều này một lần nữa không thể xảy ra như chúng ta đã giả định rằng hệ thống cơ bản là nhất quán và do đó không phải cả hai tuyên bố đều có thể đúng.
Tóm lại, S (và không phải S) không thể chứng minh được trong hệ thống khi chúng ta giả định tính nhất quán của nó. Tuy nhiên, S thể hiện tính nhất quán của hệ thống cơ bản vì nó nói rằng bản thân S không thể chứng minh được. Nếu chúng ta chỉ có một câu duy nhất trong hệ thống cơ bản thực sự không thể chứng minh được thì hệ thống PHẢI nhất quán vì điều đó có nghĩa là không phải mọi tuyên bố đều có thể chứng minh được. Do đó, tính không thể chứng minh được của S tương đương với tính không thể chứng minh được của tính nhất quán của hệ thống cơ bản.
Để có một phác thảo phác thảo chính xác và hình thức hơn về chứng minh của Goedel mà không cần nhiều kiến thức toán học, vui lòng xem:
https://en.wikipedia.org/wiki/Proof_sketch_for_Gödel%27s_first_incompleteness_theorem
Với những định lý đáng kinh ngạc này, chương trình của Hilbert thực tế đã chết, một điều mà Goedel không hề có ý định làm.
Tuy nhiên, các định lý về Tính không đầy đủ của Goedel không nói rằng việc chứng minh tính nhất quán là không thể, nhưng chúng cho thấy để chứng minh như vậy, người ta luôn cần sử dụng các tiên đề chưa được chứng minh bổ sung hoặc các phương pháp không được chấp nhận từ bên ngoài hệ thống - và điều đó sẽ làm hỏng toàn bộ mục đích của tính nhất quán bằng chứng và sẽ là một loại gian lận.
Gần như cùng lúc khi Goedel đang nghiên cứu các định lý của mình, nhà toán học người Ba Lan Alfred Tarski cũng nghiên cứu một vấn đề tương tự và có kết quả tương tự. Ông đã chỉ ra rằng trong bất kỳ hệ thống hình thức có tính biểu đạt rõ ràng nào cho phép định nghĩa các số tự nhiên một cách nhất quán, thì khái niệm “chân lý” không thể được định nghĩa nếu không tạo ra mâu thuẫn trong hệ thống. Đó là một đòn giáng mạnh nữa vào chương trình và mục tiêu của Hilbert. Làm sao toán học có thể tồn tại được nếu không thể định nghĩa khái niệm “chân lý” trong khuôn khổ tiên đề của nó?
Alan Turing – Thuật toán là gì, Trí thông minh là gì?
Vấn đề cuối cùng do Hilbert đặt ra vào năm 1928 và vẫn chưa được giải quyết sau kết quả của Goedel và niềm hy vọng cuối cùng của Hilbert là cái gọi là vấn đề Entscheidungsproblem: liệu có một thuật toán nào có thể quyết định bất kỳ phát biểu toán học nào cho dù nó đúng hay không trong một số bước hữu hạn? Xét cho cùng, các định lý Bất toàn – dù có sức tàn phá khủng khiếp – không loại trừ khả năng tồn tại của một thủ tục quyết định như vậy.
Tuy nhiên, như bạn có thể đoán bây giờ, câu trả lời cho bài toán Entscheidungs cũng là phủ định. Không thể có thuật toán nào như vậy và người đã chứng minh được điều này chính là nhà toán học trẻ tuổi và xuất sắc người Anh Alan Turing (bên trái), người ngày nay được nhiều người coi là một trong những cha đẻ của AI.
Turing bị cuốn hút bởi công việc của Goedel và biết về chương trình của Hilbert cũng như nỗ lực tìm ra thuật toán quyết định của ông. Tuy nhiên, khi biết các định lý của Goedel, Turing đã thẳng thắn chứng minh rằng không thể có một thuật toán hữu hạn kiểm tra chính xác các phát biểu toán học về tính đúng đắn của chúng.
Để chứng minh bài toán Entscheidungs và để xác định thuật toán thực sự là gì, trước tiên, ông đã phát triển mô hình máy tính đa năng nổi tiếng và rất đơn giản về mặt khái niệm - cái gọi là Máy Turing (phổ quát), được đặt theo tên ông. Thay vì sử dụng các kỹ thuật chứng minh toán học phức tạp như Goedel hay Alonso Church, những người đồng thời và độc lập cũng giải được bài toán Entscheidungs, Turing đã sử dụng mô hình máy Turing đơn giản và trực quan hơn nhiều của mình để giải bài toán.
Turing lần đầu tiên giải được một bài toán khác được gọi là Bài toán dừng của máy Turing. Vấn đề dừng là vấn đề cần quyết định, với bất kỳ chương trình nào được mô phỏng trên máy Turing và đầu vào của nó, liệu chương trình có dừng sau các bước hữu hạn ở cuối hay không (không tính đến các hạn chế về thời gian và bộ nhớ).
Sử dụng logic tương tự như Goedel đã làm trong Định lý Bất toàn của mình, Turing đã chứng minh rằng nếu có bất kỳ thuật toán nào như vậy tồn tại và được chạy trên máy Turing, thì máy có thể chạy mãi mãi và dừng cùng lúc, điều này là mâu thuẫn và do đó giả định không thể đúng. Sử dụng kết quả phủ định này cho bài toán Dừng, Turing sau đó suy luận rằng cũng không thể có một thuật toán cho bài toán Entscheidungs cụ thể hơn cho các định lý toán học.
Khác với những kết quả mang tính lý thuyết của Goedel, máy Turing và các kết quả của Turing có những hệ quả rất thiết thực hàng ngày đối với các nhà khoa học và lập trình viên máy tính. Ví dụ, đó là một hệ quả dễ dàng của tính không thể giải quyết được của vấn đề Dừng và Entscheidungs mà cũng không thể có một chương trình trong bất kỳ ngôn ngữ lập trình cấp cao phổ biến nào được sử dụng ngày nay có thể kiểm tra xem liệu bất kỳ chương trình nào sẽ bị mắc kẹt trong một vòng lặp vô tận (nghĩa là nó gặp sự cố) hay không khi chạy với một số đầu vào nhất định. Điều đó có nghĩa là không có trình kiểm tra hoặc trình gỡ lỗi chương trình chung. Vì vậy, đừng lãng phí thời gian của bạn để cố gắng phát triển một chương trình như vậy. Nhưng điều đó không có nghĩa là Microsoft và các hãng phần mềm lớn khác không nên tiếp tục cải tiến sản phẩm của mình.
Máy tính có thể thông minh đến mức nào? Để bảo vệ bài kiểm tra Turing
Turing hiểu rõ những hạn chế mạnh mẽ mà các định lý của Goedel áp đặt lên những gì chúng ta có thể làm và đạt được với máy tính và thuật toán. Chính ông đã chứng minh rằng máy tính không thể giải được bài toán Dừng (và ngày nay chúng ta biết còn nhiều bài toán khác không thể tính toán được). Vì vậy, anh ấy đã tự hỏi mình câu hỏi, cuối cùng máy tính có thể trở nên thông minh đến mức nào? Máy tính thông minh thực sự có thể thực hiện được không? Ông thậm chí còn quan tâm đến triết học toán học và logic về những chủ đề này, đồng thời đến thăm và thảo luận sâu sắc quan điểm của mình với nhà triết học Ludwig Wittgenstein, người có quan điểm rất khác với Turing về tất cả những vấn đề này.
Trái ngược với các nhà toán học đồng nghiệp của mình, Turing rất quen thuộc và thậm chí còn tham gia một cách chuyên nghiệp vào việc phát triển những chiếc máy tính lập trình lớn đầu tiên. Ai cũng biết rằng Turing là một phần trong nỗ lực giải mã Enigma của Đức Quốc xã trong Thế chiến thứ hai tại Bletchley Park bằng cách sử dụng và phát triển một trong những máy tính quy mô lớn đầu tiên. Vì vậy, ông có hiểu biết sâu sắc và tốt hơn nhiều về công nghệ máy tính thời kỳ đầu so với Russell, Goedel, Hilbert và hầu hết các nhà toán học và logic học cùng thời với ông.
Do đó, không có gì đáng ngạc nhiên khi Turing say mê với những chiếc máy tính thời kỳ đầu và những gì chúng có thể làm, đồng thời khá lạc quan về mức độ thông minh mà máy móc có thể đạt được bất chấp những hạn chế về mặt lý thuyết đã biết xuất phát từ kết quả của Goedel. Ông thậm chí còn phát triển một trong những chương trình chơi cờ đầu tiên để xem máy tính có thể thực hiện những nhiệm vụ như vậy tốt đến mức nào và liệu chúng có thể đạt được các kỹ năng ở cấp độ con người hay không. Turing tự hỏi bản thân rằng những chiếc máy tính trong tương lai thậm chí có thể trở nên thông minh hơn nhiều đến mức nào.
Kết quả là ông đã xuất bản một bài báo nổi tiếng có tựa đề “Máy tính và trí thông minh” vào năm 1950. Trong bài báo này, ông đã giới thiệu Bài kiểm tra Turing khét tiếng.
Turing lập luận rằng câu hỏi liệu máy tính có thể “suy nghĩ” hay trở nên “thông minh” hay không không thể trả lời được vì các thuật ngữ “tư duy” và “trí thông minh” chưa được xác định rõ ràng và sẽ vẫn khó xác định trong tương lai. Tuy nhiên, bằng cách nào đó, để nắm được cách đánh giá trí thông minh của máy móc và để có ít nhất một số tiêu chí thực tế dễ chịu, Turing đã đề xuất bài kiểm tra Turing của mình, một loại bài kiểm tra “trí thông minh của máy tính”.
Ông đề xuất rằng một cỗ máy hoặc chương trình nên được coi là “thông minh” nếu ít nhất nó có thể bắt chước và mô phỏng tốt khả năng hiểu ngôn ngữ tự nhiên và kỹ năng giao tiếp của con người ở mức độ khiến thực tế không thể phân biệt được giữa con người và máy móc chỉ bằng cách đánh giá ngôn ngữ tương ứng của chúng. kỹ năng.
Turing chọn một bài kiểm tra ngôn ngữ bởi vì, mặc dù nó khá hạn chế về mặt đo lường trí thông minh, nhưng nó vẫn cần rất nhiều kỹ năng để một cỗ máy hoặc chương trình có thể thành thạo, chẳng hạn như bài kiểm tra mà chương trình/máy sẽ phải: “hiểu” ngôn ngữ ở mức độ rất cao và có thể so sánh được với con người, cần có khả năng tạo ra ngôn ngữ có chất lượng như con người, cần có nhiều kiến thức và đặc biệt là kiến thức thông thường về thế giới để có bất kỳ loại ngôn ngữ nào. trò chuyện với một con người. Nó thậm chí sẽ phải có một “lý thuyết về tâm trí” của con người vì bằng cách nào đó nó phải có khả năng đánh lừa con người thực hiện bài kiểm tra tin rằng chính nó cũng là một con người. Máy móc cần phải “hiểu” và có thể dự đoán những gì con người mong đợi ở nó, nó cần phải “hiểu” cách “nói dối” về chính nó, giả vờ còn sống và tỉnh táo mà không bị bắt. Nó cần phải có sự hiểu biết theo ngữ cảnh, trí nhớ, sự hài hước, kỹ năng xã hội, “hiểu” chính trị, khoa học cơ bản, văn hóa, v.v.
Mặc dù đề xuất bài kiểm tra Turing như một tiêu chí cho “trí thông minh tổng quát” đã bị chỉ trích từ nhiều phía vì những lý do tốt và xấu, nhưng một bài kiểm tra Turing nghiêm túc vẫn chưa được bất kỳ máy tính hay chương trình nào vượt qua thành công cho đến tận ngày nay. Điều này cho thấy bài kiểm tra thực sự rất khó vượt qua và bằng cách nào đó phù hợp và hỗ trợ trực giác của chúng ta rằng máy móc ngày nay vẫn còn kém xa mức độ thông minh nói chung của con người. Hệ thống AI có thể chơi cờ vua và cờ vây, đồng thời cũng sớm lái ô tô tốt hơn con người chúng ta, nhưng việc vượt qua bài kiểm tra Turing nghiêm túc vẫn là một cột mốc quan trọng mà AI đang chờ đạt được. Nó cho thấy Turing đã có tầm nhìn xa như thế nào khi đề xuất mô hình thử nghiệm này.
Hội nghị AI năm 1956 – Sự ra đời của AI?
Sau Thế chiến thứ hai, trung tâm nghiên cứu trong nhiều lĩnh vực khoa học, toán học và logic đặc biệt đã chuyển từ Trung Âu sang Hoa Kỳ do thiếu kinh phí sau chiến tranh nhưng phần lớn là do nhiều nhà nghiên cứu nhập cư đã rời Châu Âu chạy trốn khỏi Đức Quốc xã và chuyển đi. sang Mỹ (trong đó có Einstein, Goedel, von Neumann, Fermi và nhiều người khác). Một ngày nào đó ai đó nên giải thích điều này với Donald Trump.
Hầu hết mọi người trong cộng đồng AI, đặc biệt là thế hệ trẻ, dường như không nhận thức được trình độ cao của văn hóa khoa học trước Thế chiến thứ hai và do đó, sự ra đời của AI thường bắt nguồn từ hội nghị Dartmouth nổi tiếng năm 1956, nơi thuật ngữ “trí tuệ nhân tạo” được đưa ra. " đã được hình thành. Đây vẫn là quan điểm trung tâm phổ biến của Hoa Kỳ về sự xuất hiện của AI ngày nay. Như tôi đã cố gắng trình bày ở đây, quan điểm này là sai lầm và không thể thiếu hiểu biết hơn về lịch sử AI và khoa học máy tính nói chung.
Sẽ không có AI nếu không có cuộc khủng hoảng nền tảng của toán học và logic vào cuối thế kỷ 19 và đầu thế kỷ 20 cũng như những nỗ lực to lớn, thành tựu và hiểu biết thiên tài của những người như Frege, Russell, Hilbert, Goedel và Turing, chỉ kể tên một số ít.
Hội nghị Dartmouth được tổ chức chỉ 2 năm sau cái chết bi thảm và sớm của Alan Turing vào năm 1954. Một nhóm những người tài giỏi đã gặp nhau ở Dartmouth để thúc đẩy chương trình nghị sự về trí tuệ máy móc và mỗi người trong số họ đều có những đóng góp đáng chú ý và nổi tiếng cho AI và một số lĩnh vực khác. đến khoa học nói chung (như Minsky và Shannon) trong những thập kỷ sau và trong nửa sau thế kỷ 20 và đã đưa chúng ta đến vị trí ngày nay trong lĩnh vực AI. Không còn nghi ngờ gì nữa, hội nghị này là một cột mốc quan trọng trong sự phát triển của AI, nhưng nó không nên được coi là ngày ra đời của nó - giống như nền văn hóa thế giới của chúng ta cũng không nên được coi là bắt đầu từ việc khám phá ra Châu Mỹ.
Vì sự tiến bộ và hàng loạt kết quả về AI đã đạt được sau hội nghị này đã được biết đến và ghi lại rất rõ ràng nên tôi không cần phải nhắc lại ở đây và tôi kết thúc hành trình lịch sử nhỏ bé của mình về sự khởi đầu và sự xuất hiện của AI. .
Phần kết luận
Ngay cả sau hơn 75 năm, sự liên quan và tác động của các định lý Goedel vẫn là chủ đề thảo luận trong giới AI cũng như trong triết học khoa học và toán học ngày nay. Một số nhà khoa học cho rằng các định lý của Goedel cho thấy những rào cản không thể vượt qua về nguyên tắc đối với các máy móc hiện tại để trở nên thực sự thông minh (hoặc có ý thức về vấn đề đó) và các định lý này đã giáng một đòn chí mạng vào mọi nỗ lực xây dựng, chẳng hạn như AGI (trí thông minh nhân tạo) và trí thông minh ở cấp độ con người. các hệ thống trong AI.
Tôi thà rút ra một kết luận khác từ các định lý của Goedel: tác động của các định lý của ông vẫn có thể được cảm nhận bởi sự thống trị hiện nay của toán học trong các mô hình AI và hầu hết các phương pháp tiếp cận AI. Tuy nhiên, tất cả trí thông minh mà chúng ta biết cho đến nay chỉ xuất hiện trong các hệ thống sinh học, sống chứ không phải trong các máy móc dựa trên các nguyên tắc toán học, logic hoặc kỹ thuật như tất cả các mô hình AI hiện đại.
Nhìn lại, các định lý cho chúng ta thấy rằng có thể chúng ta đã đi sai đường đến AI. Do đó, con đường phía trước của AI nằm ở cái mà tôi gọi là “bước ngoặt sinh học”.
Do đó, câu hỏi quan trọng đối với AI trong thế kỷ 21 là: làm thế nào để các hệ thống sinh học đạt được trí thông minh? (xem thêm bài viết gần đây của tôi: Bẻ khóa mã thần kinh).
Nếu toán học hiện tại và logic tính toán không thể đưa chúng ta đến trí thông minh (nhân tạo) và ý thức máy móc ở cấp độ con người, thì các ngành khoa học khác như sinh học hệ thống, hóa học hệ thống, sinh học tính toán, vật lý sinh học, sinh học tế bào (lý thuyết) hiện đại và hiện đại. Thay vào đó, khoa học nhận thức (thần kinh) sẽ dẫn đầu.
E. Schoneburg, Hồng Kông, ngày 8 tháng 5 năm 2017
0 Comments
Đăng nhận xét