Teori Informasi Algoritma Dalam Matematika – Teori informasi algoritmik (AIT) Merupakan cabang ilmu teoretis yang berhubungan dengan perhitungan dan generasi komputasi informasi objek (misalnya, string dan struktur data lainnya). Dengan kata lain, AIT menunjukkan bahwa inkompresibilitas komputasional “meniru” hubungan atau ketidaksetaraan yang ditemukan dalam teori informasi (kecuali untuk konstanta yang hanya bergantung pada bahasa pemrograman umum yang dipilih.
Teori Informasi Algoritma Dalam Matematika
transitionmathproject – Menurut Gregory Chaitin , itu adalah “hasil dari menempatkanTeori informasi Shannon dan teori komputabilitas Turing menjadi pengocok koktail dan gemetar dengan kuat.” Selain formalisasi ukuran universal untuk konten informasi yang tidak dapat direduksi dari objek yang dihasilkan secara komputasi, beberapa pencapaian utama AIT adalah untuk menunjukkan bahwa: sebenarnya kompleksitas algoritme mengikuti (dalam kasus yang dibatasi sendiri ).
Baca Juga : Mengulas Lebih Dalam Tentang Matematika Diskrit
Ketidaksetaraan yang sama (kecuali untuk konstanta ) bahwa entropi tidak seperti dalam teori informasi klasik; keacakan adalah inkompresibilitas; dan, dalam bidang perangkat lunak yang dihasilkan secara acak, kemungkinan terjadinya struktur data apa pun adalah urutan program terpendek yang menghasilkannya saat dijalankan pada mesin universal.
AIT pada dasarnya mempelajari ukuran konten informasi yang tidak dapat direduksi dari string (atau struktur data lainnya). Karena sebagian besar objek matematika dapat dideskripsikan dalam bentuk string, atau sebagai limit dari barisan string, maka objek tersebut dapat digunakan untuk mempelajari berbagai objek matematika, termasuk bilangan bulat . Salah satu motivasi utama di balik AIT adalah mempelajari informasi yang dibawa oleh objek matematika seperti di bidang metamatematika , misalnya, seperti yang ditunjukkan oleh hasil ketidaklengkapan yang disebutkan di bawah ini.
Motivasi utama lainnya datang dari: melampaui keterbatasan teori informasi klasik untuk objek tunggal dan tetap; memformalkan konsep keacakan; dan menemukan inferensi probabilistik yang berarti tanpa pengetahuan sebelumnya tentang distribusi probabilitas (misalnya, apakah itu independen dan terdistribusi identik , Markovian , atau bahkan stasioner). Dengan cara ini, AIT diketahui pada dasarnya didasarkan atas tiga konsep utama matematika dan hubungan di antara mereka: kompleksitas algoritmik , keacakan algoritme , dan probabilitas algoritmik.
Ikhtisar
Teori informasi algoritma pada prinsipnya mempelajari ukuran kompleksitas pada string (atau struktur data lainnya). Karena sebagian besar objek matematika dapat dideskripsikan dalam bentuk string, atau sebagai limit dari barisan string, maka objek tersebut dapat digunakan untuk mempelajari berbagai objek matematika, termasuk bilangan bulat .
Secara informal, dari sudut pandang teori informasi algoritmik, konten informasi dari string setara dengan panjang representasi mandiri string yang paling terkompresi yang mungkin. Representasi mandiri pada dasarnya adalah sebuah program — dalam beberapa bahasa pemrograman universal yang tetap tetapi tidak relevan — yang, ketika dijalankan, mengeluarkan string asli.
Dari sudut pandang ini, sebuah ensiklopedia setebal 3000 halaman sebenarnya berisi informasi yang lebih sedikit daripada 3000 halaman surat-surat yang benar-benar acak, meskipun faktanya ensiklopedia itu jauh lebih berguna. Ini karena untuk merekonstruksi seluruh urutan huruf acak, seseorang harus tahu apa itu setiap huruf. Di sisi lain, jika setiap vokal dihilangkan dari ensiklopedia, seseorang dengan pengetahuan bahasa Inggris yang memadai dapat merekonstruksinya, seperti halnya seseorang dapat merekonstruksi kalimat “Ths sntnc hs lw nfrmtn cntnt” dari konteks dan konsonan yang ada.
Tidak seperti teori informasi klasik, teori informasi algoritmik memberikan definisi formal dan ketat dari string acak dan urutan tak terbatas acak yang tidak bergantung pada intuisi fisik atau filosofis tentang nondeterminisme atau kemungkinan . (Set string acak tergantung pada pilihan mesin Turing universal yang digunakan untuk mendefinisikan kompleksitas Kolmogorov, tetapi pilihan apa pun memberikan hasil asimtotik yang identik karena kompleksitas Kolmogorov dari string adalah invarian hingga konstanta aditif bergantung hanya pada pilihan mesin Turing universal. Karena alasan ini, himpunan barisan tak hingga acak tidak bergantung pada pilihan mesin universal.)
Beberapa hasil teori informasi algoritmik, seperti teorema ketidaklengkapan Chaitin , tampaknya menantang intuisi matematika dan filosofis umum. Paling penting di antara ini adalah pembangunan konstan Chaitin ini Ω , bilangan real yang mengungkapkan probabilitas bahwa mesin Turing yang universal diri pembatasan akan menghentikan ketika input disediakan oleh membalik dari sebuah koin (kadang-kadang dianggap sebagai probabilitas bahwa acak program komputer akhirnya akan berhenti).
Meskipun Ω mudah didefinisikan, dalam setiap konsisten axiomatizable teori satu hanya dapat menghitung finitely banyak digit Ω , sehingga dalam arti diketahui, memberikan batas mutlak pada pengetahuan yang mengingatkan pada teorema ketidaklengkapan Gödel . Meskipun angka dari Ω tidak dapat ditentukan, banyak properti dari Ω diketahui; misalnya, ini adalah urutan acak algoritmik dan dengan demikian digit binernya didistribusikan secara merata (sebenarnya itu normal ).
Sejarah
Teori informasi algoritmik didirikan oleh Ray Solomonoff, yang menerbitkan ide-ide dasar yang menjadi dasar bidang tersebut sebagai bagian dari penemuannya tentang probabilitas algoritmik — cara untuk mengatasi masalah serius yang terkait dengan penerapan aturan Bayes dalam statistik. Dia pertama kali menjelaskan hasilnya pada Konferensi di Caltech pada tahun 1960, dan dalam sebuah laporan, Februari 1960, “A Preliminary Report on a General Theory of Inductive Inference.” Teori informasi algoritma kemudian dikembangkan secara mandiri oleh Andrey Kolmogorov , pada tahun 1965 dan Gregory Chaitin , sekitar tahun 1966.
Ada beberapa varian dari kompleksitas Kolmogorov atau informasi algoritmik; yang paling banyak digunakan didasarkan pada program self-delimiting dan terutama karena Leonid Levin (1974). Per Martin-Löf juga memberikan kontribusi signifikan terhadap teori informasi barisan tak hingga. Pendekatan aksiomatik untuk teori informasi algoritmik berdasarkan aksioma Blum (Blum 1967) diperkenalkan oleh Mark Burgin dalam makalah yang dipresentasikan untuk diterbitkan oleh Andrey Kolmogorov(Burgin 1982). Pendekatan aksiomatik mencakup pendekatan lain dalam teori informasi algoritmik.
Dimungkinkan untuk memperlakukan ukuran informasi algoritmik yang berbeda sebagai kasus tertentu dari ukuran informasi algoritmik yang ditentukan secara aksiomatis. Alih-alih membuktikan teorema serupa, seperti teorema invarians dasar, untuk setiap ukuran tertentu, adalah mungkin untuk dengan mudah menyimpulkan semua hasil seperti itu dari satu teorema yang sesuai yang dibuktikan dalam pengaturan aksiomatik. Ini adalah keuntungan umum dari pendekatan aksiomatik dalam matematika.
Pendekatan aksiomatik teori informasi algoritmik dikembangkan lebih lanjut dalam buku (Burgin 2005) dan diterapkan pada metrik perangkat lunak (Burgin dan Debnath, 2003; Debnath dan Burgin, 2003).
Definisi yang tepat
Sebuah string biner dikatakan acak jika kompleksitas Kolmogorov string setidaknya panjang string. Argumen penghitungan sederhana menunjukkan bahwa beberapa string dengan panjang tertentu adalah acak, dan hampir semua string sangat dekat dengan acak. Karena kompleksitas Kolmogorov bergantung pada pilihan tetap mesin Turing universal (secara informal, “bahasa deskripsi” tetap di mana “deskripsi” diberikan), kumpulan string acak memang bergantung pada pilihan mesin universal tetap.
Baca Juga : 5 Hukum dan Teori Ilmiah Yang Harus Anda Ketahui
Namun demikian, kumpulan string acak, secara keseluruhan, memiliki properti serupa terlepas dari mesin tetap, sehingga seseorang dapat (dan sering) berbicara tentang properti string acak sebagai grup tanpa harus terlebih dahulu menentukan mesin universal. Urutan biner yang tak terbatas dikatakan acak jika, untuk beberapa konstan c , untuk semua n , yang kompleksitas Kolmogorov dari segmen awal panjang n dari urutan setidaknya n – c . Dapat ditunjukkan bahwa hampir setiap urutan (dari sudut pandang ukuran standar — “koin adil” atau ukuran Lebesgue—pada ruang barisan biner tak terhingga) adalah acak.
Juga, karena dapat ditunjukkan bahwa kompleksitas Kolmogorov relatif terhadap dua mesin universal yang berbeda paling banyak berbeda pada konstanta, kumpulan urutan tak terbatas acak tidak bergantung pada pilihan mesin universal (berlawanan dengan string hingga). Definisi keacakan ini biasanya disebut keacakan Martin-Löf , setelah Per Martin-Löf , untuk membedakannya dari gagasan keacakan serupa lainnya.
Kadang-kadang juga disebut keacakan 1 untuk membedakannya dari gagasan lain yang lebih kuat tentang keacakan (2-keacakan, 3-keacakan, dll.). Selain konsep keacakan Martin-Löf, ada juga keacakan rekursif, keacakan Schnorr, dan keacakan Kurtz dll. Yongge Wangmenunjukkan bahwa semua konsep keacakan ini berbeda.