Kompleksitas Kolmogorov: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Hidayatsrf (bicara | kontrib) Tidak ada ringkasan suntingan |
Hidayatsrf (bicara | kontrib) |
||
| Baris 4: | Baris 4: | ||
Dalam [[teori informasi algoritmik]] (subbidang dari [[ilmu komputer]] dan [[matematika]]), '''Kompleksitas Kolmogorov''' dari sebuah objek (misalnya sepotong teks), adalah panjang dari [[program komputer]] terpendek (dalam [[bahasa pemrograman]] yang telah ditentukan) yang menghasilkan objek sebagai keluaran. Kompleksitas ini adalah ukuran dari [[perhitungan]] sumber daya yang dibutuhkan untuk menentukan objek, dan juga dikenal sebagai kompleksitas deskriptif ''Kolmogorov - [[Gregory Chaitin|Chaitin]]'', '''entropi algoritmik''', atau '''kompleksitas ukuran program'''. Istilah ini dinamai sesuai [[Andrey Kolmogorov]], yang pertama kali menerbitkan tulisan terkait subjek ini pada tahun 1963.<ref>{{cite journal|authorlink=Andrey Kolmogorov|first=Andrey|last=Kolmogorov|year=1963|title=On Tables of Random Numbers| journal=[[Sankhya (journal)|Sankhyā]] Ser. A.|volume=25|pages=369–375|mr=178484}}</ref><ref>{{cite journal|authorlink=Andrey Kolmogorov|first=Andrey|last=Kolmogorov|year=1998|title=On Tables of Random Numbers| journal=Theoretical Computer Science|volume=207|issue=2|pages=387–395|doi=10.1016/S0304-3975(98)00075-9 |mr=1643414}}</ref> |
Dalam [[teori informasi algoritmik]] (subbidang dari [[ilmu komputer]] dan [[matematika]]), '''Kompleksitas Kolmogorov''' dari sebuah objek (misalnya sepotong teks), adalah panjang dari [[program komputer]] terpendek (dalam [[bahasa pemrograman]] yang telah ditentukan) yang menghasilkan objek sebagai keluaran. Kompleksitas ini adalah ukuran dari [[perhitungan]] sumber daya yang dibutuhkan untuk menentukan objek, dan juga dikenal sebagai kompleksitas deskriptif ''Kolmogorov - [[Gregory Chaitin|Chaitin]]'', '''entropi algoritmik''', atau '''kompleksitas ukuran program'''. Istilah ini dinamai sesuai [[Andrey Kolmogorov]], yang pertama kali menerbitkan tulisan terkait subjek ini pada tahun 1963.<ref>{{cite journal|authorlink=Andrey Kolmogorov|first=Andrey|last=Kolmogorov|year=1963|title=On Tables of Random Numbers| journal=[[Sankhya (journal)|Sankhyā]] Ser. A.|volume=25|pages=369–375|mr=178484}}</ref><ref>{{cite journal|authorlink=Andrey Kolmogorov|first=Andrey|last=Kolmogorov|year=1998|title=On Tables of Random Numbers| journal=Theoretical Computer Science|volume=207|issue=2|pages=387–395|doi=10.1016/S0304-3975(98)00075-9 |mr=1643414}}</ref> |
||
Gagasan tentang kompleksitas Kolmogorov dapat digunakan untuk menyatakan dan [[Bukti ketidakmungkinan|membuktikan kemustahilan]] sama dengan [[argumen diagonal Cantor]], [[Teorema ketidaklengkapan Gödel]], dan [[masalah terputus|masalah terputus Turing]]. Secara khusus, tidak ada satu pun program ''P'' yang bisa menghitung batas bawah untuk setiap kompleksitas Kolmogorov teks yang dapat mengembalikan nilai yang pada dasarnya lebih besar dari panjang ''P'' sendiri |
Gagasan tentang kompleksitas Kolmogorov dapat digunakan untuk menyatakan dan [[Bukti ketidakmungkinan|membuktikan kemustahilan]] sama dengan [[argumen diagonal Cantor]], [[Teorema ketidaklengkapan Gödel]], dan [[masalah terputus|masalah terputus Turing]]. Secara khusus, tidak ada satu pun program ''P'' yang bisa menghitung batas bawah untuk setiap kompleksitas Kolmogorov teks yang dapat mengembalikan nilai yang pada dasarnya lebih besar dari panjang ''P'' sendiri; karenanya tidak ada satu program pun yang dapat menghitung kompleksitas Kolmogorov secara tepat untuk banyak teks yang tak terhingga. |
||
== Referensi == |
== Referensi == |
||
Revisi per 21 Mei 2021 04.37
Dalam teori informasi algoritmik (subbidang dari ilmu komputer dan matematika), Kompleksitas Kolmogorov dari sebuah objek (misalnya sepotong teks), adalah panjang dari program komputer terpendek (dalam bahasa pemrograman yang telah ditentukan) yang menghasilkan objek sebagai keluaran. Kompleksitas ini adalah ukuran dari perhitungan sumber daya yang dibutuhkan untuk menentukan objek, dan juga dikenal sebagai kompleksitas deskriptif Kolmogorov - Chaitin, entropi algoritmik, atau kompleksitas ukuran program. Istilah ini dinamai sesuai Andrey Kolmogorov, yang pertama kali menerbitkan tulisan terkait subjek ini pada tahun 1963.[1][2]
Gagasan tentang kompleksitas Kolmogorov dapat digunakan untuk menyatakan dan membuktikan kemustahilan sama dengan argumen diagonal Cantor, Teorema ketidaklengkapan Gödel, dan masalah terputus Turing. Secara khusus, tidak ada satu pun program P yang bisa menghitung batas bawah untuk setiap kompleksitas Kolmogorov teks yang dapat mengembalikan nilai yang pada dasarnya lebih besar dari panjang P sendiri; karenanya tidak ada satu program pun yang dapat menghitung kompleksitas Kolmogorov secara tepat untuk banyak teks yang tak terhingga.
Referensi
- ^ Kolmogorov, Andrey (1963). "On Tables of Random Numbers". Sankhyā Ser. A. 25: 369–375. MR 0178484.
- ^ Kolmogorov, Andrey (1998). "On Tables of Random Numbers". Theoretical Computer Science. 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR 1643414.
Pranala luar
- The Legacy of Andrei Nikolaevich Kolmogorov
- Chaitin's online publications
- Solomonoff's IDSIA page
- Generalizations of algorithmic information by J. Schmidhuber
- Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997.
- Tromp's lambda calculus computer model offers a concrete definition of K()
- Universal AI based on Kolmogorov Complexity ISBN 3-540-22139-5 by M. Hutter: ISBN 3-540-22139-5
- David Dowe's Minimum Message Length (MML) and Occam's razor pages.
- P. Grunwald, M. A. Pitt and I. J. Myung (ed.), Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0-262-07262-9.