Đị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 và Y
được xác định là kích cỡ của chương trình nhỏ nhất để đồng thời tính X và Y.
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 X và Y:
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 và Y mà mỗi chuỗi có kích cỡ N bits. Thông thường thì X và Y
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 N
và T. 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