Apa contoh masalah bisnis yang mustahil secara komputasi?

Saya memiliki rekan kerja yang menolak untuk menerima kenyataan bahwa mesin Turing (dan mesin Von Neuman dengan ekstensi) tidak dapat memecahkan masalah mereka sendiri yang menyatakan:

Anda dapat melakukan apa saja dengan cukup waktu dan uang.

Dia juga tidak suka masalah teoritis dengan alasan bahwa:

Di bidang kami, kami tidak akan pernah mengalami pertanyaan itu. Kami pengembang aplikasi, bukan ilmuwan teoretis.

Apakah ada contoh yang baik dari masalah bisnis yang secara komputasi tidak mungkin saya dapat gunakan untuk membantu meyakinkannya tentang hal ini?

Secara teknis tidak mungkin, tapi ...

Sumber daya penjadwalan , dengan tujuan menemukan jadwal ideal yang memaksimalkan penggunaan slot waktu. Saya pernah mengerjakan sebuah proyek, pada hari-hari komputasi saya sebelumnya, yang memiliki persyaratan ini. Saya mengerjakannya beberapa saat sebelum saya menyadari bahwa itu NP-keras.

Contoh masalah lain yang secara teknis tidak mungkin, tetapi secara teknis sulit, dapat ditemukan di sini .

Sebagian besar masalah komputasi yang sulit dalam komputasi bisnis bukan tidak mungkin, hanya tidak praktis. Temanmu benar; Anda dapat memecahkan sebagian besar dari mereka jika Anda memberikan cukup uang kepada mereka. Namun argumen itu tidak masuk akal; Inti menjalankan bisnis adalah menghasilkan uang, bukan kehilangannya.

Dalam praktik sehari-hari, kita berbicara tentang kelengkapan Turing dengan cara yang tidak jelas, bukan untuk menunjukkan beberapa prinsip matematika, tetapi untuk mengilustrasikan (misalnya) ketidakcukupan HTML dan CSS sebagai sarana lengkap untuk memproduksi program fitur-lengkap.

Demikian pula, Masalah Pemutusan penting bagi ahli teori, tetapi tidak memiliki banyak relevansi dengan sebagian besar bisnis.

Yang lain mengomentari ini, tetapi saya akan mencoba menuliskan jawaban yang memberikan sudut pandang saya.

Saya suka Robert Harvey menjawab, dan komentar untuk jawabannya, dan saya ingin memperluas itu.

Saya pikir Anda harus menyajikan masalah yang tidak dapat dipastikan ini (seperti pemutusan hubungan kerja) dengan cara biasa: misalnya, alat IDE yang "memeriksa apakah fungsi ini selalu mengembalikan nilai".

Saat mengajar, contoh favorit saya adalah refactoring ( kesetaraan fungsi, masalah lain yang tidak dapat dipastikan ). Saya bertanya:

bagaimana Anda memeriksa apakah suatu fungsi / program melakukan hal yang sama setelah Anda refactoring bagus? Tentu, kami memiliki unit test untuk itu, tetapi mereka tidak mencakup semua kasing. Dan mereka bosan menulis ... Tapi kita adalah programmer! Kita harus menulis sebuah program yang memeriksa apakah kedua fungsi ini menghasilkan hasil yang selalu sama! Mengapa Anda tidak mencoba menulisnya?

atau, sebagai variasi, mungkin lebih dekat dengan kasus Anda:

Kami memiliki kode warisan ini ditulis dalam dialek COBOL kuno yang tidak diketahui, yang tidak memiliki spesifikasi dan / atau kompiler. Kami hanya punya program. Seluruh bisnis kami bergantung padanya, jadi kami harus 100% yakin kode Java yang baru melakukan hal yang persis sama dalam setiap situasi. Manajemen menginginkan program yang melakukan itu, memeriksa semua kasus yang mungkin, dan memperkirakannya dapat dilakukan dalam 6 hingga 8 minggu. Mengapa Anda tidak mencoba menulisnya?

Intinya bukan untuk menulis program seperti itu. Atau perkiraan yang cukup baik dari persyaratan. Intinya adalah untuk menyadari bahwa itu TIDAK dapat dilakukan dengan cara langsung, JANGAN sia-siakan usaha kita untuk mencari cara melakukannya (hanya untuk menyadari bahwa itu tidak mungkin), tetapi kenali itu. "Ah! Ini tidak bisa dipastikan! Tidak mungkin melakukannya secara langsung. Aku harus mencari cara lain yang lebih pintar untuk melakukannya, dengan perkiraan yang cukup baik".

Anda harus mencari cara untuk menyajikan masalah dengan cara yang mudah dikenali, dan tampaknya sederhana. Anda tidak akan percaya berapa banyak siswa CS yang akan mencoba untuk menulis program seperti itu secara langsung ... sebelum mengambil kelas komputasi :)

Dengan asumsi kita dapat mengesampingkan pertanyaan moral untuk saat ini:

Bisnis A telah mengontrak Anda untuk cara berkomunikasi antara kantor satelit A1 dan A2 tanpa siapa pun selain orang yang berwenang di A1 dan A2 yang dapat memahami komunikasi tersebut.

Bisnis B telah mengontrak Anda untuk cara menguping secara cerdas semua komunikasi antara A1 dan A2.

Jelas Anda tidak bisa melakukan keduanya.

Karena cara matematika bekerja (matematika yang tepat telah menjadi subjek penelitian yang sedang berlangsung selama 100 tahun), salah satu dari persyaratan berikut tidak dapat dipenuhi:

(1): Memberikan algoritma enkripsi yang tidak dapat dipecah oleh penyerang dengan jumlah uang sewenang-wenang yang tersedia.

(2): Menyediakan algoritma pemecahan enkripsi untuk algoritma enkripsi sewenang-wenang yang berjalan dalam waktu yang wajar.

Saya baru saja mengambil kelas tentang Model Proses Bisnis dan Notasi ( BPMN ). Di sana dapat dengan mudah dilihat bahwa alur kerja dengan terlalu banyak pemisahan, sambungan, dan putaran menjadi cepat tidak praktis (meskipun tidak selalu mustahil , AFAIK) untuk dipahami dan dikendalikan, (ketika Anda menggunakan terlalu banyak OR-split bukannya XOR-splits).

Untuk industri perangkat lunak, saya pikir hal yang sama berlaku untuk masalah serupa "cakupan beberapa kondisi" dalam analisis cakupan kode .

Untuk bisnis, cara yang harus ditempuh adalah mengecilkan ruang masalah, dan tidak membuang lebih banyak sumber daya pada masalah yang kompleks. Dalam contoh saya, tambahkan kendala pada alur kerja, (atau dalam analisis cakupan kode, sederhanakan kode), alih-alih bekerja keras untuk menemukan semua, katakanlah, N jejak yang mungkin dan hasil di mana N adalah jumlah yang sangat besar.

Selain itu saya pikir ada banyak masalah dalam analisis jaringan / grafik yang tidak mungkin untuk dipecahkan (mencoba menentukan topologi jaringan dengan secara iteratif berjalan di semua jalur dll).

Contoh klasik sedang mencoba mem - parsing HTML dengan ekspresi reguler . Ini dapat bekerja dengan himpunan HTML terbatas tetapi solusi umum tidak mungkin, karena fakta bahwa mereka memiliki tata bahasa Chomsky yang berbeda (karena tautannya memperjelas (ish)).

Secara umum, beberapa orang tidak suka berpikir secara filosofis (seperti rekan kerja Anda) dan saya tidak yakin Anda bisa membantah jalan keluar dari pola pikir Anda. Poin pertamanya jelas salah, tetapi yang kedua mungkin hanya cara mengatakan saya tidak perlu khawatir tentang hal ini untuk kode formulir web untuk barang yang diterima. Saya punya simpati dengan ini, tetapi kadang-kadang mengetahui teorinya berarti Anda tidak berkomitmen untuk menemukan Holy Grail di waktu kerja.

Mungkin jawabannya adalah rekan kerja Anda benar. Mungkin Anda salah mengerti Turing, atau bagaimana penerapannya di sini?

Semua mesin terbatas, oleh karena itu tidak ada mesin Turing 'nyata' dan tidak ada program yang tidak akan pernah berhenti. Program sepele yang mengeksekusi loop infinite sederhana dapat berjalan 5 menit atau 50 tahun tetapi pada mesin yang terbatas itu akan berhenti. Masalah non-sepele yang non-sepele seperti 'menghitung pi dengan tepat' juga akan berhenti, karena pada akhirnya perhitungan akan melebihi kapasitas untuk menyimpan angka lebih lanjut.

Hasil Turing tidak menjamin apa pun yang sangat berguna pada mesin yang terbatas, sehingga pencarian Anda pada akhirnya tidak membuahkan hasil. Lebih baik fokus pada berapa banyak waktu dan berapa banyak uang dan biarkan tak terhingga bagi para matematikawan.

Anda mungkin berpikir bahwa program seperti { while true: print "running"; print "halted"; }adalah contoh tandingan tetapi tidak. Program ini memiliki efek samping, yang mungkin atau tidak dapat menghentikannya. Mengabaikan efek samping, adalah mungkin untuk menemukan bukti formal bahwa program ini tidak akan berhenti. Dalam pertanyaan ini kami hanya memusatkan perhatian pada program-program yang menghindari bukti formal tidak berhenti, di mana pertanyaan berhenti tidak dapat diputuskan. Ini bukan program seperti itu.

Mungkin membantu membedakan Turing 'kuat' dari Turing 'lemah'. Mesin Turing yang kuat sebenarnya tak terbatas dan jika gagal berhenti, akan berjalan untuk waktu yang tak terbatas. Kita tidak bisa membangun itu.

Mesin Turing yang lemah memiliki batas waktu dan ruang yang terbatas, dan mereka adalah satu-satunya jenis yang dapat kita bangun. Kami tertarik pada program yang tidak dapat dibuktikan berhenti dalam batas-batas itu. Turing memberi tahu kami bahwa ada program semacam itu tetapi kami tidak dapat mengidentifikasi mereka. Jika batasnya cukup rendah, kami dapat mengidentifikasinya dengan menulis program dan menjalankannya hingga batasnya.

Inti dari Turing adalah tidak ada jalan pintas. Satu-satunya cara untuk memastikan apakah suatu masalah layak secara komputasi adalah dengan menulis program, menjalankannya, dan mencari tahu. Dengan waktu dan uang yang cukup, Anda dapat menulis semua program, menjalankannya selamanya dan seiring waktu, dan menemukan program yang menghasilkan hasil (penghalang). Yang lain masih akan berjalan. Apakah Anda rekan kerja punya cukup waktu dan uang untuk melakukan itu?

Namun serius, perselisihan adalah tentang batasan. Turing dan NP selesai memberi tahu kami bahwa kelas masalah tertentu tidak dapat diselesaikan oleh komputer dalam anggaran apa pun atau pada jadwal apa pun, tidak peduli seberapa besar anggaran itu atau seberapa murahnya jadwal itu. Contoh-contoh masalah semacam itu berlimpah: putus kunci kriptografi; mengoptimalkan rute untuk melakukan pengiriman ke ratusan alamat; kotak kemasan di truk; menemukan bug dalam program besar!

Jadi mintalah rekan kerja Anda anggaran dan jadwal, dan buat janji bahwa Anda dapat menghasilkan masalah yang tidak dapat diselesaikan dalam anggaran atau jadwal itu. Janji itu akan sangat mudah untuk ditepati.