Thứ Năm, 3 tháng 5, 2012

Định lý Goedel và Thông tin


Định lý Goedel và Thông tin

Gregory J. Chaitin

Người dịch: Hà Hữu Nga

Định lý của Goedel có thể được biểu diễn bằng cách sử dụng các lập luận có một thiên hướng lý thuyết thông tin. Bằng cách tiếp cận như vậy, người ta có thể lập luận rằng nếu một định lý chứa nhiều thông tin hơn một tập tiên đề nhất định thì định lý có thể xuất phát từ các tiên đề đó. Ngược lại với cách chứng minh truyền thống dựa trên nghịch lý về lời nói dối, quan điểm mới này gợi ý rằng hiện tượng về tính chất không hoàn thiện được Goedel phát hiện là tự nhiên và phổ biến rộng rãi chứ không phải là bất thường và mang tính bệnh lý.

I. Giới thiệu

Để xác lập một cấp số, chúng ta hãy lắng nghe Hermann Weyl (1946), theo đọan trích của Eric Temple Bell (1951):

Chúng tôi không dám chắc về những cơ sở tối hậu của logic và toán học. Giống như tất cả mọi người và tất cả mọi thứ trong thế giới ngày nay, chúng ta có vấn đề “khủng hoảng” của mình. Chúng ta đã vấp phải nó gần 50 năm nay rồi. Nhìn bề ngoài, dường như ngày nay chẳng có gì cản trở công việc hàng ngày của chúng ta cả, nhưng tôi xin thay mặt cho ai đó thú nhận rằng đã có một ảnh hưởng thực tiễn to lớn đối với đời sống toán học của tôi: nó dẫn dắt ý thích của tôi đến những lĩnh vực mà tôi coi là tương đối “an toàn”, và là một kênh chắc chắn khơi nguồn nhiệt tình và lòng quyết tâm khiến tôi có thể theo đuổi công việc nghiên cứu của mình. Kinh nghiệm này có lẽ cũng được các nhà toán học khác chia sẻ. Họ chính là những con người không hề thờ ơ với những nỗ lực khoa học của họ trong ngữ cảnh của toàn bộ những mối bận tâm và tìm hiểu, sự chịu đựng và tồn tại sáng tạo của con người trên thế giới này.

Và đây chính là những gì John von Neumann (1963) thể hiện:

... đã tồn tại trong kinh nghiệm của mọi người mà giờ đây vẫn đang sống ít nhất là ba cuộc khủng hoảng nghiêm trọng…Đó là hai cuộc khủng hoảng về vật lý – có tên gọi là tìm kiếm - linh hồn khái niệm gắn liền với những phát hiện trong lý thuyết lượng tử …Cuộc khủng hoảng thứ ba trong toán học. Đó là một cuộc khủng hoảng khái niệm nghiêm trọng liên quan đến phương pháp chứng minh toán học một cách chính xác và nghiêm nhặt. Theo những quan niệm trước đây về sự nghiêm nhặt tuyệt đối của toán học, thật đáng ngạc nhiên là một sự việc như vậy lại có thể xảy ra, và thậm chí còn đáng ngạc nhiên hơn nữa khi nó lại đã có thể xảy ra trong những ngày gần đây khi mà những điều thần kỳ không được giả định là có thể xuất hiện nữa. Nhưng nó đã thực sự xuất hiện.

Trong thời gian phát hiện ra nó, cái định lý về tính chất không hoàn hảo Kurt Goedel ấy thật là một cú sốc lớn và đã gây ra một tính bất định lớn và sự suy sụp của nhiều nhà toán học nhạy cảm với các vấn đề cơ bản, vì dường như là nó đã lật tung tấm chăn che đậy tính tất định, tính khách quan, và tính nghiêm nhặt toán học.

Cách chứng minh của nó còn được coi là cực kỳ khó hiểu và tối nghĩa. Nhưng thời gian trôi qua, tình hình đã đảo ngược. Một số lượng lớn những cách chứng minh khác nhau về định lý Goedel mọi người đều đã biết, và giờ đây người ta lại coi là dễ chứng minh và hầu như rất rõ ràng: nó cũng tương đương với tính không thể giải được của vấn đề còn đang treo lại, hoặc thay vào đó bằng lời xác quyết rằng có một tập đếm được theo cách đệ qui (r.e) nhưng lại không phải là tập đệ qui. Và nó đã không còn kéo dài ảnh hưởng đến cuộc sống hàng ngày của các nhà toán học hoặc đến thói quen làm việc của họ nữa; không ai còn bị mất ăn mất ngủ vì nó nữa.

Cách chứng minh nguyên gốc của Goedel đã tạo ra một xác quyết nghịch lý rằng nó là chân, nhưng không thể chứng minh bằng những cách hình thức hóa thông thường của lý thuyết số. Ngược lại, tôi muốn đo lường bản số của một tập tiên đề và qui tắc suy luận. Tôi mong có thể nói được rằng nếu ai đó có 10 bảng tiên đề và một định lý 20 bảng, thì cái định lý đó không thể xuất phát từ các tiên đề đó. Và tôi sẽ lập luận rằng cách tiếp cận ấy đối với định lý Goedel thực sự gợi ra một thay đổi trong những thói quen hàng ngày của các nhà toán học, và định lý của Goedel không thể bị rũ bỏ được.

Để cụ thể hơn, tôi sẽ áp dụng quan điểm nhiệt động học và cơ học thống kê đối với định lý Goedel, và sẽ sử dụng các khái niệm ấy như một xác suất, tính ngẫu nhiên, entropi, và thông tin để nghiên cứu hiện tượng tính không hoàn hảo và cố gắng đánh giá xem nó mở rộng như thế nào. Dựa trên cơ sở phân tích này, tôi gợi ý rằng toán học có lẽ có bà con họ hàng với vật lý nhiều hơn là nó có ý định thừa nhận, và có lẽ câu trả lời chính xác cho định lý Goedel là một thái độ mềm dẻo hơn liên quan đến việc chấp nhận các tiên đề và các phương pháp suy lý mới. Các chứng minh xác suất về tính nguyên qua cách lấy mẫu (Chaitin and Schwartz, 1978) cũng gợi ý rằng các nguồn chân lý toán học thường lớn hơn cái mà người ta vẫn nghĩ. Có lẽ lý thuyết số nên được theo đuổi một cách cởi mở hơn theo tinh thần của khoa học thực nghiệm (Púlya, 1959)!.

Tôi mắc nợ McCarthy và nhất là Jacob Schwartz về việc làm cho tôi nhận ra rằng định lý của Goedel không phải là một trở ngại đối với hệ thống trí tuệ nhân tạo thực tiễn AT* [công nghệ nâng cao] dựa trên logic hình thức. Một trí tuệ nhân tạo như vậy sẽ có hình thức của một bộ kiểm tra chứng minh trí tuệ. Giấc mơ của Gottfried Wilhelm Liebnitz và David Hilbert về các cuộc tranh cãi có thể được giải quyết bằng các từ  “Thưa các ngài, xin để cho chúng tôi tính đã!”, và toán học có thể được hình thức hóa, sẽ vẫn là một đề tài nghiên cứu thiết thực. Ngay cho dù các nhà toán học và các nhà logic học có lầm lạc để lỡ chuyến tàu tư tưởng đã được ngăn lại bởi định lý của Goedel thì những tiến bộ to lớn trong thực tế cũng đã được thực hiện một cách “lén lút” dưới cái biển hiệu của khoa học máy tính, LISP* [Ngôn ngữ xử lý danh sách] và AI* (Cole et al., 1981; Dewar et al., 1981; Levin, 1974; Wilf, 1982).

Nói bằng cách ẩn dụ theo Douglas Hofstadter (1979), giờ đây chúng ta sẽ dạo qua một Gallery Nghệ thuật các cách chứng minh định lý của Goedel, đến cách phối màu các bức tranh của Moussorgsky trong một cuộc triển lãm!. Chúng ta hãy bắt đầu với một vài cách chứng minh truyền thống (Davis, 1978; Hofstadter, 1979; Levin, 1974; Post, 1965).

2. Chứng minh Truyền thống Định lý Goedel

Cách chứng minh nguyên bản của Goedel về định lý tính chất không hoàn hảo là dựa trên cơ sở nghịch lý của lời nói dối: “Phán đoán này là giả”. Ông đã phát hiện được một định lý thay vì một nghịch lý bằng cách thay đổi câu đó thành: “Phán đoán này không thể chứng minh được”. Nếu khẳng định này là không thể chứng minh được thì nó là giả, và việc hình thức hóa của lý thuyết số trong vấn đề này là không hoàn thiện. Nếu khẳng định này có thể được chứng minh thì nó là giả, và việc hình thức hóa lý thuyết số là không nhất quán. Cách chứng minh nguyên bản ấy là hoàn toàn khó hiểu rất giống với một chương trình dài trong ngôn ngữ máy. Kỹ thuật nổi tiếng của Goedel bằng cách số hóa các phán đoán là một trong nhiều ý tưởng tài tình được đưa ra để xây dựng một xác quyết lý thuyết số tự nói về bản thân nó rằng nó là không thể chứng minh được.

Cách chứng minh nguyên bản của Goedel được áp dụng vào việc hình thức hóa riêng cho lý thuyết số, và được triển khai thành một bài báo chỉ ra rằng các phương pháp tương tự được áp dụng vào một lớp rất rộng lớn các hệ thống tiên đề hình thức. Cách tiếp cận hiện đại trong thực tế áp dụng vào toàn bộ các hệ tiên đề hình thức một khái niệm thậm chí vẫn chưa được định nghĩa khi Goedel viết bài báo đầu tiên của ông, bằng cách còn nợ vì thiếu một định nghĩa toán học về thao tác hiệu quả hoặc thuật toán máy tính. Sau khi Alan Turing tiếp tục định nghĩa thao tác hiệu quả bằng cách tạo ra một phép tính lý tưởng hóa giản đơn mà ngày nay gọi là máy Turing (cũng được Emil Post độc lập thực hiện thành công), giờ đây đã có thể tiến đến một loại tổng hợp hơn.

Đòi hỏi chủ chốt của Hilbert đối với một hệ thống toán học hình thức là ở chỗ cần có một tiêu chuẩn khách quan để quyết định xem liệu một cách chứng minh được viết bằng một ngôn ngữ của hệ thống có hiệu lực hay không. Nói cách khác, phải có một thuật toán, một chương trình máy tính, một máy Turing để kiểm tra các cách chứng minh. Và định nghĩa hiện đại cô đọng về hệ tiên đề hình thức như một tập các khẳng định đếm được theo cách đệ qui là kết quả trực tiếp khi người ta sử dụng cái gọi là thuật toán Bảo tàng Anh. Người ta áp dụng bộ kiểm tra chứng minh lần lượt đối với tất cả những cách chứng minh có thể, và in tất cả các định lý nào đương nhiên là có lượng thời gian vô cùng lớn. Bằng cách đó, trong thực tế, LISP là một ngôn ngữ lập trình rất thuận tiện dùng để viết một bộ kiểm tra chứng minh đơn giản (Levin, 1974).

Turing đã chỉ ra rằng một vấn đề đang còn treo lại thì không thể giải quyết được, có nghĩa là không có thao tác hiệu quả hoặc thuật toán để quyết định xem liệu chương trình ấy có treo hay không. Được trang bị bằng một định nghĩa tổng quát về hệ tiên đề hình thức như một tập các khẳng định đếm được theo cách đệ qui bằng một ngôn ngữ hình thức, người ta có thể trực tiếp suy luận được một phiên bản của định lý về tính không hoàn hảo của Goedel từ định lý Turing. Tôi sẽ phác thảo ba cách chứng minh khác nhau về tính không thể giải được của vấn đề đang treo cùng một lúc; trước hết tôi xin được bắt đầu từ định lý của Goedel. Việc suy luận rất đơn giản là nếu luôn luôn có thể chứng minh các chương trình đặc biệt có bị treo hay không, vì tập các định lý là đệ quy, thì người ta có thể sử dụng cái đó để giải vấn đề đang bị treo cho bất cứ một chương trình đặc biệt nào bằng cách liệt kê toàn bộ các định lý cho đến khi vấn đề được giải quyết. Nhưng điều đó lại mâu thuẫn với tính chất không thể giải được của vấn đề còn đang treo lại.

Đến đây đã xuất hiện ba kiểu chứng minh mà vấn đề đang bị treo thì không thể giải quyết được. Một kiểu chứng minh cho rằng hàm F(N) được định nghĩa là một hàm nhiều hơn giá trị của hàm có thể tính toán thứ N được áp dụng cho số tự nhiên N, hoặc 0 nếu giá trị này không được xác định vì chương trình máy tính thứ N không treo trên đầu vào N. F không thể là một hàm có thể tính toán, vì nếu chương trình N tính toán nó thì người ta sẽ có F(N) = F(N) + 1, là thứ không thể có được. Nhưng chỉ có một cách duy nhất là F có thể không tính toán được vì người ta không thể quyết định xem chương trình thứ N có bị treo khi cho đầu vào N không.

Cách chứng minh mà tôi vừa đưa ra tất nhiên là một loại phương pháp chéo mà Georg Cantor sử dụng để chỉ ra rằng các số thực nhiều hơn các số tự nhiên (Courant and Robbins, 1941). Có một cái gì đó gần hơn với kỹ thuật nguyên bản của Cantor cũng có thể được sử dụng để chứng minh định lý Turing. Lập luận ấy phù hợp với các nguyên tắc của nghịch lý Bertrand Russell (Russell, 1967) về tập hợp mọi thứ gì không phải là thành viên của bản thân chúng. Hãy xem xét các chương trình cho những tập đếm được của các số tự nhiên và hãy đánh số các chương trình máy tính đó. Hãy xác định một tập các số tự nhiên bao gồm cả các con số của toàn bộ chương trình không bao gồm con số riêng trong tập đầu ra của nó. Tập các số tự nhiên này không thể là tập đếm được theo cách đệ qui vì nếu nó được liệt kê bởi chương trình máy tính N thì người ta gặp phải nghịch lý người thợ cạo Bertrand Russell trong một thị trấn nhỏ, ông ta cạo râu cho tất cả mọi người và chỉ cạo cho những người không thể tự cạo được cho bản thân mình và cũng không thể tự cạo cho bản thân mình cũng như không thể tránh làm như vậy được. Nhưng chỉ có một cách duy nhất là tập hợp này không thể trở thành tập đếm được theo cách đệ qui vì nếu nó không thể quyết định có cung cấp một con số tự nhiên cụ thể hay không, và đây là loại vấn đề treo.

Nhưng đối với một cách chứng minh khác về tính chất không thể giải quyết được của vấn đề đang treo, hãy xem xét các chương trình không có đầu vào mà vẫn tạo ra một con số đơn tự nhiên như là đầu ra hoặc như là một chuỗi vô tận mà không hề có việc tạo ra một đầu ra. Hãy suy nghĩ về các chương trình này như là được viết bằng khái niệm nhị phân thay cho những con số tự nhiên như trước. Giờ đây tôi xác định được cái gọi là hàm Busy Beaver: BB của N là đầu ra số tự nhiên lớn nhất bằng bất kỳ chương trình nào có kích cỡ nhỏ hơn N bit. Hàm Busy Beaver gốc đo kích cỡ chương trình trong khuôn khổ con số của các trạng thái trong một máy Turing thay cho việc sử dụng phép đo lý thuyết thông tin chính xác hơn là các bits. Vậy là rất dễ nhận thấy rằng  BB của N phát triển nhanh hơn bất kỳ hàm có thể tính toán nào, và vì vậy mà không thể tính toán được, là tình trạng như trước, hàm ý rằng vấn đề đang treo là không thể giải quyết được.

Bằng một tiểu luận hoàn mỹ và dễ hiểu, Post (1965) đã chứng minh cho các phiên bản của định lý Goedel dựa trên những khái niệm của ông về các tập đếm được theo cách đệ qui. Và ông đã công thức hóa dạng lý thuyết trừu tượng hiện đại của Goedel giống hệt một bài thơ haiku Nhật Bản: có một tập đệ quy của các con số tự nhiên không đệ qui. Tập này có thuộc tính là có những chương trình để in toàn bộ các thành viên của tập theo một trật tự nào đó, nhưng không phải là trật tự đi lên. Cuối cùng người ta có thể nhận ra rằng một con số tự nhiên là một thành viên của tập nhưng không có thuật toán để quyết định xem một con số nhất định có thuộc tập đó hay không. Tập đó là đệ quy nhưng phần bù của nó thì lại không. Trong thực tế, tập các con số của các chương trình đang treo là một tập như vậy. Giờ đây chúng ta hãy xem xét một tập tiên đề hình thức đặc biệt trong đó người ta có thể nói về các con số tự nhiên và những chương trình máy tính, và hãy để cho X là bất cứ tập đệ quy nào mà phần bù của nó không phải là đệ quy. Lập tức xuất hiện một vấn đề là không phải toàn bộ các xác quyết về hình thức “con số tự nhiên N không phải là một thành viên của tập X” là những định lý thuộc hệ tiên đề hình thức. Trong thực tế, nếu X là cái mà Post gọi là một tập đệ quy đơn thì cuối cùng nhiều xác quyết như vậy có thể trở thành các định lý.

Những cách chứng minh truyền thống định lý về tính không hoàn hảo của Goedel đã chỉ ra rằng các hệ tiên đề hình thức là không hoàn hảo, nhưng chúng lại không đưa ra những cách thức để đo lường bản số của các hệ tiên đề hình thức, để sắp xếp mức độ hoàn hảo hoặc không hoàn hảo. Thực ra thì khái niệm về một tập đơn của Post chứa đựng viên ngọc của những phiên bản lý thuyết thông tin của định lý Goedel là cái mà tôi sẽ đưa ra sau, nhưng đây chỉ là hiển nhiên trong hồi tưởng. Bằng cách nào đó người ta có thể chọn ra một tập X đệ quy đơn đặc biệt và xếp hạng các hệ tiên đề hình thức theo một cách thức như thế nào để cho nhiều định lý dạng “N không thuộc X” khác nhau là có thể chứng minh. Dưới đây là ba phiên bản định lượng khác của định lý về tính không hoàn hảo của Goedel là kiểu phân loại rơi vào phạm vi của các phương pháp truyền thống.

Hãy xem xét một hệ tiên đề hình thức đặc biệt trong đó người ta có thể nói về các hàm hồi qui tổng thể, các hàm có thể tính toán, mà chúng có một con số tự nhiên như là giá trị cho mỗi đầu vào con số tự nhiên, và tính chất phức tạp về mặt thời gian vận hành của chúng. Người ta có thể cấu trúc một hàm hồi qui tổng thể phát triển nhanh hơn bất cứ hàm nào là hàm hồi qui tổng thể có thể chứng minh bằng hệ tiên đề hình thức. Người ta cũng có thể cấu trúc một hàm hồi qui tổng thể dài hơn để tính toán bất cứ hàm hồi qui tổng thể có thể chứng minh nào. Thế có nghĩa là một chương trình máy tính tạo ra một sản phẩm số tự nhiên và sau đó treo bất cứ khi nào nó được cung cấp một đầu vào con số tự nhiên, nhưng điều này lại không thể được chứng minh bằng hệ tiên đề hình thức vì chương trình quá dài không thể sản xuất ra sản phẩm của nó. Cũng rất thú vị khi sử dụng các bản số siêu hạn cấu trúc (Hofstadter, 1979) để đo lường bản số của các hệ tiên đề hình thức. Một bản số cấu trúc là một loại có thể đạt được khi giới hạn dưới của một chuỗi có thể tính toán những bản số cấu trúc nhỏ hơn. Người ta đo lường bản số của một hệ tiên đề hình thức bằng bản số cấu trúc đầu tiên trong hệ. Điều này giống như nghịch lý của bản số không thể xác định hoặc bản số không được đề cập đầu tiên (Russell, 1967)!

Trước khi quay trở về với các định lý về tính chất không hoàn hảo của lý thuyết thông tin, trước hết tôi phải giải thích các khái niệm cơ bản của lý thuyết thông tin thuật toán (Chaitin, 1975b, 1977, 1982).

3. Lý thuyết Thông tin Thuật toán

Lý thuyết thông tin thuật toán tập trung vào các đối tượng riêng mà không phải là vào các tập hợp và các phân phối xác xuất được xem xét trong lý thuyết thông tin của Claude Shannon và Norbert Wiener. Cần bao nhiêu bits để mô tả phương thức tính toán một đối tượng riêng lẻ?. Nói cách khác, chương trình nhỏ nhất để tính cho nó là bao nhiêu bits? Rất dễ thấy rằng từ mục đích tổng quát, các máy tính, loại máy Turing phổ quát, có thể tái tạo mô hình cho nhau, thì việc lựa chọn máy tính như một tiêu chuẩn so sánh không phải là điều quan trọng nhất và thực sự chỉ tương thích với việc lựa chọn gốc trong một hệ thống điều khiển mà thôi.

Các khái niệm cơ bản của lý thuyết thông tin này là: nội dung thông tin thuật toán, thông tin chung, thông tin liên quan, thông tin lẫn nhau, tính ngẫu nhiên thuật toán, và sự độc lập thuật toán. Tất cả những khái niệm đó được định nghĩa đơn giản như sau:

Nội dung thông tin thuật toán H(X) của một đối tượng riêng X được xác định là kích cỡ của chương trình nhỏ nhất để tính X. Các chương trình phải tự giải giới hạn đến mức là thủ tục con có thể được kết hợp bằng việc giàng buộc lẫn nhau giữa chúng. Thông tin chung H(X,Y) của hai đối tượng X Y được xác định là kích cỡ của chương trình nhỏ nhất để đồng thời tính XY. Nội dung thông tin điều kiện và tương đối H(XIY) của X được cho Y được xác định là kích cỡ của chương trình nhỏ nhất để tính X từ một chương trình tối thiểu cho Y.

Hãy lưu ý rằng nội dung thông tin tương đối của một đối tượng không hề lớn hơn nội dung thông tin tuyệt đối của nó, vì việc trở thành nguồn thông tin bổ sung nhất định chỉ có thể trợ giúp. Cũng vậy, vì các thủ tục con có thể được ràng buộc với nhau nó tiếp nối cái mà thông tin chung là cộng tính dưới. Thế có nghĩa là nội dung thông tin chung được khoanh lại ở trên bằng tổng của các nội dung thông tin cá lẻ của các đối tượng đang được đặt vấn đề. Mức độ mà nội dung thông tin chung ít hơn tổng này dẫn đến khái niệm cơ bản tiếp theo, nguồn thông tin lẫn nhau.

Nội dung thông tin lẫn nhau H(X:Y) đo lường tính chất chung của XY: nó được xác định là mức độ mà việc biết X giúp cho người ta tính được Y, về cơ bản hệt như mức độ biết Y giúp cho người ta tính được X, cũng hệt như mức độ rẻ hơn để tính toán chúng cùng với nhau chứ không phải tách rời nhau. Thế có nghĩa là:

H(X:Y)
=
H(X) − H(X|Y)

=
H(Y) − H(Y|X)

=
H(X) + H(Y) − H(X,Y).

Cần lưu ý rằng điều này hàm ý là:

H(X,Y)
=
H(X) + H(Y|X)

=
H(Y) + H(X|Y).

Giờ đây tôi có thể xác định hai khái niệm rất cơ bản và có ý nghĩa về phương diện triết học: tính ngẫu nhiên thuật toán và tính độc lập thuật toán. Tôi tin rằng các thuật toán này hoàn toàn gắn chặt với các khái niệm trực giác xét theo cùng một cái tên, một đối tượng là hỗn độn, điển hình, không đáng để ý, không có cấu trúc, mô hình hoặc các đặc điểm khác biệt, và là nguồn thông tin tối giản, và hai đối tượng không có gì chung và không có mối liên hệ nào.

Hãy xem xét chẳng hạn, tập toàn bộ các chuỗi dài N-bit. Hầu hết những chuỗi S như vậy có H(S) xấp xỉ ngang bằng với N thêm H(N), là N thêm thông tin thuật toán bao gồm trong chữ số hai-cơ sở cho N, ngang bằng với N thêm trật tự của log N. Không hề có một S dài N-bit có nội dung thông tin lớn hơn nội dung này. Một số có nội dung thông tin ít hơn; đó là những chuỗi có cấu trúc hoặc mô hình chính qui. Các S với một kích cỡ nhất định có nội dung thông tin lớn nhất được coi là ngẫu nhiên hoặc không thành mô hình hoặc không thể ép được. Sự tách rời giữa cái ngẫu nhiên và không ngẫu nhiên là ở đâu đó xung quanh H(S) ngang bằng với N nếu chuỗi S dài N bits.

Tương tự như vậy, một chuỗi nhị phân vô tận chẳng hạn như việc mở rộng hai cơ sở của p là ngẫu nhiên khi và chỉ khi toàn bộ các phân đoạn đầu tiên của nó là ngẫu nhiên, có nghĩa là khi và chỉ khi có một hằng số C như là không có phân đoạn đầu tiên nào có nội dung thông tin ít hơn C bits dưới độ dài của nó. Tất nhiên p là đối cực của một chuỗi ngẫu nhiên: nó chỉ có dạng H(N) là trật tự của log N bits để tính N bits đầu tiên của p. Nhưng cái xác xuất mà một chuỗi vô tận đạt được bằng những lần gieo đồng tiền một cách công bằng là ngẫu nhiên về phương diện thuật toán thì có tính thống nhất.

Hai chuỗi là độc lập về phương diện thuật toán nếu thông tin chung của chúng về cơ bản là zero, chính xác hơn, nếu thông tin chung của chúng nhỏ hết mức có thể. Hãy xem xét chẳng hạn hai chuỗi bất kỳ X Y mà mỗi chuỗi có kích cỡ N bits. Thông thường thì XY là ngẫu nhiên với nhau, ngoại trừ một thực tế là chúng có cùng độ dài, sao cho H(X:Y) xấp xỉ ngang bằng với H(N). Nói cách khác việc biết một trong số chúng là không giúp ích gì được trong việc tính chuỗi khác ngoại trừ một điều là chúng nói cho người ta về kích cỡ của chuỗi kia.

Để minh họa cho các ý tưởng này, hãy cho phép tôi đưa ra một cách chứng minh lý thuyết thông tin có nhiều vô tận các số nguyên (Chaitin, 1979). Hãy giả định ngược lại rằng chỉ có rất nhiều số nguyên hữu hạn trong thực tế K của chúng. Hãy xem xét một số tự nhiên ngẫu nhiên N. Một mặt chúng ta biết rằng H(N) ngang bằng với log2 N + trật tự của log log N, vì chữ số hai-cơ sở cho N là một chuỗi (log2 N)-bit ngẫu nhiên về phương diện thuật toán. Mặt khác, N có thể được tính từ những số mũ trong quá trình nhân tử hóa nguyên tố của nó, và ngược lại. Vì vậy H(N) ngang bằng với thông tin chung của các số mũ K trong quá trình nhân tử hóa nguyên tố của nó. Bằng tính cộng dưới, thông tin chung này được giới hạn từ trên bằng tổng của các nội dung thông tin của các số mũ K riêng lẻ. Mỗi số mũ là thuộc về trật tự log N. Vì vậy nội dung thông tin của mỗi số mũ là thuộc về trật tự log log N. Vì vậy H(N) đồng thời ngang bằng với log2 N + O (log log N) và ít hơn hoặc bằng với K O (log log N), là không thể.

Các khái niệm lý thuyết thông tin thuật toán được làm ra để sắp xếp trật tự nhằm đạt được các định lý về tính không hoàn hảo về mặt định lượng, và giờ đây tôi sẽ đưa ra một số chứng minh lý thuyết thông tin của định lý Goedel (Chaitin, 1974a, 1974b, 1975a, 1977, 1982; Chaitin and Schwartz, 1978; Gardner, 1979).

4. Chứng minh Lý thuyết Thông tin Định lý Goedel

Tôi giả sử rằng chúng ta coi một hệ tiên đề hình thức là một chương trình máy tính để liệt kê tập các định lý, và đo kích cỡ của nó bằng bits. Nói cách khác, việc đo kích cỡ của một hệ tiên đề hình thức mà tôi sẽ sử dụng là hoàn toàn khó khăn. Đó chỉ là một lượng không gian mà nó chiếm để chỉ định rõ một thuật toán kiểm tra chứng minh và làm thế nào để áp dụng nó vào toàn bộ các chứng minh có thể, là cái nói chung là một lượng không gian mà nó chiếm là rất chính xác về trật tự chữ cái alphabet, ngữ vựng, ngữ pháp, các tiên đề, và các qui tắc suy luận. Điều đó cân bằng với số trang mà nó chiếm để thể hiện hệ tiên đề hình thức trong một cuốn sách giáo khoa.

Đây là định lý bất hoàn hảo lý thuyết thông tin đầu tiên. Hãy xem xét một hệ tiên đề hình thức N-bit. Có một chương trình máy tính kích cỡ N không bị treo, nhưng người ta không thể chứng minh điều này trong hệ tiên đề hình thức. Một mặt, N bits của các tiên đề có thể cho phép người ta suy diễn một cách chính xác những chương trình nhỏ hơn N nào bị treo còn những chương trình nào thì không. Nếu Chúa nói với chúng ta có bao nhiêu chương trình kích cỡ khác nhau ít hơn N bị treo thì điều này có thể được thể hiện như là một số hai cơ sở N-bit, và từ đó cuối cùng người ta có thể suy luận những chương trình nào bị treo, những chương trình nào thì không. Một khải huyền thay thế sẽ biết được rằng chương trình cỡ nhỏ hơn N dài nhất sẽ bị treo. Trong ngữ cảnh hiện thời, các chương trình có toàn bộ các đầu vào chứa trong chúng.

Có một cách khác để cản trở một hệ tiên đề hình thức N-bit thì chỉ việc tung một đồng xu hai mặt thật đều nhiều hơn N lần một chút. Hầu như chắc chắn việc tạo ra một chuỗi nhị phân sẽ là ngẫu nhiên về phương diện thuật toán, nhưng lại không thể chứng minh điều này bằng hệ tiên đề hình thức. Nếu người ta tin rằng định đề của cơ học lượng tử mà Chúa chơi súc sắc với vũ trụ, còn Albert Einstein thì không, thì vật lý học cung cấp một phương tiện để thể hiện những giới hạn của các hệ tiên đề hình thức. Thực tế trong một hệ tiên đề hình thức N-bit người ta vẫn không thể chứng minh được rằng một đối tượng đặc biệt có nội dung thông tin thuật toán lớn hơn N, thậm chí dù hầu như toàn bộ, toàn bộ nhưng hạn chế vào nhiều, các đối tượng đều có thuộc tính này.

Cách chứng minh này rất giống với nghịch lý “con số tự nhiên đầu tiên không thể gọi bằng một cái tên không dưới 1 tỷ từ” của G.G. Berry được Russell công bố vào đầu thế kỷ (Russell 1967). Phiên bản nghịch lý Berry sẽ gây ra một trò lường gạt là “cái đối tượng có cách chứng minh ngắn nhất trong hệ tiên đề hình thức sau là cái mà nội dung thông tin lớn hơn nội dung thông tin của hệ tiên đề hình thức...” mà ở đó các điểm được điền đầy bằng một sự mô tả hoàn chỉnh hệ tiên đề hình thức đang được đặt vấn đề.  

Nhân tiện cũng cần phải nói rằng trong một hệ tiên đề hình thức nhất định người ta chỉ có thể chứng minh rằng nhiều chuỗi đặc biệt hạn chế là ngẫu nhiên, nó có mối liên hệ chặt chẽ với khái niệm về một tập đệ quy đơn của Post. Thực sự thì tập không ngẫu nhiên hoặc các chuỗi có thể nén là một tập đệ quy đơn. Vì vậy Berry và Post đã có mầm mống của định lý bất hoàn hảo của tôi!

Để tiếp tục, tôi phải xác định một số thực ngẫu nhiên hấp dẫn về phương diện thuật toán giữa zero và một, là số mà tôi muốn gọi là O (Chaitin, 1975b; Gardner, 1979). O là chủ thể thích hợp cho việc thờ cúng của những thầy mật tế, đối với những người chẳng hạn như Charles Bennett (Gardner, 1979) đã lập luận một cách thuyết phục theo nghĩa O chứa toàn bộ chân lý toán học kiến thiết và thể hiện nó một cách chính xác và cô đọng nhất. Việc biết giá trị số của O với N bits chính xác, điều đó có nghĩa là việc biết N bits đầu tiên của sự mở rộng hai cơ sở O, là một tiên đề N-bit cho phép người ta suy luận một cách chính xác những chương trình kích cỡ nào ít hơn N bị treo và những chương trình kích cỡ nào không bị treo.  

O được xác định là xác suất treo của bất kỳ mục đích tổng quát tiêu chuẩn nào mà máy tính được chọn, nếu mỗi bit chương trình của nó được sản xuất ra bởi một lần tung một đồng xu công bằng một cách độc lập. Đối với định lý của Turing trong lý thuyết hàm hồi qui mà vấn đề treo không thể giải quyết được thì ở đó có sự tương hợp trong lý thuyết thông tin thuật toán với định lý mà sự mở rộng hai cơ sở của O là ngẫu nhiên về mặt thuật toán. Vì vậy nó coi N bits của các tiên đề có thể chứng minh cho kết quả của N bits đầu tiên của O. Và những bits này dường như là hoàn toàn ngẫu nhiên giống như các sản phẩm của một quá trình vật lý ngẫu nhiên vậy. Vì vậy người ta có thể đo bản số của một hệ tiên đề hình thức bằng bao nhiêu giá trị số của O mà nó có thể suy luận từ các tiên đề của nó. Loại đo lường này giống như đo lường bản số của một hệ tiên đề hình thức trong khuôn khổ kích cỡ tính bằng bits của những chương trình ngắn nhất mà vấn đề của nó không thể được quyết định trong hệ tiên đề hình thức.

Có thể xác định định lý về tính bất hoàn hảo này bằng cách liên quan đến O sao cho không hề đề cập trực tiếp đến các xác suất treo, thực tế là trong khuôn khổ lý thuyết số đơn giản khi không hề đề cập gì đến các chương trình máy tính. O có thể được thể hiện như là giới hạn của một dãy có thể tính toán của các số hữu tỷ ngày càng đơn điệu. Vì vậy bit thứ N của nó là giới hạn khi T hướng đến tính vô hạn của một hàm có thể tính toán của NT. Vì vậy bit thứ N của O có thể được thể hiện dưới dạng ?X ?Y [thuộc tính có thể tính toán của X, Y, và N]. Các hỗn độn hoàn hảo chỉ là hai lượng từ cách biệt hẳn với tính chất có thể tính toán! O cũng có thể được thể hiện thông qua một đa thức P trong một trăm biến số, với các hệ số số nguyên và các số mũ (Davis et al., 1976): bit thứ N của O là một số 1 khi và chỉ khi có nhiều số tự nhiên vô hạn K chẳng hạn như phương trình P(N, K, X1, ... , X98) = 0 có một cách giải bằng các số tự nhiên.

Tất nhiên O có vấn đề rất nghiêm trọng là nó chiếm một thời gian quá dài để suy luận các định lý từ bản thân nó, và đây cũng là trường hợp với hai tiên đề khác mà chúng ta đã xem xét. Vì vậy tiên đề toán hoàn hảo lý tưởng thực tế là vô dụng! Người ta thực sự không muốn cái tiên đề cô đọng nhất để suy luận một tập nhất định của các khẳng định. Hệt như có một sự đánh đổi giữa kích cỡ chương trình và thời gian vận hành, có một sự dung hòa giữa số bits của các tiên đề mà người ta muốn thừa nhận và kích cỡ của các chứng minh. Tất nhiên các chân lý ngẫu nhiên hoặc tối giản không thể được nén thành các tiên đề ngắn hơn bản thân chúng. Tuy nhiên nếu một tập các khẳng định không độc lập về phương diện thuật toán thì nó sẽ chiến số bits của các tiên đề ít hơn để suy luận ra toàn bộ số chúng so với tổng của số các bits của các tiên đề mà chúng cần để  suy luận một cách tách biệt, và điều đó là đáng mong ước chừng nào các cách chứng minh không chiếm quá dài. Điều đó gợi ý một thái độ thực dụng đối với chân lý toán học, một cái gì đó giống với chân lý của các nhà vật lý nhiều hơn.

Chân lý của chúng ta thực sự là một cuộc dạo chơi dài qua một phòng trưng bày những định lý không hoàn hảo. Cái gì là kết cục hoặc là đạo đức? Đó là lúc để thực hiện một phán đoán về ý nghĩa của định lý Goedel.

5. Ngữ nghĩa của Định lý Goedel

Lý thuyết thông tin gợi ra rằng hiện tượng Goedel là tự nhiên và phổ biến, chứ không phải là một loại bệnh học hoặc bất thường. Rất lạ là nó lại thực hiện điều đó thông qua việc giải thích các lập luận, và không có việc trưng ra các xác quyết đơn lẻ tuy là thực, nhưng lại không thể chứng minh! Tuy nhiên điều đó giúp ta có được những cách chứng minh đặc biệt thú vị và những khẳng định tự nhiên chân thật không thể được thể hiện trong các hệ tiên đề hình thức thời thượng.

Vấn đề thực sự là ở chỗ: có phải định lý Goedel là một nhiệm vụ cho cuộc cách mạng, tình trạng vô chính phủ, và sự bừa bãi?! Người ta có thể dứt bỏ sau khi cố gắng trong vòng hai tháng để chứng minh một định lý, và bổ sung cho nó như một tiên đề mới? Điều này có vẻ là lố bịch, nhưng nó lại là một loại mà các nhà lý thuyết số đã thực hiện với sự phỏng đoán của Bernhard Riemann? (Polya 1959).Tất nhiên hai tháng thì không đủ. Các tiên đề mới nên được lựa chọn cẩn thận, vì tính chất hữu dụng của chúng và những số lượng lớn bằng chứng gợi ý rằng chúng là đúng khi cũng được xem xét một cách cẩn thận, có nghĩa là trong hoạt động của cộng đồng vật lý học.

Bản thân Goedel đã tán thành quan điểm này với một sinh lực và tính minh bạch to lớn, trong thảo luận của ông về việc liệu có phải giả thuyết liên tục Cantor nên được bổ sung vào lý thuyết tập như một tiên đề mới (Goedel 1964):

Ngay cả việc bất chấp sự cần thiết nhu cầu nội tại của một tiên đề mới nào đó, và ngay cả trong trường hợp không hề có một sự cần thiết nội tại nào thì một quyết định có thể chứng minh về chân lý của nó cũng theo một cách khác, cụ thể là về phương diện suy luận bằng cách nghiên cứu “sự thành công” của nó. Sự thành công ở đây có nghĩa là tính chất hoàn thiện trong các kết quả, đặc biệt là trong các kết quả “có thể xác minh”, tức là các kết quả có thể thể hiện mà không cần tiên đề mới, những cách chứng minh với sự trợ giúp của tiên đề mới, tuy nhiên việc phát hiện lại đơn giản hơn và dễ dàng hơn rất nhiều, và có thể rút gọn nhiều cách chứng minh khác nhau thành một cách. Các tiên đề cho hệ thống các số thực bị các nhà trực giác luận phản đối theo nghĩa đó, đều đã được xác minh ở một mức độ nào đó, bằng cách viện đến một sự thật là lý thuyết số phân tích thường xuyên cho phép người ta chứng minh những định lý lý thuyết số bằng một cách thức rất nặng nề, lại có thể được xác minh bằng các phương pháp cơ bản. Tuy nhiên một mức độ minh xác cao hơn thế có thể hiểu được. Có thể có những tiên đề quá thừa kết quả có thể xác minh của chúng khi rọi sáng rực rỡ vào một lĩnh vực tổng thể, và bằng cách có được các phương pháp mạnh như vậy để giải quyết các vấn đề, và thậm chí còn giải quyết chúng một cách xây dựng, ở chừng mực có thể, đó là không có vấn đề liệu chúng có cần thiết hay không, chúng có được chấp nhận một cách tối thiểu theo cùng một nghĩa như bất cứ lý thuyết vật lý nào đã được thiết kế thành công hay không.

Dưới đây Goedel tiếp tục thảo luận về những ý tưởng này:

Trước đây người ta đã chỉ ra rằng bên cạnh trực giác toán học, có tồn tại một tiêu chuẩn khác, mặc dù chỉ là có thể, về chân lý của các tiên đề toán, cụ thể là thành quả của chúng trong toán học, và có thể thêm cả trong vật lý học nữa...Trường hợp ứng dụng đơn giản nhất tiêu chuẩn đó vào cuộc thảo luận đã xuất hiện khi một tiên đề.... nào đó có những kết quả lý thuyết số có thể minh xác bằng việc tính toán cho đến bất kỳ một số nguyên nào.

Goedel cũng tự thể hiện bằng những thuật ngữ bất định trong một thảo luận về logic toán của Russell  (Goedel 1964):

Tính tương đồng giữa toán học và các khoa học tự nhiên cũng được Russell bàn luận sâu về một khía cạnh khác... các tiên đề cần rõ ràng không phải trong bản thân chúng, mà là sự minh xác của chúng, chính xác như trong vật lý học, nằm trong một sự thật là chúng tạo khả năng cho “các tri giác cảm tính” này được diễn dịch... Tôi cho rằng ... quan điểm này đã được minh định một cách rộng rãi bằng những phát triển tiếp theo, và người ta hy vọng rằng nó sẽ càng như vậy trong tương lai. Hóa ra là việc giải quyết bất kỳ vấn đề thuật toán nào cũng đều đòi hỏi việc sử dụng các giả định đề cơ bản là siêu vượt thuật toán...Hơn nữa dường như có vẻ là để giải quyết bất kỳ vấn đề nào về lý thuyết tập trừu tượng và thậm chí về những vấn đề có liên quan của lý thuyết các số thực thì các tiên đề mới dựa trên một ý tưởng nào đó cho đến lúc này vẫn còn chưa được biết sẽ là cần thiết. Có lẽ những khó khăn rõ ràng là không thể vượt qua được mà một vài vấn đề toán học khác thể hiện trong nhiều năm là căn cứ vào một thực tế là các tiên đề cần thiết lại vẫn chưa được tìm ra. Tất nhiên trong các hoàn cảnh này toán học có thể đánh mất nhiều “tính bất định tuyệt đối” của nó; nhưng dưới ảnh hưởng của phê bình hiện đại về các cơ sở, điều này đã xảy ra ở một mức độ rộng lớn...

Tôi muốn kết thúc như tôi đã bắt đầu với một đoạn trích từ công trình của Weyl (1949): “Một toán học thực sự hiện thực phải được lĩnh hội theo cùng một nguyên tắc với vật lý, như một ngành của cấu trúc lý thuyết của một thế giới thực, và phải chấp nhận cùng một thái độ cẩn trọng và tỉnh táo đối với những khai triển có tính giả thuyết về các cơ sở của nó như nó đã được thể hiện trong vật lý vậy”.

6. Định hướng Nghiên cứu Tương lai

Hãy chứng minh rằng một phỏng đoán toán học nổi tiếng là không thể giải được trong những hình thức hóa của lý thuyết số. Vấn đề: nếu “định lý cuối cùng” của Pierre Fermat là không thể giải được thì nó là chân, vậy thì điều đó khó thực hiện được.

a. Hình thức hóa toàn bộ môn toán đại học bằng một cách thực tiễn. Người ta muốn viết ra những cuốn sách giáo khoa có thể được tự do sử dụng thông qua một bộ kiểm tra chứng minh hình thức thực tiễn và không quá dày so với những cuốn vẫn được sử dụng. LISP (Levin, 1974) và SETL* (Dewar et al., 1981) có thể rất thích hợp cho định hướng này.

b. Lý thuyết thông tin thuật toán có phù hợp với vật lý, đặc biệt là với nhiệt động học và cơ học thống kê không? Khai thác nhiệt động học ước tính (Bennett, 1982) và xác định các cực giới hạn vật lý của các máy tính.

c. Có tồn tại một hiện tượng vật lý tính toán một cái gì đó không thể tính toán không? Ngược lại, có phải luận đề của Turing cho rằng bất cứ cái gì có thể tính toán thì đều có thể được tính bằng một máy Turing giới hạn vũ trụ vật lý mà chúng ta đang tồn tại không?

d. Phát triển những phương pháp đo lường tự tổ chức và các chứng minh hình thức cho rằng đời sống phải tiến hóa (Chaitin, 1979; Eigen and Winkler, 1981; von Neumann, 1966).

e. Phát triển các định nghĩa hình thức về trí tuệ và các phép đo những cấu phần khác nhau của nó; áp dụng lý thuyết thông tin và lý thuyết phức tạp vào AI.
____________________________________

Chú thích:

AI*                    [Artifact Intelligence]: Trí tuệ Nhân tạo
AT*                   [Advanced Technology]: Công nghệ Nâng cao
LISP*                 [List Processing Language]: Ngôn ngữ xử lý danh sách
SETL*                [Set Theory as a Language]: Lý thuyết tập như một ngôn ngữ

Nguồn: Goedel's Theorem and Information - International Journal of Theoretical Physics 22 (1982), pp. 941-954. Gregory J. Chaitin, IBM Research, P.O. Box 218, York Town Heights, New York 10598

Tác giả: Tiến sĩ Gregory John Chaitin, sinh năm 1947, Giáo sư Toán học và Khoa học Máy tính Đại học Buenos Aires, Argentina và Đại học Auckland, New Zealand. Ông còn viết về triết học, đặc biệt là siêu hình học và triết học toán học.

Ghi chú của Tác giả:

Trong bài viết này tôi đã thay ký hiệu I(x) bằng phức hợp quy mô chương trình của x bằng ký hiệu tôi dùng hiện nay H(x). GJC, 13 Dec 95.

References

Xin được đưa ra một vài gợi ý về tư liệu. Những xuất bản phẩm trước đây về định lý Gödel bao gồm: Chaitin, 1974a, 1974b, 1975a, 1977, 1982; Chaitin và Schwartz, 1978. Liên quan đến các xuất bản phẩm của các tác giả khác gồm có Davis, 1978; Gardner, 1979; Hofstadter, 1979; Levin, 1974; Post, 1965. Để có thêm các thảo luận về tri thức luận toán học và khoa học, xem Einstein, 1944, 1954; Feynman, 1965; Gödel, 1964; Pólya, 1959; von Neumann, 1956, 1963; Taub, 1961; Weyl, 1946, 1949.

Bell, E. T. 1951. Mathematics, Queen and Servant of Science, McGraw-Hill, New York.

Bennett, C. H. 1982. The thermodynamics of computation---a review. Published in International Journal of Theoretical Physics, 21, 905-940.

Chaitin, G. J. 1974a. Information – theoretic computational complexity. Published in EEE Transactions on Information Theory, IT-20, 10-15.

Chaitin, G. J. 1974b. Information – theoretic limitations of formal systems. Published in Journal of the ACM, 21, 403-424.

Chaitin, G. J. 1975a. Randomness and mathematical proof. Published in Scientific American, 232 (5), May 1975, 47-52. Also published in the French, Japanese, and Italian editions of Scientific American.

Chaitin, G. J. 1975b. A theory of program size formally identical to information theory. Published in Journal of the ACM, 22, 329-340.

Chaitin, G. J. 1977. Algorithmic information theory. Published in IBM Journal of Research and Development, 21, 350-359, 496.

Chaitin, G. J., and Schwartz, J. T. 1978. A note on Monte Carlo primality tests and algorithmic information theory. Published in Communications on Pure and Applied Mathematics, 31, 521-527.

Chaitin, G. J. 1979. Toward a mathematical definition of “life”. Published in The Maximum Entropy Formalism, R. D. Levine and M. Tribus (eds.), MIT Press, Cambridge, Massachusetts, pp. 477-498.

Chaitin, G. J. 1982. Algorithmic information theory. Published in Encyclopedia of Statistical Sciences, Vol. 1, Wiley, New York, pp. 38-41.

Cole, C. A., Wolfram, S., et al. 1981. SMP: a symbolic manipulation program, California Institute of Technology, Pasadena, California.

Courant, R., and Robbins, H. 1941. What is Mathematics? Oxford University Press, London.

Davis, M., Matijasevic, Y., and Robinson, J. 1976. Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution. Published in Mathematical Developments Arising from Hilbert Problems, Proceedings of Symposia in Pure Mathematics, Vol. XXVII, American Mathematical Society, Providence, Rhode Island, pp. 323-378.

Davis, M. 1978. What is a computation? Published in Mathematics Today: Twelve Informal Essays, L. A. Steen (ed.), Springer-Verlag, New York, pp. 241-267.

Dewar, R. B. K., Schonberg, E., and Schwartz, J. T. 1981. Higher Level Programming: Introduction to the Use of the Set-Theoretic Programming Language SETL. Courant Institute of Mathematical Sciences, New York University, New York.

Eigen, M., and Winkler, R. 1981. Laws of the Game, Knopf, New York.

Einstein, A. 1944. Remarks on Bertrand Russell's theory of knowledge. Published in The Philosophy of Bertrand Russell, P. A. Schilpp (ed.), Northwestern University, Evanston, Illinois, pp. 277-291.

Einstein, A. 1954. Ideas and Opinions, Crown, New York, pp. 18-24.

Feynman, A. 1965. The Character of Physical Law, MIT Press, Cambridge, Massachusetts.

Gardner, M. 1979. The random number Ω bids fair to hold the mysteries of the universe

Mathematical Games Dept. Published in Scientific American, 241 (5) (November 1979), 20-34.

Gödel, K. 1964. Russell's mathematical logic, and What is Cantor's continuum problem?. Published in Philosophy of Mathematics, P. Benacerraf and H. Putnam (eds.), Prentice-Hall, Englewood Cliffs, New Jersey, pp. 211-232, 258-273.

Hofstadter, D. R. 1979. Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, New York.

Levin, M. 1974. Mathematical Logic for Computer Scientists, MIT Project MAC report MAC TR-131, Cambridge, Massachusetts. 

Pólya, G. 1959. Heuristic reasoning in the theory of numbers. Published in American Mathematical Monthly, 66, 375-384.

Post, E. 1965. Recursively enumerable sets of positive integers and their decision problems. Published in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, M. Davis (ed.), Raven Press, Hewlett, New York, pp. 305-337.

Russell, B. 1967. Mathematical logic as based on the theory of types. Published in From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, J. van Heijenoort (ed.), Harvard University Press, Cambridge, Massachusetts, pp. 150-182.

Taub, A. H. (ed.) 1961. J. von Neumann---Collected Works, Vol. I, Pergamon Press, New York, pp. 1-9.

von Neumann, J. 1956. The mathematician. Published in The World of Mathematics, Vol. 4, J. R. Newman (ed.), Simon and Schuster, New York, pp. 2053-2063.

von Neumann, J. 1963. The role of mathematics in the sciences and in society, and Method in the physical sciences. Published in J. von Neumann---Collected Works, Vol. VI, A. H. Taub (ed.), McMillan, New York, pp. 477-498.

von Neumann, J. 1966. Theory of Self-Reproducing Automata, A. W. Burks (ed.), University of Illinois Press, Urbana, Illinois.

Weyl, H. 1946. Mathematics and logic. Published in American Mathematical Monthly, 53, 1-13.

Weyl, H. 1949. Philosophy of Mathematics and Natural Science, Princeton University Press, Princeton, New Jersey.

Wilf, H. S. 1982. The disk with the college education. Published in American Mathematical Monthly, 89, 4-8.


Không có nhận xét nào:

Đăng nhận xét