एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम

"Algorithmic randomness" redirects here. Not to be confused with Randomized algorithms.

सहजता से, एक एल्गोरिथम यादृच्छिक अनुक्रम (या यादृच्छिक अनुक्रम) बाइनरी अंकों के सैद्धांतिक कंप्यूटर विज्ञान में एक अनुक्रम # अनंत अनुक्रम है जो किसी भी एल्गोरिदम (उपसर्ग-मुक्त या नहीं) सार्वभौमिक ट्यूरिंग मशीन पर चल रहा है। धारणा को किसी भी परिमित वर्णमाला (जैसे दशमलव अंक) पर अनुक्रमों के अनुरूप लागू किया जा सकता है। एल्गोरिथम सूचना सिद्धांत में यादृच्छिक अनुक्रम अध्ययन की प्रमुख वस्तुएं हैं।

जैसा कि कभी-कभी विभिन्न प्रकार के एल्गोरिदम पर विचार किया जाता है, उनके चलने के समय पर एल्गोरिदम से लेकर एल्गोरिदम तक जो एक ओरेकल मशीन के प्रश्न पूछ सकते हैं, यादृच्छिकता की विभिन्न धारणाएँ हैं। इनमें से सबसे आम मार्टिन-लोफ यादृच्छिकता (के-यादृच्छिकता या 1-यादृच्छिकता) के रूप में जाना जाता है, लेकिन यादृच्छिकता के मजबूत और कमजोर रूप भी मौजूद हैं। जब एल्गोरिथम रैंडम शब्द का उपयोग स्पष्टीकरण के बिना किसी विशेष एकल (परिमित या अनंत) अनुक्रम को संदर्भित करने के लिए किया जाता है, तो इसे आमतौर पर असम्पीडित या, अनुक्रम अनंत और प्रीफ़िक्स एल्गोरिथम रैंडम (यानी, के-असंपीड़ित) होने के मामले में लिया जाता है। मार्टिन-लोफ-चैटिन यादृच्छिक।

एल्गोरिथम यादृच्छिकता और स्टोकेस्टिक यादृच्छिकता के बीच स्पष्ट करना महत्वपूर्ण है। एल्गोरिथम यादृच्छिकता के विपरीत, जिसे संगणनीय (और इस प्रकार नियतात्मक) प्रक्रियाओं के लिए परिभाषित किया गया है, स्टोचैस्टिक यादृच्छिकता को आमतौर पर एक अनुक्रम की संपत्ति कहा जाता है जो एक स्वतंत्रता (संभाव्यता सिद्धांत) द्वारा उत्पन्न होने वाली प्राथमिकता है (या इसका परिणाम है) समान रूप से संभाव्यता वितरण समसंभाव्य स्टोकेस्टिक प्रक्रिया।

क्योंकि बाइनरी अंकों के अनंत अनुक्रमों को इकाई अंतराल में वास्तविक संख्याओं के साथ पहचाना जा सकता है, यादृच्छिक बाइनरी अनुक्रमों को अक्सर (एल्गोरिथमिक रूप से) यादृच्छिक वास्तविक संख्या कहा जाता है। इसके अतिरिक्त, अनंत बाइनरी अनुक्रम प्राकृतिक संख्याओं के सेट के विशिष्ट कार्यों के अनुरूप होते हैं; इसलिए उन अनुक्रमों को प्राकृतिक संख्याओं के समुच्चय के रूप में देखा जा सकता है।

सभी मार्टिन-लोफ यादृच्छिक (बाइनरी) अनुक्रमों की श्रेणी को रैंड या एमएलआर द्वारा दर्शाया गया है।

इतिहास

एक यादृच्छिक अनुक्रम की पहली उपयुक्त परिभाषा 1966 में प्रति मार्टिन-लोफ द्वारा दी गई थी। इससे पहले रिचर्ड वॉन मिसेस जैसे शोधकर्ताओं ने एक यादृच्छिक अनुक्रम को परिभाषित करने के लिए एक यादृच्छिकता परीक्षण की धारणा को औपचारिक रूप देने का प्रयास किया था, जो कि यादृच्छिकता के लिए सभी परीक्षणों को पारित करता है। ; हालाँकि, एक यादृच्छिकता परीक्षण की सटीक धारणा अस्पष्ट छोड़ दी गई थी। मार्टिन-लोफ की प्रमुख अंतर्दृष्टि यादृच्छिकता के लिए एक परीक्षण की धारणा को औपचारिक रूप से परिभाषित करने के लिए अभिकलन के सिद्धांत का उपयोग करना था। यह संभाव्यता में यादृच्छिकता के विचार के विपरीत है; उस सिद्धांत में, नमूना स्थान का कोई विशेष तत्व यादृच्छिक नहीं कहा जा सकता है।

इसकी स्थापना के बाद से, मार्टिन-लोफ यादृच्छिकता को डेटा संपीड़न, यादृच्छिकता परीक्षणों और जुए के संदर्भ में कई समकक्ष विशेषताओं को स्वीकार करने के लिए दिखाया गया है-जो मूल परिभाषा के लिए थोड़ा बाहरी समानता रखते हैं, लेकिन इनमें से प्रत्येक गुणों की हमारी सहज धारणा को संतुष्ट करता है यादृच्छिक अनुक्रम होना चाहिए: यादृच्छिक अनुक्रम असंगत होना चाहिए, उन्हें यादृच्छिकता के लिए सांख्यिकीय परीक्षण पास करना चाहिए, और उन पर पैसा लगाना मुश्किल होना चाहिए। मार्टिन-लोफ यादृच्छिकता की इन कई परिभाषाओं का अस्तित्व, और संगणना के विभिन्न मॉडलों के तहत इन परिभाषाओं की स्थिरता, इस बात का प्रमाण देती है कि मार्टिन-लोफ यादृच्छिकता गणित की एक मौलिक संपत्ति है और मार्टिन-लोफ के विशेष मॉडल की दुर्घटना नहीं है। थीसिस कि मार्टिन-लोफ यादृच्छिकता की परिभाषा सही ढंग से यादृच्छिकता की सहज धारणा को पकड़ती है, मार्टिन-लोफ-चैटिन थीसिस कहलाती है; यह कुछ हद तक चर्च-ट्यूरिंग थीसिस के समान है।

तीन समकक्ष परिभाषाएँ

मार्टिन-लोफ की एक यादृच्छिक अनुक्रम की मूल परिभाषा रचनात्मक नल कवर के संदर्भ में थी; उन्होंने एक अनुक्रम को यादृच्छिक होने के लिए परिभाषित किया यदि यह ऐसे किसी आवरण में समाहित नहीं है। ग्रेगरी चैतिन, लियोनिद लेविन और क्लॉस-पीटर Schnorr ने कोलमोगोरोव जटिलता के संदर्भ में एक लक्षण वर्णन साबित किया: एक अनुक्रम यादृच्छिक है यदि इसके प्रारंभिक खंडों की संपीडनशीलता पर एक समान सीमा है। श्नॉर ने मार्टिंगेल (संभाव्यता सिद्धांत) के संदर्भ में तीसरी समकक्ष परिभाषा दी। ली और वितानी की किताब कोलमोगोरोव कॉम्प्लेक्सिटी एंड इट्स एप्लिकेशन का एक परिचय इन विचारों का मानक परिचय है।

• 'एल्गोरिथमिक जटिलता' (चैटिन 1969, श्नोर 1973, लेविन 1973): एल्गोरिथम जटिलता (जिसे (उपसर्ग-मुक्त) कोलमोगोरोव जटिलता या प्रोग्राम-साइज़ जटिलता के रूप में भी जाना जाता है) को परिमित की एल्गोरिथम संपीड्यता पर एक निचली सीमा के रूप में सोचा जा सकता है। अनुक्रम (अक्षरों या बाइनरी अंकों का)। यह ऐसे प्रत्येक अनुक्रम w को एक प्राकृतिक संख्या K(w) प्रदान करता है, जो सहजता से, एक कंप्यूटर प्रोग्राम की न्यूनतम लंबाई को मापता है (कुछ निश्चित प्रोग्रामिंग भाषा में लिखा गया है) जो कोई इनपुट नहीं लेता है और रन होने पर आउटपुट w करेगा। उपसर्ग-मुक्त होने के लिए जटिलता आवश्यक है: कार्यक्रम (0 और 1 का एक क्रम) 0s की एक अनंत स्ट्रिंग द्वारा पीछा किया जाता है, और कार्यक्रम की लंबाई (इसे रोकते हुए) के दाईं ओर शून्य की संख्या शामिल होती है प्रोग्राम जिसे यूनिवर्सल ट्यूरिंग मशीन पढ़ती है। अतिरिक्त आवश्यकता की आवश्यकता है क्योंकि हम एक लंबाई चुन सकते हैं जैसे कि लंबाई सबस्ट्रिंग के बारे में जानकारी को कोड करती है। एक प्राकृतिक संख्या c और एक अनुक्रम w को देखते हुए, हम कहते हैं कि w 'c-incompressible' है, यदि $K(w)\geq |w|-c$.

एक अनंत अनुक्रम एस मार्टिन-लोफ यादृच्छिक है अगर और केवल अगर एक निरंतर सी है जैसे कि एस के सभी परिमित उपसर्ग (कंप्यूटर विज्ञान) सी-असंपीड़ित हैं।

• 'कंस्ट्रक्टिव नल कवर' (मार्टिन-लोफ 1966): यह मार्टिन-लोफ की मूल परिभाषा है। एक परिमित बाइनरी स्ट्रिंग w के लिए हम C_wडब्ल्यू 'द्वारा उत्पन्न सिलेंडर' निरूपित करें। यह डब्ल्यू से शुरू होने वाले सभी अनंत अनुक्रमों का सेट है, जो कैंटर स्पेस में एक मूल खुला सेट है। 'उत्पाद माप (गणित)' μ(C_w) w द्वारा उत्पन्न सिलेंडर को 2 के रूप में परिभाषित किया गया है^{-|व|</सुप>. कैंटर स्पेस का प्रत्येक खुला उपसमुच्चय असंयुक्त मूल खुले सेटों के एक गणनीय अनुक्रम का संघ है, और एक खुले सेट का माप ऐसे किसी अनुक्रम के उपायों का योग है। एक प्रभावी ओपन सेट एक ओपन सेट है जो बाइनरी स्ट्रिंग्स के पुनरावर्ती गणना योग्य अनुक्रम द्वारा निर्धारित बुनियादी ओपन सेट के अनुक्रम का संघ है। एक रचनात्मक नल कवर या प्रभावी उपाय 0 सेट एक पुनरावर्ती गणना योग्य अनुक्रम है $U_{i}$ ऐसे प्रभावी खुले सेटों की $U_{i+1}\subseteq U_{i}$ और $\mu (U_{i})\leq 2^{-i}$ प्रत्येक प्राकृतिक संख्या के लिए मैं। प्रत्येक प्रभावी नल कवर जी-डेल्टा सेट निर्धारित करता है$G_{\delta }$ माप 0 का सेट, अर्थात् सेट का प्रतिच्छेदन $U_{i}$.}

एक अनुक्रम को मार्टिन-लोफ रैंडम के रूप में परिभाषित किया जाता है यदि यह किसी में निहित नहीं है $G_{\delta }$ एक रचनात्मक नल कवर द्वारा निर्धारित सेट।

• 'कंस्ट्रक्टिव मार्टिंगेल्स' (श्नोर 1971): ए मार्टिंगेल (संभाव्यता सिद्धांत) एक कार्य है $d:\{0,1\}^{*}\to [0,\infty )$ ऐसा है कि, सभी परिमित तार w के लिए, $d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2$, कहाँ पे $a^{\smallfrown }b$ तार a और b का संयोजन है। इसे निष्पक्षता की स्थिति कहा जाता है: यदि मार्टिंगेल को सट्टेबाजी की रणनीति के रूप में देखा जाता है, तो उपरोक्त शर्त के लिए आवश्यक है कि सट्टेबाज उचित बाधाओं के खिलाफ खेले। एक मार्टिंगेल डी को अनुक्रम एस पर 'सफल' कहा जाता है यदि $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ कहाँ पे $S\upharpoonright n$ एस के पहले एन बिट्स हैं। एक मार्टिंगेल डी 'रचनात्मक' है (जिसे 'कमजोर गणना योग्य', 'कम अर्ध-गणना योग्य' के रूप में भी जाना जाता है) यदि कोई गणना योग्य कार्य मौजूद है ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ ऐसा है कि, सभी परिमित बाइनरी स्ट्रिंग्स के लिए w

1. ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ सभी सकारात्मक पूर्णांक टी के लिए,
2. $\lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).$ : एक अनुक्रम मार्टिन-लोफ यादृच्छिक है अगर और केवल अगर कोई रचनात्मक मार्टिंगेल सफल नहीं होता है।

परिभाषाओं की व्याख्या

कोल्मोगोरोव जटिलता लक्षण वर्णन अंतर्ज्ञान को व्यक्त करता है कि एक यादृच्छिक अनुक्रम असंपीड़ित है: उपसर्ग से बहुत कम प्रोग्राम द्वारा कोई उपसर्ग नहीं बनाया जा सकता है।

अशक्त आवरण लक्षण वर्णन अंतर्ज्ञान बताता है कि एक यादृच्छिक वास्तविक संख्या में ऐसी कोई संपत्ति नहीं होनी चाहिए जो असामान्य हो। प्रत्येक माप 0 सेट को एक असामान्य संपत्ति के रूप में माना जा सकता है। अनुक्रम के लिए बिना माप के 0 सेट में झूठ बोलना संभव नहीं है, क्योंकि प्रत्येक एक-बिंदु सेट में माप 0 है। मार्टिन-लोफ का विचार परिभाषा को 0 सेटों को मापने के लिए सीमित करना था जो प्रभावी रूप से वर्णित हैं; एक प्रभावी नल कवर की परिभाषा प्रभावी रूप से वर्णित माप 0 सेटों का एक गणनीय संग्रह निर्धारित करती है और अनुक्रम को यादृच्छिक होने के लिए परिभाषित करती है यदि यह इनमें से किसी विशेष माप 0 सेट में नहीं है। चूंकि माप 0 सेट के एक गणनीय संग्रह के मिलन का माप 0 है, इसलिए यह परिभाषा तुरंत प्रमेय की ओर ले जाती है कि यादृच्छिक अनुक्रमों का एक माप 1 सेट है। ध्यान दें कि यदि हम वास्तविक संख्याओं के अंतराल [0,1] के साथ बाइनरी अनुक्रमों के कैंटर स्पेस की पहचान करते हैं, तो कैंटर स्पेस पर माप लेबेसेग माप से सहमत है।

ज़रेबंद लक्षण वर्णन अंतर्ज्ञान बताता है कि कोई भी प्रभावी प्रक्रिया एक यादृच्छिक अनुक्रम के खिलाफ पैसे की सट्टेबाजी करने में सक्षम नहीं होनी चाहिए। मार्टिंगेल डी एक सट्टेबाजी की रणनीति है। d एक परिमित स्ट्रिंग w पढ़ता है और अगले बिट पर पैसा लगाता है। यह अपने पैसे के कुछ अंश पर शर्त लगाता है कि अगला बिट 0 होगा, और उसके बाद का शेष पैसा होगा कि अगला बिट 1 होगा। d उस पैसे को दोगुना कर देता है जो वास्तव में हुआ था, और यह बाकी को खो देता है। d(w) वह राशि है जो स्ट्रिंग w को देखने के बाद उसके पास होती है। चूँकि स्ट्रिंग w को देखने के बाद लगाई गई बेट की गणना d(w), d(w0), और d(w1) के मानों से की जा सकती है, इसके पास मौजूद धनराशि की गणना करना बेट की गणना करने के बराबर है। ज़रेबंद लक्षण वर्णन कहता है कि किसी भी कंप्यूटर द्वारा लागू की जाने वाली कोई भी सट्टेबाजी की रणनीति (रचनात्मक रणनीतियों के कमजोर अर्थों में भी, जो आवश्यक रूप से संगणनीय नहीं हैं) एक यादृच्छिक अनुक्रम पर पैसे की सट्टेबाजी कर सकती है।

मार्टिन-लोफ यादृच्छिक अनुक्रमों के गुण और उदाहरण

• चैटिन स्थिरांक|चैटिन की रुकने की संभावना Ω एक यादृच्छिक अनुक्रम का एक उदाहरण है।
• रैंड^c (रैंड का पूरक (सेट सिद्धांत)) सभी अनंत अनुक्रमों के सेट का एक माप (गणित) 0 सबसेट है। यह इस तथ्य से निहित है कि प्रत्येक रचनात्मक शून्य कवर में माप 0 सेट शामिल होता है, केवल गणनीय रचनात्मक शून्य कवर होते हैं, और माप 0 सेट के एक गणनीय संघ में माप 0 होता है। इसका तात्पर्य है कि RAND एक माप 1 सेट का सबसेट है सभी अनंत क्रम।
• हर यादृच्छिक क्रम सामान्य संख्या है।
• रैंड का एक रचनात्मक अशक्त आवरण है^सी. इसका मतलब यह है कि यादृच्छिकता के लिए सभी प्रभावी परीक्षण (अर्थात्, रचनात्मक नल कवर), एक मायने में, यादृच्छिकता के लिए इस सार्वभौमिक परीक्षण द्वारा सम्मिलित हैं, क्योंकि कोई भी अनुक्रम जो यादृच्छिकता के लिए इस एकल परीक्षा को पास करता है, यादृच्छिकता के लिए सभी परीक्षणों को पारित करेगा। (मार्टिन-लोफ 1966)
• एक सार्वभौमिक रचनात्मक मार्टिंगेल 'डी' है। यह मार्टिंगेल इस मायने में सार्वभौमिक है कि, किसी रचनात्मक मार्टिंगेल डी को देखते हुए, यदि डी अनुक्रम पर सफल होता है, तो 'डी' उस क्रम पर भी सफल होता है। इस प्रकार, रैंड में हर क्रम पर 'डी' सफल होता है^c (लेकिन, चूंकि d रचनात्मक है, यह RAND में बिना किसी क्रम के सफल होता है)। (श्नोर 1971)
• वर्ग रैंड एक है $\Sigma _{2}^{0}$ कैंटर स्पेस का सबसेट, जहां $\Sigma _{2}^{0}$ अंकगणितीय पदानुक्रम के दूसरे स्तर को संदर्भित करता है। ऐसा इसलिए है क्योंकि एक अनुक्रम S RAND में है यदि और केवल यदि सार्वभौमिक प्रभावी अशक्त आवरण में कुछ खुला सेट है जिसमें S शामिल नहीं है; इस गुण को a द्वारा परिभाषित किया जा सकता है $\Sigma _{2}^{0}$ सूत्र।
• एक यादृच्छिक क्रम है जो है $\Delta _{2}^{0}$, अर्थात्, हॉल्टिंग समस्या के लिए एक ऑरेकल के सापेक्ष संगणनीय। (Schnorr 1971) Chaitin's Chaitin's constant|Ω ऐसे अनुक्रम का एक उदाहरण है।
• कोई यादृच्छिक अनुक्रम निर्णायकता (तर्क), संगणनीय रूप से गणना योग्य, या संगणनीय रूप से गणना योग्य | सह-गणना योग्य-गणनीय नहीं है। चूंकि ये इसके अनुरूप हैं $\Delta _{1}^{0}$, $\Sigma _{1}^{0}$, और $\Pi _{1}^{0}$ अंकगणितीय पदानुक्रम के स्तर, इसका मतलब है कि $\Delta _{2}^{0}$ अंकगणितीय पदानुक्रम में सबसे निचला स्तर है जहाँ यादृच्छिक क्रम पाया जा सकता है।
• हर क्रम कुछ यादृच्छिक अनुक्रम के लिए ट्यूरिंग रिड्यूसिबल है। (कुचेरा 1985/1989, पेटर जीएसी। जीएसी 1986)। इस प्रकार मनमाने ढंग से उच्च ट्यूरिंग डिग्री के यादृच्छिक क्रम हैं।

सापेक्ष यादृच्छिकता

जैसा कि मार्टिन-लोफ यादृच्छिक अनुक्रम की प्रत्येक समतुल्य परिभाषा कुछ ट्यूरिंग मशीन द्वारा गणना योग्य है, पर आधारित है, कोई स्वाभाविक रूप से पूछ सकता है कि ट्यूरिंग ऑरेकल मशीन द्वारा गणना योग्य क्या है। एक निश्चित ओरेकल ए के लिए, एक अनुक्रम बी जो न केवल यादृच्छिक है बल्कि वास्तव में, ए के सापेक्ष संगणनीयता के लिए समकक्ष परिभाषाओं को संतुष्ट करता है (उदाहरण के लिए, कोई मार्टिंगेल जो ऑरैकल ए के सापेक्ष रचनात्मक है, बी पर सफल होता है) को यादृच्छिक रिश्तेदार कहा जाता है ए के लिए। दो अनुक्रम, जबकि स्वयं यादृच्छिक होते हैं, उनमें बहुत समान जानकारी हो सकती है, और इसलिए कोई भी दूसरे के सापेक्ष यादृच्छिक नहीं होगा। किसी भी समय एक अनुक्रम से दूसरे अनुक्रम में ट्यूरिंग कमी होती है, दूसरा क्रम पहले के सापेक्ष यादृच्छिक नहीं हो सकता है, जैसे कि गणनीय अनुक्रम स्वयं गैर-यादृच्छिक होते हैं; विशेष रूप से, इसका अर्थ है कि चैटिन का स्थिरांक|चैटिन का Ω हॉल्टिंग समस्या के सापेक्ष यादृच्छिक नहीं है।

सापेक्ष यादृच्छिकता से संबंधित एक महत्वपूर्ण परिणाम मिचेल वैन लैंबलजेन प्रमेय है, जिसमें कहा गया है कि यदि सी ए और बी से बना अनुक्रम है, ए के पहले बिट को इंटरलीविंग करके, बी का पहला बिट, ए का दूसरा बिट, ए का दूसरा बिट बी, और इसी तरह, फिर सी एल्गोरिदमिक रूप से यादृच्छिक है अगर और केवल अगर ए एल्गोरिदमिक रूप से यादृच्छिक है, और बी एल्गोरिदमिक रूप से ए के सापेक्ष यादृच्छिक है। एक निकट संबंधी परिणाम यह है कि यदि ए और बी दोनों स्वयं यादृच्छिक हैं, तो ए यादृच्छिक सापेक्ष है बी अगर और केवल अगर बी ए के सापेक्ष यादृच्छिक है।

मार्टिन-लोफ यादृच्छिकता से अधिक मजबूत

सापेक्ष यादृच्छिकता हमें पहली धारणा देती है जो मार्टिन-लोफ यादृच्छिकता से अधिक मजबूत है, जो कि कुछ निश्चित ऑरेकल ए के सापेक्ष यादृच्छिकता है। किसी भी ऑरेकल के लिए, यह कम से कम उतना ही मजबूत है, और अधिकांश ऑरेकल के लिए, यह सख्ती से मजबूत है, क्योंकि वहाँ होगा मार्टिन-लोफ रैंडम सीक्वेंस बनें जो कि ऑरेकल ए के सापेक्ष रैंडम नहीं हैं। महत्वपूर्ण ऑरेकल को अक्सर हॉल्टिंग प्रॉब्लम माना जाता है, $\emptyset '$, और nth जंप ऑरेकल, $\emptyset ^{(n)}$, क्योंकि ये दैवज्ञ विशिष्ट प्रश्नों का उत्तर देने में सक्षम हैं जो स्वाभाविक रूप से उत्पन्न होते हैं। एक क्रम जो ऑरेकल के सापेक्ष यादृच्छिक है $\emptyset ^{(n-1)}$ एन-यादृच्छिक कहा जाता है; एक अनुक्रम 1-यादृच्छिक है, इसलिए, अगर और केवल अगर यह मार्टिन-लोफ यादृच्छिक है। एक अनुक्रम जो प्रत्येक n के लिए n-यादृच्छिक होता है, अंकगणितीय रूप से यादृच्छिक कहलाता है। अधिक जटिल गुणों पर विचार करते समय कभी-कभी एन-यादृच्छिक अनुक्रम उत्पन्न होते हैं। उदाहरण के लिए, केवल गिने-चुने ही बहुत से हैं $\Delta _{2}^{0}$ सेट, इसलिए कोई सोच सकता है कि ये गैर-यादृच्छिक होना चाहिए। हालांकि, हॉल्टिंग प्रायिकता चैटिन का स्थिरांक|Ω है $\Delta _{2}^{0}$ और 1-यादृच्छिक; यह 2-यादृच्छिकता तक पहुँचने के बाद ही होता है कि एक यादृच्छिक सेट होना असंभव है $\Delta _{2}^{0}$.

मार्टिन-लोफ यादृच्छिकता से कमजोर

इसके अतिरिक्त, यादृच्छिकता की कई धारणाएँ हैं जो मार्टिन-लोफ़ यादृच्छिकता से कमज़ोर हैं। इनमें से कुछ कमजोर 1-रैंडमनेस, श्नोरर रैंडमनेस, कंप्यूटेबल रैंडमनेस, आंशिक कंप्यूटेबल रैंडमनेस हैं। योंगगे वांग ने दिखाया कि Schnorr यादृच्छिकता संगणनीय यादृच्छिकता से भिन्न है। इसके अतिरिक्त, कोल्मोगोरोव-लवलैंड यादृच्छिकता को मार्टिन-लोफ यादृच्छिकता से अधिक मजबूत नहीं माना जाता है, लेकिन यह ज्ञात नहीं है कि यह वास्तव में कमजोर है या नहीं। यादृच्छिकता स्पेक्ट्रम के विपरीत छोर पर के-तुच्छ सेट की धारणा है। ये सेट एंटी-रैंडम हैं क्योंकि सभी प्रारंभिक खंड लघुगणकीय रूप से संकुचित होते हैं (अर्थात, $K(w)\leq K(|w|)+b$ प्रत्येक प्रारंभिक खंड w के लिए), लेकिन वे गणना योग्य नहीं हैं।

यह भी देखें

• यादृच्छिक क्रम
• ग्रेगरी चैटिन
• स्टोकेस्टिक्स
• मोंटे कार्लो विधि
• के-तुच्छ सेट
• सार्वभौमिकता संभावना
• सांख्यिकीय यादृच्छिकता

आगे की पढाई

• Downey, Rod; Hirschfeldt, Denis R.; Nies, André; Terwijn, Sebastiaan A. (2006). "Calibrating Randomness". The Bulletin of Symbolic Logic. 12 (3/4): 411–491. CiteSeerX 10.1.1.135.4162. doi:10.2178/bsl/1154698741. Archived from the original on 2016-02-02.
• Gács, Péter (1986). "Every sequence is reducible to a random one" (PDF). Information and Control. 70 (2/3): 186–192. doi:10.1016/s0019-9958(86)80004-3.
• Kučera, A. (1985). "Measure, Π⁰
  ₁-classes and complete extensions of PA". Recursion Theory Week. Lecture Notes in Mathematics. Vol. 1141. Springer-Verlag. pp. 245–259. doi:10.1007/BFb0076224. ISBN 978-3-540-39596-6.

• Kučera, A. (1989). "On the use of diagonally nonrecursive functions". Studies in Logic and the Foundations of Mathematics. Vol. 129. North-Holland. pp. 219–239.

• Levin, L. (1973). "On the notion of a random sequence". Soviet Mathematics - Doklady. 14: 1413–1416.

• Li, M.; Vitanyi, P. M. B. (1997). An Introduction to Kolmogorov Complexity and its Applications (Second ed.). Berlin: Springer-Verlag.

• Martin-Löf, P. (1966). "The definition of random sequences". Information and Control. 9 (6): 602–619. doi:10.1016/s0019-9958(66)80018-9.
• Nies, André (2009). Computability and randomness. Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.

• Schnorr, C. P. (1971). "A unified approach to the definition of a random sequence". Mathematical Systems Theory. 5 (3): 246–258. doi:10.1007/BF01694181. S2CID 8931514.

• Schnorr, Claus P. (1973). "Process complexity and effective random tests". Journal of Computer and System Sciences. 7 (4): 376–388. doi:10.1016/s0022-0000(73)80030-3.

• Chaitin, Gregory J. (1969). "On the Length of Programs for Computing Finite Binary Sequences: Statistical Considerations". Journal of the ACM. 16 (1): 145–159. doi:10.1145/321495.321506. S2CID 8209877.

• Ville, J. (1939). Etude critique de la notion de collectif. Paris: Gauthier-Villars.