Apa contoh paling sederhana dari program yang kita tidak tahu apakah mereka berakhir?

Masalah penghentian menyatakan tidak ada algoritma yang akan menentukan apakah program yang diberikan berhenti. Sebagai konsekuensinya, harus ada program yang tidak dapat kami katakan apakah mereka berakhir atau tidak. Apa contoh paling sederhana (paling kecil) dari program semacam itu?

Contoh yang cukup sederhana bisa berupa program yang menguji dugaan Collatz :

$n$$5 × 2^{60} ≈ 5.764 × 10^{18}$

Masalah penghentian menyatakan tidak ada algoritma yang akan menentukan apakah program yang diberikan berhenti. Sebagai konsekuensinya, harus ada program yang tidak dapat kami katakan apakah mereka berakhir atau tidak.

"Kami" bukan suatu algoritma =) Tidak ada algoritma umum yang dapat menentukan apakah suatu program berhenti untuk setiap program .

Apa contoh paling sederhana (paling kecil) dari program semacam itu?

Pertimbangkan program berikut:

n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

Function is_perfect memeriksa apakah n adalah angka sempurna . Tidak diketahui apakah ada angka sempurna yang aneh, jadi kami tidak tahu apakah program ini berhenti atau tidak.

Anda menulis:

Masalah penghentian menyatakan tidak ada algoritma yang akan menentukan apakah program yang diberikan berhenti. Sebagai konsekuensinya, harus ada program yang tidak dapat kami katakan apakah mereka berakhir atau tidak.

Ini adalah non-sequitur, di kedua arah. Anda menyerah pada kesalahan umum yang layak ditangani.

$P$$P$$P$

Hanya jika Anda mengharuskan algoritme harus menyelesaikan masalah Penghentian untuk semua program can Anda dapat menunjukkan bahwa tidak ada algoritma seperti itu yang dapat ada.

Sekarang, mengetahui bahwa masalah Penghentian tidak dapat dipastikan tidak menyiratkan bahwa ada program yang tidak dapat dibuktikan oleh siapa pun yang tidak dapat dihentikan atau dibatalkan. Bahkan jika Anda tidak lebih kuat dari mesin Turing (yang hanya merupakan hipotesis, bukan fakta yang terbukti), yang kami tahu adalah bahwa tidak ada algoritma tunggal / orang yang dapat memberikan bukti seperti itu untuk semua program. Mungkin ada orang yang berbeda yang dapat memutuskan untuk setiap program.

Beberapa bacaan terkait lainnya:

• Bagaimana bisa diputuskan apakah π$\pi$
• Daya komputasi manusia: Bisakah manusia memutuskan masalah yang terputus pada Mesin Turing?
• Algoritma untuk memecahkan "masalah terputus-" Turing
• Sintesis program, decidability, dan masalah penghentian
• Apakah mungkin untuk menyelesaikan masalah penghentian jika Anda memiliki input yang terbatas atau dapat diprediksi?
• Mengapa fungsi total tidak dapat dihitung?

Jadi, Anda melihat bahwa pertanyaan Anda yang sebenarnya (seperti yang diulang di bawah) tidak ada hubungannya dengan apakah masalah penghentian itu dapat dihitung. Sama sekali.

Apa contoh paling sederhana (terkecil) dari [program yang kita tidak tahu untuk menghentikan atau mengulangi]?

$S$

$\qquad\displaystyle g(n) = \begin{cases}1, &S \text{ true},\\ g(n+1), &\text{else}.\end{cases}$

Memang, ini tidak terlalu "alami".

1. Tidak semua , tetapi "banyak" dalam arti tertentu. Paling tidak banyak, setidaknya.

Setiap masalah terbuka mengenai keberadaan nomor dengan properti tertentu memunculkan program semacam itu (yang mencari nomor tersebut). Sebagai contoh, ambil dugaan Collatz; karena kami tidak tahu apakah itu benar, kami juga tidak tahu apakah program berikut berakhir:

    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1  

Mengingat bahwa masalah Sibuk Berang-berang tidak diselesaikan untuk mesin Turing 5-negara-2-simbol, harus ada mesin Turing dengan hanya lima negara dan hanya dua simbol yang belum terbukti berhenti atau tidak ketika mulai untuk pita kosong . Itu adalah program yang sangat singkat, singkat, dan tertutup.

pertanyaannya rumit karena decidability (formalisasi / generalisasi setara CS untuk masalah penghentian) dikaitkan dengan bahasa sehingga perlu disusun kembali dalam format itu. ini tampaknya tidak banyak ditunjukkan, tetapi banyak masalah terbuka dalam matematika / CS dapat dengan mudah dikonversi ke masalah (bahasa) dari kepastian keputusan yang tidak diketahui. ini adalah karena korespondensi yang ketat antara pembuktian teorema dan (un) analisis desidabilitas. misalnya (agak seperti jawaban lainnya dengan angka sempurna ganjil), ambil dugaan bilangan prima kembar yang berasal dari Yunani (lebih dari 2 milenia yang lalu) dan tunduk pada kemajuan penelitian besar baru-baru ini misalnya oleh Zhang / Tao. mengubahnya menjadi masalah algoritmik sebagai berikut:

Input: n . Output: Y / N ada setidaknya n primer kembar.

algoritma mencari bilangan prima kembar dan berhenti jika menemukan n dari mereka. tidak diketahui apakah bahasa ini dapat dipilih. penyelesaian masalah bilangan prima kembar (yang menanyakan apakah ada jumlah terbatas atau tak terbatas) juga akan menyelesaikan kepantasan bahasa ini (jika juga dibuktikan / ditemukan berapa banyak, jika terbatas).

contoh lain, ambil hipotesis Riemann dan pertimbangkan bahasa ini:

Input: n . Output: Y / N ada setidaknya n nol nol dari fungsi Riemann zeta.

Algoritme mencari nol nol (kode ini tidak terlalu kompleks, mirip dengan pencarian root, dan ada formulasi lain yang setara yang relatif sederhana, yang pada dasarnya menghitung jumlah "paritas" dari semua bilangan prima kurang dari x dll) dan berhenti jika ia menemukan n dari mereka dan lagi, yang tidak diketahui apakah bahasa ini adalah decidable dan resolusi adalah "hampir" setara dengan memecahkan dugaan Riemann.

sekarang, bagaimana dengan contoh yang lebih spektakuler? ( Peringatan, mungkin lebih kontroversial juga)

Input: c: Output: Y / N terdapat algoritma O (n ^c ) untuk SAT.

sama halnya, resolusi desidabilitas bahasa ini hampir setara dengan masalah P vs NP . namun ada kasus yang kurang jelas untuk kode "sederhana" untuk masalah dalam kasus ini.

$1 ≤ n ≤ 10^{50}$

$10^{20}$