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

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

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

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

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

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

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

इतिहास

एक यादृच्छिक अनुक्रम की प्रथम उपयुक्त परिभाषा 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.