Mengapa manusia dapat memecahkan masalah "tidak dapat dipastikan" tertentu?

Pencocokan pola tingkat tinggi adalah masalah yang tidak dapat ditentukan. Itu berarti tidak ada algoritma yang, diberikan persamaan a => b, di mana adan badalah istilah terbuka pada kalkulus lambda yang diketik sederhana, menemukan substitusi Ssehingga aS => bS, di mana =>singkatan "memiliki bentuk normal Bn yang sama". Namun, manusia dapat menyelesaikan masalah itu secara efisien. Misalnya, diberikan masalah berikut:

a = (λt . t 
    (F (λ f x . (f (f (f x))))) 
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

Setiap manusia dengan pengetahuan yang cukup tentang kalkulus lambda akan dapat memperhatikan Fadalah fungsi "ganda" untuk jumlah gereja, dengan cepat datang dengan solusi yang

 F = (λ a b c . (a b (a b c)))

Pertanyaan saya adalah: jika masalah itu tidak dapat dipastikan, bagaimana manusia dapat dengan cepat dan mudah menyelesaikannya?

computability Viktor Maia
sumber

"manusia dapat menyelesaikan masalah itu secara efisien" - kutipan diperlukan. Apa buktimu untuk itu? Menampilkan satu contoh di mana Anda dapat menyelesaikannya secara efisien tidak berarti Anda dapat menyelesaikannya secara efisien untuk semua contoh masalah. Anda tidak dapat membuktikan "X benar, untuk semua X" dengan menunjukkan satu contoh X di mana X benar.

Masalah tidak dapat dipastikan artinya tidak ada algoritma yang menjawab dengan benar "ya" atau "tidak" untuk setiap contoh masalah. Itu tidak menyiratkan bahwa seseorang dapat menemukan algoritma yang memecahkan beberapa (atau banyak) contoh masalah. [Heh. Ketika DW menjawab ketika saya sedang menyusun komentar ini.]

Rick Decker

Selesaikan masalah ini? Saya bahkan tidak mengerti masalah ini.

MikeTheLiar

Cara saya memahaminya adalah ini: Solusi itu adalah solusi ad hoc. Setiap instance dari masalah memiliki satu - dalam banyak kasus tidak semudah termotivasi seperti dalam contoh Anda, tetapi Anda selalu dapat mengatakan 'jika Anda mendapatkan instance X, output Y' karena suatu algoritma dapat dinilai hanya berdasarkan kebenaran - tetapi mengkode semua solusi dengan cara ini tidak menghasilkan prosedur yang terbatas (yang merupakan satu-satunya jenis yang masuk akal dan dengan demikian apa yang biasanya dimaksud). Sebagai alternatif, agar masalah dapat diputuskan, Anda tidak diizinkan untuk melihat instance mana yang diberikan sebelum memilih strategi algoritma.

Vandermonde

Juga, inilah sebabnya mengapa hanya masalah dengan jumlah instance yang tak terbatas yang secara umum dianggap atau disebut demikian, karena Anda bisa saja menyebutkan semua solusi seperti di atas.

Vandermonde

Jawaban:

Manusia dapat menyelesaikan beberapa contoh dari masalah itu secara efisien, tetapi tidak ada alasan untuk percaya bahwa manusia dapat menyelesaikan semua kejadian secara efisien. Menunjukkan satu contoh yang dapat diselesaikan manusia dengan efisien tidak berarti bahwa manusia dapat menyelesaikan semua kejadian secara efisien.

Tidak dapat ditentukan berarti "tidak ada algoritma yang dapat menyelesaikan semua instance dan yang selalu berakhir". Mungkin masih ada algoritme yang dapat memecahkan beberapa kasus , bahkan untuk masalah yang tidak dapat ditentukan .

Jadi tidak ada kontradiksi.

DW
sumber

@ RSVM, ya, itu memang berarti itu. Sebagai contoh, berikut adalah contoh bodoh dari algoritma komputer: "jika inputnya persis seperti contoh yang diberikan dalam pertanyaan Anda, maka output F = (λ a b c . (a b (a b c)))dan hentikan". Itu adalah algoritma komputer yang memecahkan masalah untuk beberapa kasus (khususnya, untuk tepat 1 kasus). Ya, tidak apa-apa - mengajukan pertanyaan baru seperti itu sepertinya hal yang tepat untuk dilakukan. Seperti biasa, tolong beri tahu kami penelitian apa yang telah Anda lakukan dalam pertanyaan (Anda harus melakukan beberapa sebelum bertanya).

Dimana Masalah yang Benar - Benar Sulit mengklaim bahwa bahkan dalam masalah lengkap NP sebagian besar kasus dapat diselesaikan dengan mudah. Ini cocok dengan pengalaman saya. Biasanya ada fitur masalah yang membuat (setidaknya bagian dari) solusinya jelas. Yang sulit diseimbangkan antara sukses dan gagal, tetapi jumlahnya tidak banyak.

Ross Millikan

@ srvm jika Anda memikirkannya, menyelesaikan masalah sulit seperti ini dalam kasus khusus adalah persis apa yang harus dilakukan pengoptimal.

Cort Ammon

@ srvm: Contoh yang sangat bagus dari masalah yang tidak dapat diputuskan yang membuat komputer memecahkan hampir setiap hari adalah masalah penghentian. Kita tahu bahwa masalah penghentian tidak dapat diputuskan, tetapi kita masih tetap menulis kertas, analisis statis, dan kompiler yang mencoba mendeteksi loop tak terbatas yang tidak diinginkan. Cara kami melakukannya adalah dengan "aturan praktis". Yaitu, kita tahu dari pengalaman manusia (bukan algoritma) bahwa jenis kode tertentu memasuki infinite loop. Jadi kami meminta komputer untuk mencari kasing yang kami tahu. Kami tahu bahwa program semacam itu tidak akan pernah menangkap semua bug. Tapi itu lebih baik daripada tidak sama sekali.

Slebetman

untuk anak cucu, tautan baru ke: Di mana Masalah yang Sungguh Sulit

Alex Moore-Niemi

Seperti yang dicatat oleh salah satu komentar, orang harus sadar bahwa ada beberapa algoritma yang cukup bagus untuk menyelesaikan Pencocokan Pola Pesanan Tinggi dalam praktiknya (seperti pencarian cepat google akan mengungkapkan).

Saya tidak tahu ada yang memecahkan masalah khusus ini, tetapi masalah "penggandaan" ini terasa lebih dekat dengan bidang sintesis program . Saya percaya bahwa ada sistem sintesis program yang dapat mengatasi masalah semacam ini.

Sangat mudah untuk membuat contoh yang membuat sistem tersebut tersedak, dan tampaknya manusia sangat pandai dalam masalah-masalah seperti ini. Menciptakan algoritma yang lebih dekat dengan manusia dalam kemampuan mereka untuk memecahkan masalah-masalah semacam ini adalah bidang pembuktian teorema otomatis dan kecerdasan buatan (untuk upaya yang lebih ambisius / tidak realistis).

cody
sumber

Manusia selalu berusaha memecahkan masalah dengan pengetahuan mereka sendiri, sehingga manusia mengembangkan beberapa algoritma untuk memecahkan masalah dengan beberapa contoh masalah. Jadi manusia mengembangkan suatu algoritma, tetapi tidak ada jaminan bahwa algoritma tertentu dapat menyelesaikan setiap masalah. Jadi tidak ada algoritma yang dapat menyelesaikan setiap masalah, tetapi masih ada beberapa masalah yang dapat diselesaikan oleh manusia meskipun tidak ada algoritma yang sempurna untuk itu seperti kita dapat mengatakan bahwa kita tahu bagaimana menyelesaikan masalah tetapi kita tidak memiliki algoritma .

sumber

Bukankah ini hanya parafrase dari jawaban yang ada? Saya tahu saya telah mengkritik sebagian besar jawaban Anda sehingga yang berikut ini mungkin terdengar tidak tulus, tetapi ternyata tidak. Sungguh luar biasa bahwa Anda ingin berkontribusi ke situs. Akan sangat bagus jika Anda dapat membantu kami menjawab beberapa dari 2.500 pertanyaan yang belum terjawab , alih-alih pertanyaan di mana kami sudah memiliki jawaban yang mengatakan semua yang ingin Anda katakan. Terima kasih!

David Richerby