Bagaimana itu bisa diputuskan apakah memiliki beberapa urutan digit?

Kami diberi latihan berikut.

Membiarkan

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Buktikan bahwa dapat dihitung.$f$

Bagaimana ini mungkin? Sejauh yang saya tahu, kita tidak tahu apakah berisi setiap urutan digit (atau yang) dan algoritma tentu saja tidak dapat memutuskan bahwa beberapa urutan tidak terjadi. Karena itu saya pikir tidak dapat dihitung, karena masalah yang mendasarinya hanya semi-decidable.$\pi$$f$

Hanya ada dua kemungkinan untuk dipertimbangkan.

• Untuk setiap bilangan bulat positif , string muncul dalam representasi desimal dari . Dalam hal ini, algoritma yang selalu mengembalikan 1 selalu benar.$n$$0^n$$\pi$

• Ada bilangan bulat terbesar sehingga muncul dalam representasi desimal dari . Dalam hal ini algoritma berikut (dengan nilai dikodekan) selalu benar:$N$$0^N$$\pi$$N$

  Zeros-in-pi(n):
   if (n > N) then return 0 else return 1
  

Kami tidak tahu mana dari kemungkinan ini yang benar, atau berapa nilai adalah yang benar dalam kasus kedua. Namun demikian, salah satu dari algoritma ini dijamin benar. Dengan demikian, ada algoritma untuk memutuskan apakah string nol muncul di ; masalahnya adalah decidable.$N$$n$$\pi$

Perhatikan perbedaan halus dengan sketsa bukti berikut yang diajukan oleh gallais :

1. Ambil mesin Turing acak dan input acak.
2. Entah perhitungan akan berlangsung selamanya atau akan berhenti di beberapa titik dan ada fungsi yang dapat dihitung (konstan) yang menggambarkan masing-masing perilaku ini.
3. ???
4. Keuntungan!

Alex ten Brink menjelaskan:

perhatikan apa yang dinyatakan teorema Henti-Hentinya: dikatakan bahwa tidak ada satu program pun yang dapat memutuskan apakah suatu program dihentikan. Anda dapat dengan mudah membuat dua program sedemikian rupa sehingga salah satu menghitung apakah program yang diberikan berhenti: yang pertama selalu mengatakan 'itu berhenti', yang kedua 'tidak berhenti' - satu program selalu benar, kami hanya tidak dapat menghitung yang mana dari mereka!

sepp2k menambahkan:

Dalam contoh Alex, algoritma tidak akan mengembalikan hasil yang tepat untuk semua input. Dalam kasus pertanyaan ini, salah satunya akan melakukannya. Anda dapat mengklaim bahwa masalahnya dapat diputuskan karena Anda tahu bahwa ada algoritma yang menghasilkan hasil yang tepat untuk semua input. Tidak masalah apakah Anda tahu algoritma yang mana. 10

Hanya memposting sedikit elaborasi pada jawaban JeffE.

Kita tahu bahwa ada dua fungsi / kasus yang dapat menghitung fungsi f (n):

1. Fungsi yang selalu mengembalikan true (untuk semua n, ada n jumlah 0 berturut-turut)
2. Fungsi yang akan mengembalikan true jika n lebih kecil dari integer N, di mana N didefinisikan sebagai panjang maksimum berturut-turut 0 yang ada dalam bilangan irasional yang diberikan (jika tidak mengembalikan false).

Satu dan hanya satu dari fungsi ini yang bisa benar. Kami tidak tahu yang mana, tetapi kami tahu pasti bahwa ada jawaban. Komputasi mensyaratkan bahwa ada fungsi yang dapat menentukan jawaban dalam jumlah langkah yang terbatas.

Jumlah langkah dalam kasus 1 sepele pasti hanya mengembalikan 1.

Dalam kasus 2 jumlah langkah juga terbatas. Untuk setiap bilangan bulat kita dapat membuat mesin Turing yang menerima jika dan sebaliknya menolak dalam waktu yang terbatas. Jadi tidak mengetahui batas atas pada tidak masalah. Untuk setiap ada mesin Turing, yaitu , yang menghitung dengan benar apakah (kita tidak tahu mana yang benar, tetapi tidak masalah, ada satu).T N ( n ) n < N N N T N ( n ) n < $N$$T_N(n)$$n < N$$N$$N$$T_N(n)$$n < N$

Meskipun mungkin tidak mungkin untuk memilih di antara kedua kasus (meskipun satu tampaknya lebih mungkin daripada yang lain), kita tahu bahwa salah satu dari mereka harus benar.

Sebagai catatan tambahan: solusi kami mengandaikan bahwa sementara kami tidak dapat menentukan fungsi mana yang akan menghasilkan nilai yang benar, esensi dari komputabilitas tidak bergantung pada konstrukabilitas bukti. Keberadaan murni sudah cukup.

Langkah 5 dari upaya pembuktian berikut tidak dapat dibenarkan, dan ternyata salah - contoh tandingan dapat ditemukan di sini . (terima kasih, Yuval; itu memang terasa seperti bagian sketsa yang paling sketsa). Saya telah meninggalkan jawabannya di sini karena saya pikir kesalahan itu bersifat instruktif.

Pertama: Sepasang jawaban JeffE sudah cukup; f dapat dihitung dengan cara apa pun.

Jalan memutar singkat, ke dalam upaya sketsa bukti dengan induksi:
Premis R : tidak mengulangi. 1. Lihat di basis 2. Ini sebagian besar untuk mengurangi jumlah kasus. 2. Tidak peduli seberapa jauh ke bawah garis Anda pergi, Anda akan selalu menemukan lain 1 tempat: alternatifnya adalah semua nol, yang berarti mulai mengulang, yang bertentangan R . 3. Sama berlaku untuk turun baris dan menemukan 0 . 4. Perluas urutan dua digit: Anda tidak dapat berhenti menemukan 01 atau 10 (yaitu, tempat di mana ia beralih), karena jika tidakπ π π $\pi$
$\pi$
$\pi$

$\pi$ akan mulai mengulangi pada 1 atau 0 . Demikian pula, Anda tidak dapat berhenti menemukan 11 atau 00 , karena jika tidak, ia mulai berulang pada 1010101 ...
5. Langkah induktif: setiap urutan hingga harus muncul jumlah kali yang tak terbatas, karena alternatifnya adalah mulai mengulangi pada salah satu urutan yang lebih pendek, yang bertentangan R .$\pi$