BerandaComputers and TechnologySurat dari Gödel untuk von Neumann

Surat dari Gödel untuk von Neumann

Kurt Gödel Kurt Gödel datang ke dunia kita seratus tahun yang lalu hari ini. Teorema ketidaklengkapan Gödel mengubah cara yang kita pikirkan matematika.
Kami mencetak ulang terjemahan dari surat he yang sekarang terkenal menulis lima puluh tahun yang lalu kepada von Neumann yang ditemukan kembali di 1988. Surat ini menjelaskan sesuatu yang dekat dengan masalah P versus NP tahun sebelum bidang Computational Complexity bahkan memilikinya nama. SIGACT dan EATCS bersama-sama mensponsori hadiah yang diberi nama Gödel karena surat itu.
Princeton, 20 Maret 1956
Tuan von Neumann yang terhormat:
Dengan kesedihan terbesar saya telah mempelajari penyakit Anda. Berita itu datang bagi saya sebagai hal yang tidak terduga. Morgenstern musim panas lalu sudah memberitahuku pertarungan kelemahan yang pernah Anda miliki, tetapi pada saat itu dia berpikir bahwa ini tidak memiliki signifikansi yang lebih besar. Seperti yang saya dengar, dalam beberapa bulan terakhir Anda telah menjalani perawatan radikal dan saya senang dengan perawatan ini berhasil seperti yang diinginkan, dan sekarang Anda melakukannya dengan lebih baik. saya harap dan berharap untuk Anda bahwa kondisi Anda akan segera membaik bahkan lebih dan bahwa penemuan medis terbaru, jika memungkinkan, akan mengarah pada a pemulihan lengkap.
Karena Anda sekarang, seperti yang saya dengar, merasa lebih kuat, saya ingin mengizinkan diri saya menulis tentang masalah matematika, yang menurut pendapat Anda akan sangat menarik bagi saya: Jelas sekali dengan mudah membuat mesin Turing, yang pertama untuk setiap formula F urutan logika predikat dan setiap bilangan asli n, memungkinkan seseorang untuk memutuskan jika ada bukti F panjang n (panjang=jumlah simbol). Membiarkan ψ (F, n) adalah jumlah langkah yang dibutuhkan mesin untuk ini dan biarkan φ (n)=max F ψ (F, n). Pertanyaannya adalah seberapa cepat φ (n) tumbuh untuk mesin yang optimal. Dapat ditunjukkan bahwa φ (n) ≥ k ⋅ n. Jika memang ada mesin dengan φ (n) ∼ k ⋅ n (atau bahkan ∼ k ⋅ n 2 ), ini akan memiliki konsekuensi terbesar pentingnya. Yaitu, itu jelas akan berarti meskipun ketidakpastian dari masalah Entscheidung, pekerjaan mental dari seorang ahli matematika tentang pertanyaan Ya-atau-Tidak bisa sepenuhnya diganti dengan mesin. Bagaimanapun, seseorang hanya harus memilih file bilangan asli n begitu besar sehingga saat mesin tidak mengirimkan a Akibatnya, tidak masuk akal untuk memikirkan lebih banyak tentang masalah tersebut. Sekarang ini bagi saya, bagaimanapun, sepenuhnya berada dalam ranah kemungkinan bahwa φ (n) tumbuh dengan lambat. Sejak

  1. sepertinya φ (n) ≥ k ⋅ n adalah satu-satunya estimasi yang dapat diperoleh dengan a generalisasi dari bukti keragu-raguan dari Entscheidungsproblem dan
  2. setelah semua φ (n) ∼ k ⋅ n (atau ∼ k ⋅ n 2 ) hanya berarti jumlah langkah yang trial and error dapat dikurangi dari N menjadi log N (atau (log N) 2 ).

Namun, pengurangan yang kuat seperti itu muncul di batas lain masalah, misalnya dalam perhitungan residu kuadrat simbol menggunakan penerapan berulang dari hukum timbal balik. Itu akan Menarik untuk diketahui, misalnya, situasi tentang penentuan keutamaan suatu bilangan dan seberapa kuat secara umum jumlah langkah dalam masalah kombinatorial hingga dapat dikurangi dengan sehubungan dengan pencarian lengkap yang sederhana.
Saya tidak tahu apakah Anda pernah mendengar itu “Masalah posting”, apakah ada derajat tidak dapat dipecahkan antara masalah bentuk (∃ y) φ (y, x), di mana φ adalah rekursif, diselesaikan dalam arti positif oleh a pria yang sangat muda dengan nama Richard Friedberg. Solusinya sangat anggun. Sayangnya, Friedberg tidak berniat untuk belajar matematika, melainkan kedokteran (tampaknya di bawah pengaruh ayahnya). Ngomong-ngomong, apa pendapat Anda tentang upaya membangun dasar-dasar analisis pada teori tipe bercabang, yang memiliki baru-baru ini mendapatkan momentum? Anda mungkin menyadari bahwa Paul Lorenzen telah mendorong pendekatan ini ke teori Lebesgue mengukur. Namun, saya percaya itu di bagian penting dari analisis metode bukti impredikatif yang tidak dapat dihilangkan memang muncul.
Saya akan sangat senang mendengar sesuatu dari Anda secara pribadi. Tolong beri tahu saya jika ada sesuatu yang bisa aku lakukan untukmu. Dengan salam terbaik saya dan keinginan, juga untuk istrimu,
Hormat kami,
Kurt Gödel
P.S. Saya dengan tulus mengucapkan selamat kepada Anda atas penghargaan yang diberikan orang Amerika itu pemerintah telah memberikan kepadamu.
[The text is taken from this pagewhere you can also find the original German text andacknowledgments. John von Neumann, who received the Presidential Medal of Freedom in 1956, had cancer at the time ofthe letter and passed away in 1957.]

% % item_read_more_button %%

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments