Veri sıkıştırma sorunu en basit haliyle sayılar ve bunların gösterimleriyle ilgili olabilir. Sayılar rakamlarla gösterilebilir ("onbir" 11 sayısı için), matematiksel ifadeler ("yirmincide iki" 1048576 için), dize ifadeleri ("beş dokuzlu" 99999 için), özel isimler ("canavarın numarası" 666 için, "Turing'in ölüm yılı" 1954 için) veya bunların keyfi kombinasyonları. Muhatabın hangi sayıdan bahsettiğimizi açıkça belirleyebileceği herhangi bir atama uygundur. Açıkçası muhatabınıza söyleyin "sekizin faktöriyeli" eşdeğer gösterimden daha verimli "kırk bin üç yüz yirmi". Burada mantıksal bir soru ortaya çıkıyor: Belirli bir sayının en kısa gösterimi nedir?
Filozof Bertrand Russell'ın 1908'de yayınladığı , karşı taraftan sayı gösterimi konusuna değiniyor: Seksen harf gerektirmeyen en küçük sayı nedir?
Böyle bir sayı mevcut olmalıdır: seksen Rus harfi ve boşluğundan yalnızca 3480 atama oluşturabilirsiniz, bu da seksen harf kullanarak 3480'den fazla sayıyı belirleyemeyeceğiniz anlamına gelir. Bu, 3480'den fazla olmayan belirli bir sayıyı bu şekilde belirlemenin imkansız olduğu anlamına gelir.
Bu, bu sayının atamaya karşılık geleceği anlamına gelir "seksen harfin yeterli olmadığı en küçük sayı", sadece 78 harften oluşuyor! Bir yandan bu sayının var olması gerekir; Öte yandan, eğer bu sayı mevcutsa, o zaman tanımı ona uymuyor demektir. Paradoks!
Bu paradoksu göz ardı etmenin en kolay yolu sözlü gösterimlerin gayri resmiliğine atıfta bulunmaktır. Mesela, gösterimde yalnızca özel olarak tanımlanmış bir dizi ifadeye izin veriliyorsa, o zaman "seksen harfin yeterli olmadığı en küçük sayı" geçerli bir gösterim olmayacaktır, oysa pratik olarak yararlı gösterimler "sekizin faktöriyeli" kabul edilebilir kalacaktır.
Sayılarla ilgili eylemlerin sırasını (algoritmasını) tanımlamanın resmi yolları var mı? Var ve bol miktarda bunlara programlama dilleri deniyor. Sözlü gösterimler yerine gerekli sayıları görüntüleyen programları (örneğin Python'da) kullanacağız. Örneğin beş dokuzlu program uygundur print("9"*5). Belirli bir sayı için en kısa programla ilgilenmeye devam edeceğiz. Böyle bir programın uzunluğuna denir sayılar; belirli bir sayının sıkıştırılabileceği teorik sınırdır.
Artık Berry'nin paradoksu yerine benzerini düşünebiliriz: Bir kilobayt programın çıktısını almak için yeterli olmadığı en küçük sayı nedir?
Daha önce olduğu gibi mantık yürüteceğiz: 2561024 kilobayt metin var, bu da kilobayt programlar tarafından 2561024'ten fazla sayının çıkarılamayacağı anlamına geliyor. Bu, 2561024'ten büyük olmayan belirli bir sayının bu şekilde elde edilemeyeceği anlamına gelir.
Ancak Python'da tüm olası kilobayt metinleri üreten, bunları yürütmek için çalıştıran ve bir sayı çıktısı verirse bu sayıyı ulaşılabilir olanlar sözlüğüne ekleyen bir program yazalım. Program, 2561024 olasılığın tamamını kontrol ettikten sonra, ne kadar zaman alırsa alsın, sözlükte eksik olan en küçük sayıyı arar ve o sayıyı yazdırır. Böyle bir programın bir kilobaytlık koda sığacağı ve bir kilobaytlık programın üretemeyeceği sayıyı çıkaracağı açıktır!
Şimdi sorun ne? Artık gösterimin gayri resmiliğine atfedilemez!
Programımızın çalışması için astronomik miktarda belleğe (2561024 öğeden oluşan bir sözlük (veya bit dizisi)) ihtiyaç duyacağı gerçeğiyle kafanız karıştıysa, o zaman aynı şeyi onsuz da yapabilirsiniz: 2561024 sayının her biri için, sırayla , uygun bir program kalmayıncaya kadar 2561024 olası programın tümünü gözden geçirin. Böyle bir aramanın çok uzun sürmesi önemli değil: sayıdan ve programdan (2561024)2 çiftten daha azını kontrol ettikten sonra sona erecek ve o çok sevilen sayıyı bulacaktır.
Yoksa bitmeyecek mi? Aslında denenecek tüm programlar arasında şunlar olacak: while True: pass (ve işlevsel analogları) - ve mesele böyle bir programın test edilmesinden öteye gitmeyecek!
Sorunun notasyonun gayri resmiliği olduğu Berry paradoksunun aksine, ikinci durumda iyi gizlenmiş bir yeniden formülasyonla karşı karşıyayız. . Gerçek şu ki, bir programın çıktısını sonlu bir sürede belirlemek imkansızdır. Özellikle Kolmogorov karmaşıklığı : Belirli bir sayı için bu sayıyı basan en kısa programın uzunluğunu bulmayı sağlayacak bir algoritma yoktur; bu da Berry'nin belirli bir sayının en kısa sözlü gösteriminin uzunluğunu bulma sorununun bir çözümü olmadığı anlamına geliyor.
Kaynak: habr.com