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

"एल्गोरिथम यादृच्छिकता" redirects here. Not to be confused with यादृच्छिक एल्गोरिदम.

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

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

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

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

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

इतिहास

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

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

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

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

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

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

• रचनात्मक शून्य आवरण (मार्टिन-लोफ 1966): यह मार्टिन-लोफ की मूल परिभाषा है। परिमित द्विचर शृंखला w के लिए हम C_w को w माध्यम से उत्पन्न बेलन को निरूपित करने देते हैं। यह w से प्रारंभ होने वाले समस्त अनंत अनुक्रमों का समुच्चय है, जो कैंटर अंतराल में मूल विवृत समुच्चय है। w के माध्यम से उत्पन्न बेलन का उत्पाद माप (गणित) μ(C_w) 2^−|w| के रूप में परिभाषित किया गया है। प्रगायक अंतराल का प्रत्येक विवृत उपसमुच्चय असंयुक्त मूलभूत विवृत समुच्चय के गणनीय अनुक्रम का संघ है, और विवृत समुच्चय का माप ऐसे किसी भी अनुक्रम के उपायों का योग है। प्रभावी विवृत समुच्चय विवृत समुच्चयों है जो द्विचर शृंखला के पुनरावर्ती गणना योग्य अनुक्रम के माध्यम से निर्धारित मूलभूत विवृत समुच्चय के अनुक्रम का संघ है। रचनात्मक शून्य आवरण या प्रभावी माप 0 समुच्चय, प्रभावी विवृत समुच्चयों का पुनरावर्ती रूप से गणना योग्य अनुक्रम ^{$U_{i}$ है, जैसे कि प्रत्येक प्राकृतिक संख्या के लिए $U_{i+1}\subseteq U_{i}$ और $\mu (U_{i})\leq 2^{-i}$ एवं i.प्रत्येक प्रभावी शून्य आवरण माप 0 का $G_{\delta }$ समुच्चय निर्धारित करता है, अर्थात् समुच्चय $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 का संयोजन है। इसे निष्पक्षता की स्थिति कहा जाता है: यदि मार्टिंगेल को शर्त की रणनीति के रूप में देखा जाता है, तब उपरोक्त शर्त के लिए आवश्यक है कि शर्त उचित बाधाओं के विरुद होनी चाहिए। मार्टिंगेल डी को अनुक्रम S पर 'सफल' माना जाता है यदि $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ जिस स्थान पर $S\upharpoonright n$ S के पूर्व 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),$ समस्त धनात्मक पूर्णांक के लिए t है
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 होता है। इसका तात्पर्य है कि रैंड समस्त अनंत क्रम के समुच्चय का माप 1 उप-समुच्चय है।
• प्रत्येक यादृच्छिक क्रम सामान्य संख्या है।
• रैंड^c का रचनात्मक अशक्त आवरण है। इसका कारण यह है कि यादृच्छिकता के लिए समस्त प्रभावी परीक्षण (अर्थात्, रचनात्मक शून्य आवरण), एक रूप में, यादृच्छिकता के लिए इस सार्वभौमिक परीक्षण के माध्यम से सम्मिलित हैं, क्योंकि कोई भी अनुक्रम जो यादृच्छिकता के लिए इस एकल परीक्षा को उत्तीर्ण करता है, यादृच्छिकता के लिए समस्त परीक्षणों को पारित करेगा। (मार्टिन-लोफ 1966)
• एक सार्वभौमिक रचनात्मक मार्टिंगेल 'डी' है। यह मार्टिंगेल इस रूप में सार्वभौमिक है कि, किसी रचनात्मक मार्टिंगेल डी को देखते हुए, यदि d अनुक्रम पर सफल होता है, तब 'd' उस क्रम पर भी सफल होता है। इस प्रकार, रैंड में प्रत्येक क्रम पर 'd' सफल होता है^c (किन्तु, चूंकि d रचनात्मक है, यह रैंड में बिना किसी क्रम के सफल होता है)। (श्नोर 1971)
• वर्ग रैंड , कैंटर अंतराल का $\Sigma _{2}^{0}$ उपसमुच्चय है जिस स्थान पर $\Sigma _{2}^{0}$ अंकगणितीय पदानुक्रम के दूसरे स्तर को संदर्भित करता है। ऐसा इसलिए है क्योंकि अनुक्रम S रैंड में है और मात्र यदि सार्वभौमिक प्रभावी अशक्त आवरण में कुछ विवृत समुच्चय है जिसमें S सम्मिलित नहीं है; इस गुण को $\Sigma _{2}^{0}$ सूत्र के माध्यम से परिभाषित किया जा सकता है।
• एक यादृच्छिक क्रम है जो $\Delta _{2}^{0}$ है, अर्थात्, स्थिरांक समस्या के लिए दैवज्ञ के सापेक्ष गणना योग्य है।। (श्नोरर 1971) चैतीन Ω ऐसे अनुक्रम का उदाहरण है।
• कोई यादृच्छिक अनुक्रम निर्णायकता (तर्क), संगणनीय रूप से गणना योग्य, या सह-गणना योग्य नहीं है। चूँकि यह अंकगणितीय पदानुक्रम के $\Delta _{1}^{0}$, $\Sigma _{1}^{0}$, और $\Pi _{1}^{0}$ स्तरों के अनुरूप हैं, इसका अर्थ है कि $\Delta _{2}^{0}$ अंकगणितीय पदानुक्रम में सबसे निचला स्तर है जिस स्थान पर यादृच्छिक अनुक्रम प्राप्त करे जा सकते हैं।
• प्रत्येक क्रम कुछ यादृच्छिक अनुक्रम के लिए परिगणन रूपांतरित है। (कुचेरा 1985/1989, पेटर जीएसी। जीएसी 1986)। इस प्रकार इच्छानुसार से उच्च परिगणन उपाधि के यादृच्छिक क्रम हैं।

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

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

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

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

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

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

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

यह भी देखें

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

आगे की पढाई

• 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.