(Salah?) Bukti untuk kemampuan komputasi suatu fungsi?

19

Pertimbangkan , fungsi yang mengembalikan 1 iff nol muncul berurutan di . Sekarang seseorang memberi saya bukti bahwa dapat dihitung: $f(n)$ $n$ $\pi$ $f(n)$

Baik untuk semua n, muncul di , atau ada st muncul di dan tidak. Untuk kemungkinan pertama ; Untuk yang kedua iff , 0 sebaliknya. $0^n$ $\pi$ $0^m$ $\pi$ $0^{m+1}$ $f(n) := 1$ $f(n) := 1$ $n \leq m$

Penulis mengklaim bahwa ini membuktikan kemampuan komputasi , karena ada algoritma untuk menghitungnya. $f(n)$

Apakah bukti ini benar?

computability Mike B.
sumber

2

Anda dapat menggunakan lateks dalam pertanyaan Anda untuk membuatnya lebih mudah dibaca.

Dave Clarke

7

Argumennya benar, tetapi tidak konstruktif. Orang itu tidak memberi Anda TM, ia memberi Anda dua TM dan memberi tahu Anda bahwa salah satunya menghitung fungsi yang Anda inginkan, tetapi tidak tahu yang mana.

Kaveh

1

Versi Anda dapat dihitung. Namun, saya salah membaca dan tidak sengaja menemukan versi yang saya percaya tidak dapat dihitung. Satu-satunya perubahan: alih-alih tepatnya n nol, tanyakan apakah π memiliki paling banyak n nol. Jika benar, saya yakin Anda tidak dapat mengkonfirmasinya, karena π memiliki jumlah digit tak terbatas dan tampaknya tidak ada pola yang muncul kembali.

chazisop

Saya mengoreksi halaman Wikipedia yang pernah membuat kesalahan terkait, menyatakan bahwa keberadaan konstanta Chaitin membuktikan keberadaan "integer yang tidak dapat dihitung".

Geoffrey Irving

jenis pertanyaan ini cenderung pada "bahasa sepele". tetapi perhatikan bagaimana biasanya sedikit reformulasi misalnya di mana bahasanya adalah mana adalah (atau ke-1) lokasi dari string atau -1 jika tidak ada string seperti itu dapat diputuskan. lihat juga bagaimana bisa diputuskan bahwa memiliki beberapa urutan digit? / Ilmu Komputer

f (n, k) = m

$f(n, k) = m$

m

$m$

0^{k}

$0^k$

π

$\pi$

vzn

23

Pikirkan seperti ini, Mike: Bukti ini "bercabang" menjadi beberapa kasus yang mungkin, salah satunya harus benar (menggunakan hukum tengah yang dikecualikan bahwa untuk setiap proposisi , baik benar atau benar). Tetapi pada akhir setiap cabang ini, Anda selalu berhasil membuktikan bahwa fungsi dapat dihitung. Oleh karena itu, tidak peduli kasus mana yang benar-benar terjadi dalam kehidupan nyata, harus dapat dihitung. (Namun, alasan pasti mengapa dapat dihitung akan berbeda, tergantung pada cabang.) $p$ $p$ $\neg p$ $f$ $f$ $f$

Ryan Williams
sumber

16

Itu benar. Ini sama dengan yang berikut ini: definisikan sebagai fungsi konstan jika Tuhan ada, dan jika Tuhan tidak ada. Fungsi yang dihasilkan adalah fungsi konstan, sehingga dapat dihitung. Apa yang Anda mungkin tidak bisa lakukan adalah memberikan fungsi itu, tetapi fungsi itu sendiri dapat dihitung. $f(x)$ $x \mapsto 0$ $x \mapsto 1$

Di sini, salah satu dari dua kemungkinan itu benar: apakah ada seperti itu , atau tidak. Fungsi tersebut adalah fungsi konstan atau fungsi ambang sederhana, didefinisikan dengan . $m$ $x \mapsto 1$ $m$

Michaël Cadilhac
sumber

4

Saya akan menggantikan "jika Tuhan itu ada" dengan

. :)

P \neq N P

$P \neq NP$

Kaveh

Ok, maaf atas kesalahpahaman, saya tidak mengalami masalah dengan non-konstruktif buktinya. Masalah yang saya miliki adalah, bahwa kita (atau setidaknya saya) tidak tahu apakah

dapat dihitung atau tidak. Mengapa tidak perlu membuktikan itu?

m

$m$

Mike B.

5

Tidak masuk akal untuk berbicara tentang apakah integer dapat dihitung atau tidak. Apa pun nilai yang saya ambil, ada mesin Turing yang mengeluarkannya. Menemukannya mungkin sulit tentu saja, tetapi ini tidak begitu berbeda dari situasi umum: menemukan algoritma itu sulit, yang merupakan fakta yang membuat banyak dari kita bekerja.

Aaron Roth

Saya masih belum mengerti. Mesin Turing apa yang mungkin menghasilkan output ini? Bukan hanya akan itu harus menunjukkan bahwa

muncul dalam

, lebih dari itu harus memverifikasi bahwa

tidak - dan itu adalah IMO masalah.

0^{m}

$0^m$

π

$\pi$

0^{m + 1}

$0^{m+1}$

Mike B.

Ini adalah cara konstruktif yang Anda bicarakan. Jika saya memberi Anda sebuah mesin yang output seperti

, tidak perlu meyakinkan Anda bahwa ini adalah hak

, karena yang mesin untuk outputing seperti

(baik, sebuah mesin setidaknya). Ini sama dengan contoh Tuhan (yang berasal dari Sipser BTW): jika mesin menghasilkan

, tidak perlu meyakinkan Anda bahwa Tuhan tidak ada. Itu hanya masalahnya.

m

$m$

m

$m$

m

$m$

0

$0$

Michaël Cadilhac

14

Saya pikir - dan berharap - bahwa setiap mahasiswa ilmu komputer dihadapkan dengan masalah ini yang terasa seperti paradoks. Ini adalah contoh yang sangat bagus untuk perbedaan komputasi dalam arti TCS dan komputasi dalam arti praktis.

$\pi$ $\pi$

$f$ $\exists M \in TM : f_M = f$

Ide dasar dari buktinya adalah: Saya memberi Anda kelas fungsi yang tak terbatas, semuanya dapat dihitung (untuk ditunjukkan; sepele di sini). Saya membuktikan kemudian bahwa fungsi yang Anda cari ada di kelas itu (untuk menunjukkan; perbedaan huruf di sini). qed

Raphael
sumber

9

Ya itu benar, itu bisa dihitung. Masalahnya adalah bahwa fungsi Anda benar-benar tidak menghasilkan solusi untuk keluarga masalah yang tak terbatas, cara (katakanlah) fungsi menghitung solusi untuk masalah penghentian adalah - jadi tidak ada masalah tentang perhitungan. Sebagai gantinya, Anda mewakili dalam bentuk-fungsi beberapa fakta matematika tunggal dengan representasi terbatas - baik bilangan bulat, atau fakta bahwa f adalah fungsi 1 yang konstan

$\Omega$

Menemukan algoritma yang benar tentu saja mungkin merupakan masalah yang sulit. Tetapi menemukan algoritma yang benar biasanya sulit!

Aaron Roth
sumber

3

posting agak lama, tetapi ingin memposting jawaban lain.

Ini adalah bukti (atau argumen) komputabilitas yang tidak konstruktif . Ini hanya mengatakan bahwa fungsi tersebut harus ada dalam beberapa hal karena saya dapat mewakilinya (atau lebih tepatnya mengindeksnya), dalam himpunan (atau semesta) dari fungsi yang dapat dihitung. Namun itu tidak membangun mesin itu sendiri (yaitu algoritma), atau indeks (dengan asumsi penghitungan yang efektif dari mesin yang dapat dihitung). Ungkapan bahasa Inggris " thanks for nothing ", tampaknya dalam kasus ini paling tepat, seperti yang berikut:

-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!

Orang-orang dalam sejarah matematika berpendapat sedikit tentang validitas aktual (atau kisaran validitas) dan makna argumen tersebut. Hasil akhirnya adalah bahwa jenis argumen yang sama muncul kembali dalam teorema ketidaklengkapan Goedel dan berbalik melawan "asumsi alam semesta tertutup" ini .

Jika Anda sangat tidak menyukai argumen ini, saya tidak akan menyalahkan Anda.

Nikos M.
sumber

(Salah?) Bukti untuk kemampuan komputasi suatu fungsi?

Jawaban: