Untuk menjawab "masalah apa yang dapat diselesaikan dengan komputasi", kami mengembangkan teori komputabilitas. Untuk masalah yang dapat dihitung, apakah ada teori untuk menjawab pertanyaan "apakah program yang saya dapatkan paling sederhana"?
Saya tidak berpikir kompleksitas komputasi menjawab pertanyaan itu. Saya pikir itu mempertimbangkan berapa lama kita perlu (meskipun diukur secara abstrak).
Saya tidak yakin apakah teori informasi algoritmik menjawab pertanyaan. Tampaknya teori berbicara tentang ukuran, di mana kesetaraan ukuran minimal dan paling sederhana tidak jelas bagi saya (well, setidaknya mereka merasa berbeda dengan saya).
Saya pikir teori setidaknya harus mendefinisikan hubungan "sederhana" atau "lebih sederhana dari".
Saya sekarang yakin bahwa saya harus melihat ke Kompleksitas Kolmogorov. Namun, saya ingin menjelaskan apa yang ada dalam pikiran saya ketika saya mengajukan pertanyaan.
Ketika saya meningkatkan suatu program, saya mencoba mengurangi koneksi yang tidak perlu antara bagian-bagian berbeda dari program (mungkin membagi ulang bagian-bagian sehingga ada koneksi yang lebih sedikit atau lebih lemah). Karena koneksi berkurang, program terasa "lebih sederhana". Oleh karena itu pilihan kata "sederhana" ketika saya mengucapkan pertanyaan. Sangat mungkin ukuran program juga menurun, tetapi itu adalah efek samping yang baik, bukan tujuan utama. Jelas, proses peningkatan tidak bisa berlangsung selamanya. Ada satu hal yang harus saya hentikan. Jika, hanya dengan mempertimbangkan "struktur" (maaf untuk konsep lain yang tidak ditentukan) atau "hubungan", dapatkah saya meyakinkan diri sendiri bahwa tidak ada lagi yang bisa dilakukan?
Di sini berisi deskripsi yang lebih baik tentang pengertian saya tentang kompleksitas.
Olaf Sporns (2007) Kompleksitas . Scholarpedia , 2 (10): 1623
Jawaban:
Masalah ini dipelajari dalam Teori Informasi Algoritma. Apa yang Anda mendefinisikan disebut kompleksitas Kolmogorov-Chaitin.
http://en.wikipedia.org/wiki/Kolmogorov_complexity
Dan tampaknya gagasan kesederhanaan yang Anda butuhkan dapat diformalkan melalui gagasan ukuran kompleksitas, yang diformalkan oleh aksioma Blum.
http://en.wikipedia.org/wiki/Blum_axioms
Tampaknya juga mungkin untuk menggeneralisasi kompleksitas Kolmogorov untuk mempertimbangkan langkah-langkah kompleksitas lainnya. Lihat referensi di bawah ini. (Artikel Wikipedia tentang kompleksitas Kolmogorov membahas masalah ini.)
Burgin1990 - Kompleksitas kolmogorov umum dan langkah kompleksitas ganda lainnya Analisis Siber dan Sistem Volume 26, Nomor 4, 481-490
sumber
Jawaban untuk pertanyaan pertama adalah Ya ada teori, itu teori informasi Algoritma dan mereka disebut Program Elegan (oleh Gregory Chaitin).
Untuk pertanyaan kedua tentang "apakah program saya mendapatkan yang paling sederhana"?
Tidak ada jawaban , karena ini adalah pertanyaan yang tidak dapat dihitung, tidak mungkin membuktikan bahwa suatu program adalah program yang Elegan.
Saya telah memberikan jawaban untuk menambahkan menyebutkan tentang program elegan .
sumber
Ada berbagai jenis pendekatan untuk memutuskan kode apa yang sederhana dan mana yang tidak.
Namun sayangnya, tidak ada cara otomatis untuk menentukannya, misalnya, Kompleksitas Kolmogorov gagal dengan fungsi rekursif, beberapa fungsi rekursif (logis dalam) sederhana tetapi pemahaman tentang itu tidak begitu sederhana.
Dalam pengalaman saya, tim kami bekerja dalam suatu sistem dan kami menemukan prosedur "sederhana" di Oracle (tidak lebih dari 50 baris) ... dan kami mencoba memahaminya, butuh 2 bulan (dan beberapa pertemuan) untuk memahami sepenuhnya itu, bukan oleh kompleksitas kode tetapi dalam logika di balik setiap variabel.
Saya pikir cara untuk menentukan betapa sederhananya sebuah kode adalah: "baca kode dan pertimbangkan waktu yang digunakan untuk memahaminya."
Jadi, "Program paling sederhana untuk menyelesaikan masalah?" dapat dibagi dalam:
a) kesederhanaan kode (kode yang jelas) tetapi terlalu subyektif.
b) fungsi yang terlalu kompleks, jika saya memiliki masalah X maka saya harus menyelesaikan tugas DX (Delta X) untuk menyelesaikannya, di mana DX harus cenderung ke X.
Misalnya, jika masalah saya adalah (satu) "mengupas apel" dan saya harus melakukannya dalam PHP (dan bahasa) maka
jika saya sangat beruntung dan PHP memiliki function function_peel_apple () maka itu adalah kode paling sederhana yang pernah ada X = 1 DX = 1, panggil saja fungsinya dan itu saja !.
Sebaliknya, jika saya tidak begitu beruntung tetapi ada function function_peel () dan function_get_apple () maka X = 1 (satu masalah) dan DX = 2 (dua tugas).
Jika, dalam kasus terburuk, tidak ada fungsi apa pun, maka saya harus membuat satu (atau lebih dari satu) sendiri dan menambahkan beberapa tugas sebelum menyelesaikan masalah, sekarang itu adalah program yang kompleks.
sumber