Angka dugaan dan dugaan Goldbach?

Latar belakang: Saya orang awam yang lengkap dalam ilmu komputer.

Saya membaca tentang angka-angka Sibuk Berang-berang di sini , dan saya menemukan bagian berikut:

Kemanusiaan mungkin tidak pernah tahu nilai BB (6) untuk yang pasti, apalagi BB (7) atau angka yang lebih tinggi dalam urutan.

Memang, sudah lima pesaing teratas dan enam aturan lolos dari kita: kita tidak bisa menjelaskan bagaimana mereka 'bekerja' dalam istilah manusia. Jika kreativitas menanamkan desain mereka, itu bukan karena manusia meletakkannya di sana. Salah satu cara untuk memahami ini adalah bahwa bahkan mesin Turing kecil dapat menyandikan masalah matematika yang mendalam. Ambil dugaan Goldbach, bahwa setiap angka genap 4 atau lebih tinggi adalah jumlah dari dua bilangan prima: 10 = 7 + 3, 18 = 13 + 5. Dugaan ini telah menolak bukti sejak 1742. Namun kita dapat merancang mesin Turing dengan, oh, katakanlah 100 aturan, yang menguji setiap bilangan genap untuk melihat apakah itu jumlah dua bilangan prima, dan berhenti kapan dan jika ia menemukan contoh berlawanan dengan dugaan. Kemudian mengetahui BB (100), pada prinsipnya kita dapat menjalankan mesin ini untuk langkah-langkah BB (100), memutuskan apakah itu berhenti, dan dengan demikian menyelesaikan dugaan Goldbach.

Aaronson, Scott. "Siapa yang bisa menyebutkan nomor yang lebih besar?" Siapa yang bisa menyebutkan nomor yang lebih besar? Np, nd Web. 25 November 2016.

Bagi saya sepertinya penulis menyarankan agar kita dapat membuktikan atau menyangkal dugaan Goldbach, sebuah pernyataan tentang jumlah yang tak terhingga banyaknya, dalam jumlah perhitungan yang terbatas. Apakah saya melewatkan sesuatu?

Pernyataan itu tentang angka yang tak terhingga banyaknya, tetapi demonstrasi (atau sanggahannya) harus menjadi latihan yang terbatas. Jika memungkinkan.

Kejutan mungkin datang dari asumsi (salah) bahwa menemukan BB (100) akan menjadi masalah "secara teoritis lebih mudah", hanya dibuat mustahil karena alasan praktis - karena ada begitu banyak mesin, dan mereka dapat berjalan untuk waktu yang lama sebelum berhenti. , jika sama sekali - setelah semua, mereka hanya mesin ...

Yang benar adalah bahwa menemukan BB (n), untuk n cukup besar, harus menjadi tugas unsurmountable, karena kedua alasan teoritis dan praktis.

Gagasan dari penulis adalah bahwa Anda dapat menulis sebuah program dalam 100 baris (angka berhingga tetap di sini) yang melakukan hal berikut: mengambil angka x, menguji dugaan. Jika tidak benar maka hentikan yang lain lanjutkan ke nomor berikutnya.

Mengetahui nomor berang-berang yang sibuk Anda dapat mensimulasikan mesin ini untuk jumlah langkah itu dan kemudian memutuskan apakah itu berhenti atau tidak. Dari atas, jika berhenti - dugaan tidak benar, jika tidak berhenti - dugaan itu benar.

Aaronson baru-baru ini memperluas secara terperinci tentang pemikiran / gagasan ini di sini bekerja dengan Yedidia. [1] mereka menemukan mesin negara 4888 eksplisit untuk dugaan Goldbach. Anda dapat membaca kertas untuk melihat bagaimana itu dibuat. TM jarang dibangun tetapi yang cenderung seperti kompiler berdasarkan bahasa tingkat tinggi dan kompiler menambah banyak status. "hand built" TM dapat dengan mudah menggunakan urutan negara dengan jumlah yang lebih sedikit, misalnya dalam 100an atau kurang dari 100. dengan kata lain tidak ada upaya dalam makalah ini untuk mencoba benar-benar meminimalkan # kondisi . ide umumnya adalah suara dan para ilmuwan komputer umumnya tidak begitu khawatir tentang konstanta yang tepat dan pekerjaan yang diterapkan.

teori umum ini diuraikan oleh Caludes (juga dikutip oleh [1]) dalam dua makalah yang sangat bagus yang menguraikan beberapa teorema cerita rakyat panjang di daerah ini dan yang telah dicatat oleh penulis lain (misalnya Michel). [2] [ 3] pada dasarnya setiap masalah matematika terbuka dapat dikonversi menjadi masalah yang tidak dapat dipastikan. ini karena sebagian besar masalah matematika melibatkan pencarian jumlah kasus yang tak terbatas untuk sampel tandingan dan sampel tandingan yang dapat diperiksa secara algoritmik (tetapi mungkin tidak efisien atau memerlukan TM besar, dll.).

juga, TM "sangat kecil" (dihitung dalam # negara) dapat memeriksa / setara dengan masalah matematika yang sangat rumit. misalnya perkiraan kasar untuk TM untuk menyelesaikan dugaan collatz akan menjadi beberapa lusin negara.

jadi ada hubungan / analogi yang menarik antara ketidakpastian dan kelengkapan NP. NP adalah kelas masalah yang dapat diperiksa secara efisien, yaitu instance dapat diperiksa dalam waktu P. masalah yang tidak dapat ditentukan adalah kelas dari semua masalah yang memungkinkan pemeriksaan algoritmik untuk sampel tandingan tanpa batas efisiensi.

di sini adalah cara dasar untuk memahami koneksi dengan masalah berang-berang yang sibuk. semua masalah yang tidak dapat dipastikan sama karena Turing computability / equivalence. sama seperti semua masalah NP lengkap dapat dikonversi satu sama lain dalam waktu P (pengurangan), semua masalah yang tidak dapat diputuskan adalah setara karena kelengkapan Turing dan pengurangan yang dapat dihitung (yang dapat mengambil waktu sewenang-wenang). maka masalah berang-berang yang sibuk dalam pengertian ini setara dengan masalah penghentian, dan jika seseorang dapat menyelesaikan berang-berang yang sibuk, maka seseorang dapat menyelesaikan semua pertanyaan matematika terbuka.

[1] TM yang relatif kecil yang perilakunya tidak tergantung pada teori himpunan / Yedidia, Aaronson

[2] Mengevaluasi Kompleksitas Masalah Matematika: Bagian 1 / Calude

[3] Mengevaluasi Kompleksitas Masalah Matematika: Bagian 2 / Calude

1. Dugaan Goldbach dapat dipalsukan (jika benar-benar salah) oleh program TM tersebut; itu tidak dapat dibuktikan benar dengan cara ini (seorang ahli matematika yang berwawasan luas, bagaimanapun, mungkin melakukan ini).

2. Mengetahui BB (27) akan memungkinkan untuk menghentikan pencarian Goldbach di beberapa titik; namun demikian BB (27) (atau Chaitin's Omega (27)) sebelumnya perlu tahu, apakah Goldbach TM akhirnya berhenti, atau tidak.

Oleh karena itu menyesatkan untuk mengatakan "BB (27) termasuk jawaban untuk Goldbach". Meskipun demikian, yang lebih penting adalah: "Goldbach (dan banyak lainnya) adalah prasyarat untuk nomor BB (27)", dengan kata lain tidak ada yang namanya "fungsi-BB" yang Anda tantang di 27. Kami jalankan saja semua mesin 27-negara, inkl. Goldbach, dan hanya setelah fakta melihat BB (27). Dan, dari POV praktis, bahkan BB (6) tampaknya sulit dipahami.

Saya pikir itu terasa kurang misterius jika kita menyatakan kembali poin Aaronson dalam hal bukti:

$C$$C$$C$$C$

$C$$C$$n$$BB(n)$$C = O(BB(n))$