Algoritmik olarak rastgele dizi - Algorithmically random sequence

Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar. (Ağustos 2018) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Sezgisel olarak, bir algoritmik olarak rastgele sıra (veya rastgele sıra) bir sıra görünen ikili rakamlar^{[açıklama gerekli ]} bir üzerinde çalışan herhangi bir algoritmaya rastgele (öneksiz veya değil) evrensel Turing makinesi. Kavram, herhangi bir sonlu alfabedeki dizilere benzer şekilde uygulanabilir (örneğin, ondalık basamaklar). Rastgele diziler, algoritmik bilgi teorisi.

Bazen farklı algoritma türleri dikkate alındığından, çalışma süreleri üzerinde belirli sınırları olan algoritmalardan, bir algoritma ile ilgili sorular sorabilen algoritmalara kadar değişir. oracle makinesi farklı rastgelelik kavramları vardır. Bunlardan en yaygın olanı şu şekilde bilinir: Martin-Löf rastgeleliği (K-rastgelelik veya 1-rastgelelik), ancak daha güçlü ve daha zayıf rastgelelik biçimleri de mevcuttur. Belirli bir tek (sonlu veya sonsuz) diziye açıklama yapmadan atıfta bulunmak için kullanılan "algoritmik olarak rastgele" terimi genellikle "sıkıştırılamaz" anlamına gelir veya dizinin sonsuz ve önek algoritmik olarak rasgele (yani, K-sıkıştırılamaz) olması durumunda, "Martin-Löf-Chaitin rastgele".

Algoritmik rastgeleliği stokastik rasgelelikle netleştirmek önemlidir. Hesaplanabilir (ve dolayısıyla belirleyici) süreçler için tanımlanan algoritmik rasgeleliğin aksine, stokastik rasgeleliğin, genellikle, bir dizi tarafından oluşturulduğu (veya sonucu olduğu) önceden bilinen bir dizinin özelliği olduğu söylenir. bağımsız aynı şekilde dağıtılmış eşitlenebilir stokastik süreç.

İkili rakamların sonsuz dizileri birim aralığında gerçek sayılarla tanımlanabildiğinden, rastgele ikili diziler genellikle (algoritmik olarak) rastgele gerçek sayılar. Ek olarak, sonsuz ikili diziler, doğal sayı kümelerinin karakteristik işlevlerine karşılık gelir; bu nedenle bu diziler doğal sayı kümeleri olarak görülebilir.

Tüm Martin-Löf rastgele (ikili) dizilerinin sınıfı, RAND veya MLR ile gösterilir.

Tarih

Rastgele bir dizinin ilk uygun tanımı şu şekilde verilmiştir: Martin-Löf için 1966'da. Daha önceki araştırmacılar Richard von Mises bir kavramını resmileştirmeye teşebbüs etmişti rastgelelik testi rasgele bir diziyi, rasgelelik için tüm testleri geçen bir dizi olarak tanımlamak için; ancak, bir rastgelelik testinin kesin fikri belirsiz kaldı. Martin-Löf'ün temel anlayışı, hesaplama teorisi rastgelelik testi kavramını resmen tanımlamak. Bu, içinde rastgelelik fikriyle çelişir. olasılık; bu teoride, bir örnek uzayın hiçbir belirli unsurunun rastgele olduğu söylenemez.

Başlangıcından bu yana, Martin-Löf rastgeleliğinin birçok eşdeğer karakterizasyonu kabul ettiği gösterilmiştir. sıkıştırma, rastgelelik testleri ve kumar - orijinal tanıma çok az dışsal benzerlik taşıyan, ancak her biri rastgele dizilerin sahip olması gereken sezgisel özellikler kavramımızı karşılayan: rastgele diziler sıkıştırılamaz olmalı, rastgele diziler için istatistiksel testleri geçmelidir ve para kazanmak zor olmalıdır. bahis onlar üzerinde. Martin-Löf rasgeleliğinin bu çoklu tanımlarının varlığı ve bu tanımların farklı hesaplama modelleri altındaki kararlılığı, Martin-Löf rasgeleliğinin matematiğin temel bir özelliği olduğunu ve Martin-Löf'ün özel modelinin bir tesadüfü olmadığını kanıtlar. Martin-Löf rastgelelik tanımının sezgisel rastgelelik kavramını "doğru" olarak yakaladığı tezine, Martin-Löf – Chaitin Tezi; biraz benzer Kilise-Turing tezi.^[1]

Üç eşdeğer tanım

Martin-Löf'ün bir rastgele diziye ilişkin orijinal tanımı, yapıcı boş kapaklar açısından yapıldı; böyle bir örtüde yer almayan bir diziyi rastgele olarak tanımladı. Gregory Chaitin, Leonid Levin ve Claus-Peter Schnorr açısından bir karakterizasyon olduğunu kanıtladı algoritmik karmaşıklık: bir dizi, başlangıçtaki bölümlerinin sıkıştırılabilirliği üzerinde tekdüze bir sınır varsa rastgele olur. Schnorr, açısından üçüncü bir eşdeğer tanım verdi Martingales. Li ve Vitanyi'nin kitabı Kolmogorov Karmaşıklığına Giriş ve Uygulamaları bu fikirlere standart bir giriştir.

• Algoritmik karmaşıklık (Chaitin 1969, Schnorr 1973, Levin 1973): Algoritmik karmaşıklık (aka (önek içermeyen) Kolmogorov karmaşıklığı veya program boyutu karmaşıklığı), sonlu bir dizinin (karakterlerden veya ikili rakamlardan oluşan) algoritmik sıkıştırılabilirliğinin alt sınırı olarak düşünülebilir. Bu tür her diziye atar w doğal bir sayı K (w) sezgisel olarak, girdi almayan ve çıktı verecek bir bilgisayar programının (bazı sabit programlama dillerinde yazılmış) minimum uzunluğunu ölçer. w çalıştırıldığında. Karmaşıklığın önek içermemesi gerekir: Programı (0 ve 1 dizisi) sonsuz bir 0 dizisi takip eder ve programın uzunluğu (durduğu varsayılarak) sağdaki sıfırların sayısını içerir. Evrensel Turing makinesinin okuduğu program. Ek gereksinim gereklidir, çünkü uzunluk, alt dizeyle ilgili bilgileri kodlayacak şekilde bir uzunluk seçebiliriz. Doğal bir sayı verildiğinde c ve bir dizi wbunu söylüyoruz w dır-dir csıkıştırılamaz Eğer ${displaystyle K (w) geq | w | -c}$.

Sonsuz bir dizi S Martin-Löf tesadüfidir, ancak ve ancak bir sabit varsa c öyle ki hepsi S 's sonlu önekler vardır csıkıştırılamaz.

• Yapıcı boş kapaklar (Martin-Löf 1966): Bu Martin-Löf'ün orijinal tanımıdır. Sonlu bir ikili dizge için w izin verdik C_w belirtmek tarafından üretilen silindir w. Bu, ile başlayan tüm sonsuz dizilerin kümesidir. wtemel bir açık küme olan Kantor alanı. ürün ölçü μ (C_w) tarafından üretilen silindirin w 2 olarak tanımlanır^−|w|. Cantor uzayının her açık alt kümesi, sayılabilir ayrık temel açık kümeler dizisinin birleşimidir ve açık kümenin ölçüsü, bu tür herhangi bir dizinin ölçülerinin toplamıdır. Bir etkili açık küme bir tarafından belirlenen temel açık kümeler dizisinin birleşimi olan açık bir kümedir yinelemeli olarak numaralandırılabilir ikili dizeler dizisi. Bir yapıcı boş kapak veya etkili ölçü 0 set özyinelemeli olarak numaralandırılabilir bir dizidir ${displaystyle U_ {i}}$ etkili açık kümelerin ${displaystyle U_ {i + 1} subseteq U_ {i}}$ ve ${displaystyle mu (U_ {i}) leq 2 ^ {- i}}$ her doğal sayı için ben. Her etkili boş kapak, bir ${displaystyle G_ {delta}}$ ölçü seti 0, yani setlerin kesişimi ${displaystyle U_ {i}}$.

Herhangi bir dizinin içinde yer almayan bir dizi, Martin-Löf rastgele olarak tanımlanır. ${displaystyle G_ {delta}}$ set yapıcı bir boş kapak tarafından belirlenir.

• Yapıcı martingales (Schnorr 1971): Bir Martingale bir işlev ${displaystyle d: {0,1} ^ {*} o [0, infty)}$ öyle ki, tüm sonlu dizeler için w, ${displaystyle d (w) = (d (w ^ {smallfrown} 0) + d (w ^ {smallfrown} 1)) / 2}$, nerede ${displaystyle a ^ {smallfrown} b}$ ... birleştirme dizelerin a ve b. Buna "adalet koşulu" denir: eğer bir martingale bir bahis stratejisi olarak görülüyorsa, o zaman yukarıdaki koşul, bahisçinin adil oranlara karşı oynamasını gerektirir. Bir martingale d söylendi başarılı olmak bir dizide S Eğer ${displaystyle limsup _ {n o infty} d (Supharpoonright n) = infty,}$ nerede ${displaystyle Supharpoonright n}$ İlk mi n bitleri S. Bir martingale d dır-dir yapıcı (Ayrıca şöyle bilinir zayıf hesaplanabilir, düşük yarı hesaplanabilir) hesaplanabilir bir işlev varsa ${displaystyle {widehat {d}}: {0,1} ^ {*} imes mathbb {N} o {mathbb {Q}}}$ öyle ki, tüm sonlu ikili dizeler için w

1. ${displaystyle {widehat {d}} (w, t) leq {widehat {d}} (w, t + 1)$ tüm pozitif tam sayılar için t,
2. ${displaystyle lim _ {t o infty} {widehat {d}} (w, t) = d (w).}$

Bir dizi Martin-Löf'ün gelişigüzel şeklidir, ancak ve ancak üzerinde yapıcı bir martingale başarılı olmazsa.

Tanımların yorumları

Kolmogorov karmaşıklık karakterizasyonu, rastgele bir dizinin sıkıştırılamaz olduğu sezgisini aktarır: hiçbir önek, önekten çok daha kısa bir program tarafından üretilemez.

Boş kapak karakterizasyonu, rastgele bir gerçek sayının "yaygın olmayan" herhangi bir özelliğe sahip olmaması gerektiği sezgisini aktarır. Her ölçü 0 kümesi, yaygın olmayan bir özellik olarak düşünülebilir. Bir dizinin hiçbir ölçü 0 kümesinde yer alması mümkün değildir, çünkü her bir noktalı kümenin ölçüsü 0'dır. Martin-Löf'ün fikri, tanımı etkin bir şekilde tanımlanabilen 0 kümeyi ölçecek şekilde sınırlamaktı; Etkili bir sıfır örtünün tanımı, etkin bir şekilde tanımlanabilir ölçüm 0 kümelerinin sayılabilir bir koleksiyonunu belirler ve bu belirli ölçüm 0 kümelerinin herhangi birinde yer almıyorsa rastgele olacak bir diziyi tanımlar. Sayılabilir bir ölçüm 0 kümeleri koleksiyonunun birleşimi 0 ölçüsüne sahip olduğundan, bu tanım hemen bir ölçü 1 rasgele dizi dizisi olduğu teoremine yol açar. İkili dizilerin Cantor uzayını gerçek sayıların [0,1] aralığı ile tanımlarsak, Cantor uzayındaki ölçü ile uyuştuğunu unutmayın. Lebesgue ölçümü.

Martingale karakterizasyonu, etkili hiçbir prosedürün rastgele bir sıraya karşı para yatırması yapılmaması gerektiği sezgisini aktarır. Bir martingale d bir bahis stratejisidir. d sonlu bir dizeyi okur w ve bir sonraki parça için para yatırır. Parasının bir kısmını, bir sonraki bitin 0 olacağına ve ardından kalan parasının bir sonraki bitin 1 olacağına bahse girer. d gerçekte meydana gelen bit üzerine koyduğu parayı iki katına çıkarır ve gerisini kaybeder. d(w) dizeyi gördükten sonra sahip olduğu para miktarıdır w. Diziyi gördükten sonra oynanan bahis w değerlerden hesaplanabilir d(w), d(w0) ve d(w1), sahip olduğu para miktarını hesaplamak, bahsi hesaplamakla eşdeğerdir. Martingale karakterizasyonu, herhangi bir bilgisayar tarafından uygulanabilecek hiçbir bahis stratejisi olmadığını söylüyor (zayıf yapıcı stratejiler anlamında bile, hesaplanabilir ) rastgele bir sırayla para yatırabilir.

Martin-Löf rastgele dizilerinin özellikleri ve örnekleri

• Chaitin'in durma olasılığı Ω rastgele bir dizinin bir örneğidir.
• RAND^c ( Tamamlayıcı RAND) bir ölçü Tüm sonsuz diziler kümesinin 0 alt kümesi. Bu, her yapıcı boş örtünün bir ölçü 0 setini kapsaması gerçeğiyle ifade edilir, sadece sayıca çok yapıcı boş örtüler ve sayılabilir ölçü birliği 0 kümeleri 0 ölçüsüne sahiptir. Bu, RAND'ın tüm sonsuz diziler kümesinin bir ölçü 1 alt kümesi olduğu anlamına gelir.
• Her rastgele sıra normal.
• RAND için yapıcı bir boş kapak var^c. Bu, rastgelelik için tüm etkili testlerin (yani, yapıcı boş örtüler) bir anlamda bunun tarafından kapsandığı anlamına gelir. evrensel Bu tek rastgelelik testini geçen herhangi bir dizi rastgelelik için tüm testleri geçeceğinden, rastgelelik testi. (Martin-Löf 1966)
• Var evrensel yapıcı martingale d. Bu martingale, herhangi bir yapıcı martingale verildiğinde evrenseldir. d, Eğer d bir dizide başarılı olursa d bu dizide de başarılı olur. Böylece, d RAND'daki her dizide başarılı olur^c (ama o zamandan beri d yapıcıdır, RAND'de hiçbir sırada başarılı olmaz). (Schnorr 1971)
• RAND sınıfı bir ${displaystyle Sigma _ {2} ^ {0}}$ Cantor alanının alt kümesi, burada ${displaystyle Sigma _ {2} ^ {0}}$ ikinci seviyeyi ifade eder aritmetik hiyerarşi. Bunun nedeni bir dizi S RAND içindedir ancak ve ancak evrensel etkili boş kapakta içermeyen bazı açık küme varsa S; bu özelliğin bir tarafından tanımlanabilir olduğu görülebilir. ${displaystyle Sigma _ {2} ^ {0}}$ formül.
• Rastgele bir dizi var ${displaystyle Delta _ {2} ^ {0}}$yani Duraklama problemi için bir oracle'a göre hesaplanabilir. (Schnorr 1971) Chaitin Ω böyle bir dizinin bir örneğidir.
• Rastgele sıra yok karar verilebilir, hesaplanabilir şekilde numaralandırılabilir veya birlikte hesaplanabilir. Bunlar karşılık geldiğinden ${displaystyle Delta _ {1} ^ {0}}$, ${displaystyle Sigma _ {1} ^ {0}}$, ve ${displaystyle Pi _ {1} ^ {0}}$ seviyeleri aritmetik hiyerarşi, bu şu demek ${displaystyle Delta _ {2} ^ {0}}$ rastgele dizilerin bulunabileceği aritmetik hiyerarşideki en düşük seviyedir.
• Her sekans Turing indirgenebilir rastgele bir sırayla. (Kučera 1985/1989, Gács 1986). Bu nedenle, rastgele yüksek rastgele diziler vardır. Turing derecesi.

Göreli rastgelelik

Bir Martin-Löf rastgele dizisinin eşdeğer tanımlarının her biri, Turing makinesi tarafından neyin hesaplanabildiğine dayandığından, doğal olarak Turing tarafından neyin hesaplanabildiği sorulabilir. oracle makinesi. Sabit bir oracle için Bir, bir dizi B Bu sadece rastgele değil, aslında, hesaplanabilirlik için eşdeğer tanımları karşılar Bir (örneğin, kahine göre yapıcı olan martingale yok Bir başarılı B) göre rastgele olduğu söylenir Bir. İki sekans kendileri rastgele olsalar da çok benzer bilgiler içerebilir ve bu nedenle ikisi de diğerine göre rastgele olmayacaktır. Ne zaman bir Turing azaltma bir diziden diğerine, ikinci dizi birinciye göre rasgele olamaz, tıpkı hesaplanabilir dizilerin kendilerinin rasgele olmaması gibi; özellikle, bu şu anlama gelir: Chaitin Ω göre rastgele değil durdurma sorunu.

Göreceli rastgelelikle ilgili önemli bir sonuç, van Lambalgen teoremi, eğer C oluşan dizidir Bir ve B ilk bitini serpiştirerek Birilk kısmı Bikinci kısmı Birikinci kısmı Bvb. sonra C algoritmik olarak rastgeledir ancak ve ancak Bir algoritmik olarak rastgele ve B algoritmik olarak rastgele Bir. Yakından ilişkili bir sonuç şudur: Bir ve B her ikisi de rastgele, o zaman Bir göre rastgele B ancak ve ancak B göre rastgele Bir.

Martin-Löf rastgeleliğinden daha güçlü

Göreli rastgelelik, bize sabit bir oracle'a göre rastgelelik olan Martin-Löf rastgeleliğinden daha güçlü olan ilk fikri verir. Bir. Herhangi bir kehanet için, bu en azından onun kadar güçlüdür ve çoğu kehanet için, kesinlikle daha güçlüdür, çünkü kehanete göre rastgele olmayan Martin-Löf rastgele dizileri olacaktır. Bir. Sıklıkla düşünülen önemli oracle'lar durdurma sorunudur. ${displaystyle emptyset '}$, ve ninci atlama oracle, ${displaystyle boş küme ^ {(n)}}$, çünkü bu kahinler doğal olarak ortaya çıkan belirli soruları cevaplayabilirler. Kahine göre rastgele olan bir dizi ${displaystyle boş küme ^ {(n-1)}}$ denir n-random; bir dizi 1 rasgele, bu nedenle, ancak ve ancak Martin-Löf rastgele ise. Bir dizi nher biri için rastgele n aritmetik olarak rasgele denir. n-Rastgele diziler bazen daha karmaşık özellikler düşünüldüğünde ortaya çıkar. Örneğin, yalnızca sayılabilecek kadar çok ${displaystyle Delta _ {2} ^ {0}}$ kümeler, bu nedenle bunların rastgele olmaması gerektiği düşünülebilir. Ancak, durma olasılığı Ω dır-dir ${displaystyle Delta _ {2} ^ {0}}$ ve 1-rastgele; ancak 2-rastgeleliğe ulaşıldıktan sonra bir rastgele setin olması imkansızdır. ${displaystyle Delta _ {2} ^ {0}}$.

Martin-Löf rastgeleliğinden daha zayıf

Ek olarak, Martin-Löf rastgeleliğinden daha zayıf olan birkaç rastgelelik kavramı vardır. Bunlardan bazıları zayıf 1-rastgelelik, Schnorr rasgelelik, hesaplanabilir rastgelelik, kısmi hesaplanabilir rasgeleliktir. Yongge Wang gösterdi ^[2] Schnorr rastgeleliğinin hesaplanabilir rastgelelikten farklı olduğu. Ek olarak, Kolmogorov-Loveland rastgeleliğinin Martin-Löf rastgeleliğinden daha güçlü olmadığı bilinmektedir, ancak gerçekte daha zayıf olup olmadığı bilinmemektedir.

Rastgelelik spektrumunun diğer ucunda bir K-önemsiz set. Bu kümeler, tüm başlangıç ​​segmentlerinin logaritmik olarak sıkıştırılabilir olması bakımından rastgele değildir (yani, ${displaystyle K (w) leq K (| w |) + b}$ her bir başlangıç ​​segmenti için w), ancak hesaplanamazlar.

Ayrıca bakınız

• Rastgele sıra
• Gregory Chaitin
• Stokastik
• Monte Carlo yöntemi
• K-önemsiz set
• Evrensellik olasılığı
• İstatistiksel rastgelelik

Referanslar

daha fazla okuma

• Downey, Rod; Hirschfeldt, Denis R .; Nies, André; Terwijn, Sebastiaan A. (2006). "Rastgele Kalibre Ediliyor". Sembolik Mantık Bülteni. 12 (3/4): 411–491. CiteSeerX  10.1.1.135.4162. doi:10.2178 / bsl / 1154698741. Arşivlenen orijinal 2016-02-02 tarihinde.
• Gács, Péter (1986). "Her dizi rastgele bir diziye indirgenebilir" (PDF). Bilgi ve Kontrol. 70 (2/3): 186–192. doi:10.1016 / s0019-9958 (86) 80004-3.
• Kučera, A. (1985). "Ölçün, Π⁰
  ₁- PA'nın sınıfları ve tam uzantıları ". Özyineleme Teorisi Haftası. Matematikte Ders Notları. 1141. Springer-Verlag. sayfa 245–259. doi:10.1007 / BFb0076224. ISBN  978-3-540-39596-6.

• Kučera, A. (1989). "Çapraz olarak yinelemeli olmayan işlevlerin kullanımı hakkında". Mantık Çalışmaları ve Matematiğin Temelleri. 129. Kuzey-Hollanda. s. 219–239.

• Levin, L. (1973). "Rasgele sıra kavramı üzerine". Sovyet Matematiği - Doklady. 14: 1413–1416.

• Li, M .; Vitanyi, P.M.B. (1997). Kolmogorov Karmaşıklığına ve Uygulamalarına Giriş (İkinci baskı). Berlin: Springer-Verlag.

• Martin-Löf, P. (1966). "Rastgele dizilerin tanımı". Bilgi ve Kontrol. 9 (6): 602–619. doi:10.1016 / s0019-9958 (66) 80018-9.
• Nies, André (2009). Hesaplanabilirlik ve rastgelelik. Oxford Mantık Kılavuzları. 51. Oxford: Oxford University Press. ISBN  978-0-19-923076-1. Zbl  1169.03034.

• Schnorr, C. P. (1971). "Rastgele bir dizinin tanımına birleşik bir yaklaşım". Matematiksel Sistemler Teorisi. 5 (3): 246–258. doi:10.1007 / BF01694181. S2CID  8931514.

• Schnorr, Claus P. (1973). "Süreç karmaşıklığı ve etkili rastgele testler". Bilgisayar ve Sistem Bilimleri Dergisi. 7 (4): 376–388. doi:10.1016 / s0022-0000 (73) 80030-3.

• Chaitin, Gregory J. (1969). "Sonlu İkili Dizileri Hesaplamak İçin Programların Uzunluğu Hakkında: İstatistiksel Hususlar". ACM Dergisi. 16 (1): 145–159. doi:10.1145/321495.321506. S2CID  8209877.

• Ville, J. (1939). Etüt eleştiri de la nosyon de kolektif. Paris: Gauthier-Villars.