โดยสัญชาตญาณแล้วลำดับสุ่มเชิงอัลกอริทึม (หรือลำดับสุ่ม ) คือลำดับของตัวเลขไบนารีที่ดูเหมือนสุ่มสำหรับอัลกอริทึมใดๆ ที่ทำงานบนเครื่องทัวริงสากล (ไม่ว่าจะมีคำนำหน้าหรือไม่ก็ตาม) แนวคิดนี้สามารถนำไปประยุกต์ใช้ในทำนองเดียวกันกับลำดับบนตัวอักษรจำกัดใดๆ (เช่น ตัวเลขทศนิยม) ลำดับสุ่มเป็นหัวข้อสำคัญในการศึกษาทฤษฎีสารสนเทศเชิงอัลกอริทึม

ในทฤษฎีความน่าจะเป็นเชิงการวัดซึ่งนำเสนอโดยAndrey Kolmogorovในปี 1933 ไม่มีสิ่งใดที่เรียกว่าลำดับสุ่ม ตัวอย่างเช่น ลองพิจารณาการโยนเหรียญที่ยุติธรรมเป็นจำนวนครั้งอนันต์ ลำดับใดๆ ก็ตาม ไม่ว่าจะเป็นหรือมีโอกาสเกิดขึ้นเท่ากับศูนย์อย่างแน่นอน ไม่มีวิธีใดที่จะกล่าวได้ว่าลำดับหนึ่ง "สุ่มมากกว่า" อีกลำดับหนึ่ง โดยใช้ภาษาของทฤษฎีความน่าจะเป็นเชิงการวัด อย่างไรก็ตาม เป็นที่ชัดเจนโดยสัญชาตญาณว่าดูเหมือนจะสุ่มมากกว่าทฤษฎีความสุ่มเชิงอัลกอริทึมได้ทำให้สัญชาตญาณนี้เป็นรูปธรรม ${\displaystyle 0000\dots }$${\displaystyle 011010\dots }$${\displaystyle 011010\dots }$${\displaystyle 0000\dots }$

เนื่องจากมีการพิจารณาอัลกอริทึมประเภทต่างๆ มากมาย ตั้งแต่อัลกอริทึมที่มีข้อจำกัดเฉพาะเกี่ยวกับเวลาในการทำงาน ไปจนถึงอัลกอริทึมที่อาจตั้งคำถามกับเครื่องออราเคิลจึงมีแนวคิดเกี่ยวกับความสุ่มที่แตกต่างกัน ความสุ่มที่พบได้บ่อยที่สุดคือความสุ่มแบบมาร์ติน-โลฟ ( ความสุ่มแบบ Kหรือความสุ่มแบบ 1 ) แต่ก็ยังมีรูปแบบของความสุ่มที่แข็งแกร่งกว่าและอ่อนกว่าอยู่ด้วย เมื่อใช้คำว่า "สุ่มเชิงอัลกอริทึม" เพื่ออ้างถึงลำดับเดี่ยว (จำกัดหรืออนันต์) เฉพาะโดยไม่มีการชี้แจงเพิ่มเติม มักจะหมายถึง "ไม่สามารถบีบอัดได้" หรือในกรณีที่ลำดับเป็นอนันต์และมีคำนำหน้าว่าสุ่มเชิงอัลกอริทึม (เช่น ไม่สามารถบีบอัดได้แบบ K) จะเรียกว่า "สุ่มแบบมาร์ติน-โลฟ-ไชติน"

นับตั้งแต่เริ่มแรก ความสุ่มแบบมาร์ติน-โลฟได้รับการพิสูจน์แล้วว่าสามารถอธิบายได้หลายรูปแบบที่เทียบเท่ากัน ไม่ว่าจะเป็นในแง่ของการบีบอัดการทดสอบความสุ่ม และการพนันซึ่งแต่ละรูปแบบนั้นดูไม่เหมือนกับนิยามดั้งเดิม แต่ล้วนสอดคล้องกับความเข้าใจโดยสัญชาตญาณของเราเกี่ยวกับคุณสมบัติที่ลำดับสุ่มควรมี กล่าวคือ ลำดับสุ่มควรบีบอัดไม่ได้ ควรผ่านการทดสอบทางสถิติสำหรับความสุ่ม และควรยากที่จะทำเงิน จาก การพนันกับลำดับเหล่านั้น การมีอยู่ของนิยามความสุ่มแบบมาร์ติน-โลฟหลายรูปแบบ และความเสถียรของนิยามเหล่านี้ภายใต้แบบจำลองการคำนวณที่แตกต่างกัน เป็นหลักฐานที่แสดงให้เห็นว่าความสุ่มแบบมาร์ติน-โลฟนั้นเป็นธรรมชาติ ไม่ใช่ผลจากความบังเอิญของแบบจำลองเฉพาะของมาร์ติน-โลฟ

สิ่งสำคัญคือต้องแยกแยะความแตกต่างระหว่างความสุ่มเชิงอัลกอริทึมและความสุ่มเชิงสุ่มแบบไม่แน่นอน ต่างจากความสุ่มเชิงอัลกอริทึมซึ่งนิยามไว้สำหรับกระบวนการที่คำนวณได้ (และดังนั้นจึงเป็นกระบวนการที่กำหนดได้) ความสุ่มเชิงสุ่มแบบไม่แน่นอนมักถูกกล่าวว่าเป็นคุณสมบัติของลำดับที่ทราบล่วงหน้าว่าถูกสร้างขึ้นโดย (หรือเป็นผลลัพธ์ของ) กระบวนการสุ่มแบบไม่แน่นอนที่มีการแจกแจงเหมือนกันและเป็น อิสระต่อกัน

เนื่องจากลำดับอนันต์ของเลขฐานสองสามารถระบุได้ว่าเป็นจำนวนจริงในช่วงหน่วย ดังนั้นลำดับเลขฐานสองแบบสุ่มจึงมักถูกเรียกว่า(ในเชิงอัลกอริทึม) จำนวนจริงแบบสุ่มนอกจากนี้ ลำดับเลขฐานสองอนันต์ยังสอดคล้องกับฟังก์ชันลักษณะเฉพาะของเซตของจำนวนธรรมชาติ ดังนั้นลำดับเหล่านั้นจึงอาจถูกมองว่าเป็นเซตของจำนวนธรรมชาติได้

กลุ่มของลำดับสุ่ม (ไบนารี) ของ Martin-Löf ทั้งหมดจะถูกแทนด้วย RAND หรือ MLR

ริชาร์ด ฟอน มิเซสได้วางกรอบแนวคิดเรื่องการทดสอบความสุ่มเพื่อกำหนดลำดับสุ่มว่าเป็นลำดับที่ผ่านการทดสอบความสุ่มทั้งหมด เขาได้นิยาม "กลุ่ม" ( kollektiv ) ว่าเป็นสตริงไบนารีอนันต์ที่กำหนดขึ้นโดยมีเงื่อนไขว่า ${\displaystyle x_{1:\infty }}$

• มีข้อจำกัดอยู่${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{i}=p\in (0,1)}$
• สำหรับกฎใดๆ ที่ "ยอมรับได้" ซึ่งเลือกเอาลำดับย่อยอนันต์ออกมาจากสตริงนั้น เราก็ยังคงมีเขาเรียกหลักการนี้ว่า " ความเป็นไปไม่ได้ของระบบการพนัน "${\displaystyle (x_{m_{i}})_{i}}$${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p}$

ในการเลือกส่วนย่อยของลำดับให้เลือกฟังก์ชันไบนารีหนึ่งฟังก์ชันก่อนโดยที่เมื่อกำหนดสตริงไบนารีใดๆฟังก์ชันนั้นจะให้ผลลัพธ์เป็น 0 หรือ 1 ถ้าให้ผลลัพธ์เป็น 1 เราจะเพิ่มส่วนย่อยนั้นเข้าไปในลำดับ มิฉะนั้นเราจะดำเนินการต่อไป ในคำจำกัดความนี้ กฎที่ยอมรับได้บางข้ออาจละเว้นไปตลอดกาลสำหรับลำดับบางลำดับ และดังนั้นจึงไม่สามารถเลือกส่วนย่อยอนันต์ได้ เราจะพิจารณาเฉพาะกฎที่เลือกส่วนย่อยอนันต์ได้เท่านั้น ${\displaystyle \phi }$${\displaystyle x_{1:k}}$${\displaystyle x_{k+1}}$

กล่าวอีกนัยหนึ่ง สตริงไบนารีอนันต์แต่ละสตริงเปรียบเสมือนเกมโยนเหรียญ และกฎที่ยอมรับได้คือวิธีการที่นักพนันใช้ตัดสินใจว่าจะวางเดิมพันเมื่อใด กลุ่มผู้เล่นก็เปรียบเสมือนเกมโยนเหรียญที่ไม่มีทางที่นักพนันคนใดคนหนึ่งจะทำได้ดีกว่าอีกคนในระยะยาว กล่าวคือ ไม่มีระบบการพนันใดที่ใช้ได้ผลกับเกมนี้

นิยามนี้เป็นการขยายความจากอักษรไบนารีไปสู่อักษรนับได้:

• ความถี่ของตัวอักษรแต่ละตัวจะลู่เข้าสู่ค่าจำกัดที่มากกว่าศูนย์
• สำหรับกฎที่ "ยอมรับได้" ใดๆ ที่เลือกเอาลำดับย่อยอนันต์ออกมาจากสตริง ความถี่ของตัวอักษรแต่ละตัวในลำดับย่อยนั้นจะยังคงลู่เข้าสู่ค่าจำกัดเดียวกันเสมอ${\displaystyle (x_{m_{i}})_{i}}$

โดยปกติกฎที่ยอมรับได้จะถูกกำหนดให้เป็นกฎที่คำนวณได้โดยเครื่องจักรทัวริง และเราต้องการด้วยเหตุนี้ เราจึงมีลำดับสุ่ม Mises–Wald–Churchนี่ไม่ใช่ข้อจำกัด เนื่องจากเมื่อกำหนดลำดับที่มีเราสามารถสร้างลำดับสุ่มที่มี ที่คำนวณได้อื่นๆ ได้[ ^{1 ] (}ในที่นี้ "Church" หมายถึงAlonzo Churchซึ่งบทความปี 1940 ของเขาเสนอให้ใช้กฎที่คำนวณได้โดยเครื่องจักรทัวริง^{[ 2 ]} ) ${\displaystyle p=1/2}$${\displaystyle p=1/2}$${\displaystyle p\in (0,1)}$

อย่างไรก็ตาม พบว่าคำจำกัดความนี้ไม่แข็งแกร่งพอ โดยสัญชาตญาณแล้ว ค่าเฉลี่ยระยะยาวของลำดับสุ่มควรจะแกว่งไปมาทั้งสองด้านของเช่นเดียวกับการเดินสุ่มที่ควรจะข้ามจุดกำเนิดเป็นจำนวนครั้งอนันต์ อย่างไรก็ตามJean Villeแสดงให้เห็นว่า แม้จะมีกฎจำนวนนับได้ ก็ยังมีลำดับไบนารีที่มีแนวโน้มไปสู่เศษส่วนของหนึ่ง แต่สำหรับคำนำหน้าจำกัดทุกคำ เศษส่วนของหนึ่งจะน้อยกว่า^{[ 4 ]}${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

โครงสร้างของวิลล์ชี้ให้เห็นว่าความหมายของความสุ่มแบบมิเซส-วาลด์-เชิร์ชนั้นไม่ดีพอ เพราะลำดับสุ่มบางลำดับไม่เป็นไปตามกฎความสุ่มบางข้อ ตัวอย่างเช่น โครงสร้างของวิลล์ไม่เป็นไปตามกฎข้อหนึ่งของลอการิทึมแบบวนซ้ำ กล่าว คือโดยทั่วไปแล้ว เราสามารถแก้ไขปัญหานี้ได้โดยการกำหนดให้ลำดับต้องเป็นไปตามกฎความสุ่มที่เป็นไปได้ทั้งหมด โดยที่ "กฎความสุ่ม" คือคุณสมบัติที่ลำดับทั้งหมดเป็นไปตามนั้นด้วยความน่าจะเป็น 1 อย่างไรก็ตาม สำหรับลำดับอนันต์แต่ละลำดับเรามีกฎความสุ่มที่ ซึ่งนำไปสู่ข้อสรุปว่าไม่มีลำดับสุ่มใดๆ $${\displaystyle \limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1}$$${\displaystyle y_{1:\infty }\in 2^{\mathbb {N} }}$${\displaystyle x_{1:\infty }\neq y_{1:\infty }}$

( ตามแบบ Martin-Löf , 1966) ^{[ 6 ]}ได้นิยาม "ความสุ่มแบบ Martin-Löf" โดยอนุญาตเฉพาะกฎของความสุ่มที่สามารถคำนวณได้ด้วย Turing เท่านั้น กล่าวอีกนัยหนึ่ง ลำดับจะสุ่มก็ต่อเมื่อผ่านการทดสอบความสุ่มที่สามารถคำนวณได้ด้วย Turing ทั้งหมด

วิทยานิพนธ์ที่ว่าคำจำกัดความของความสุ่มแบบ Martin-Löf นั้น "จับ" แนวคิดเชิงสัญชาตญาณของความสุ่มได้อย่างถูกต้องนั้น เรียกว่าวิทยานิพนธ์ Martin-Löf–Chaitinซึ่งมีความคล้ายคลึงกับวิทยานิพนธ์Church–Turing อยู่บ้าง ^{[ 7 ]}

นิยามดั้งเดิมของลำดับสุ่มที่เสนอโดย Martin-Löf นั้นอยู่บนพื้นฐานของการครอบคลุมศูนย์เชิงสร้างสรรค์ (constructive null covers) โดยเขาให้นิยามว่าลำดับจะเป็นแบบสุ่มหากลำดับนั้นไม่ถูกบรรจุอยู่ในการครอบคลุมศูนย์ดังกล่าวGregory Chaitin , Leonid LevinและClaus Peter Schnorrได้พิสูจน์ลักษณะเฉพาะในแง่ของ ความซับซ้อนเชิง อัลกอริทึม (algorithmic complexity ) โดยระบุว่า ลำดับจะเป็นแบบสุ่มหากมีการจำกัดค่าคงที่ (uniform bound) สำหรับความสามารถในการบีบอัดของส่วนเริ่มต้น (initial segments) Schnorr ได้ให้นิยามที่เทียบเท่ากันอีกแบบหนึ่งในแง่ของมาร์ติงเกล (martingales ) หนังสือ An Introduction to Kolmogorov Complexity and Its Applicationsของ Li และ Vitanyi เป็นหนังสือแนะนำมาตรฐานเกี่ยวกับแนวคิดเหล่านี้

• ความซับซ้อนเชิงอัลกอริทึม (Chaitin 1969, Schnorr 1973, Levin 1973): ความซับซ้อนเชิงอัลกอริทึม (หรือที่รู้จักกันในชื่อความซับซ้อนของ Kolmogorov (แบบไม่มีคำนำหน้า) หรือความซับซ้อนของขนาดโปรแกรม) สามารถคิดได้ว่าเป็นขอบเขตล่างของการบีบอัดเชิงอัลกอริทึมของลำดับจำกัด (ของอักขระหรือตัวเลขไบนารี) โดยจะกำหนด จำนวนธรรมชาติK(w) ให้กับลำดับ w แต่ละลำดับ ซึ่งโดยสัญชาตญาณแล้วจะวัดความยาวขั้นต่ำของโปรแกรมคอมพิวเตอร์ (ที่เขียนด้วยภาษาโปรแกรมที่กำหนดไว้) ที่ไม่รับอินพุตและจะส่งออกwเมื่อรัน เมื่อกำหนดจำนวนธรรมชาติcและลำดับwเราจะกล่าวว่าw นั้นบีบอัดไม่ได้cถ้า.${\displaystyle K(w)\geq |w|-c}$

ลำดับอนันต์ S เป็นลำดับสุ่มแบบ Martin-Löf ก็ต่อเมื่อมีค่าคงที่ c ที่ทำให้คำนำหน้าจำกัด ทั้งหมด ของ S เป็น c -incompressible กล่าวโดยย่อคือ${\displaystyle K(w)\geq |w|-O(1)}$ .

• การปกคลุมศูนย์เชิงสร้างสรรค์ (Martin-Löf 1966): นี่คือคำจำกัดความดั้งเดิมของ Martin-Löf สำหรับสตริงไบนารีจำกัดwเราให้C _wแทนทรงกระบอกที่สร้างโดยwนี่คือเซตของลำดับอนันต์ทั้งหมดที่เริ่มต้นด้วยwซึ่งเป็นเซตเปิด พื้นฐาน ในปริภูมิแคนเตอร์ผลคูณของการวัด μ( C _w ) ของทรงกระบอกที่สร้างโดยwถูกกำหนดให้เป็น 2 ^{−| w |}เซตย่อยเปิดทุกเซตของปริภูมิแคนเตอร์คือการรวมกันของลำดับที่นับได้ของเซตเปิดพื้นฐานที่ไม่ซ้ำกัน และการวัดของเซตเปิดคือผลรวมของการวัดของลำดับดังกล่าวเซตเปิดที่มีประสิทธิภาพคือเซตเปิดที่เป็นการรวมกันของลำดับของเซตเปิดพื้นฐานที่กำหนดโดย ลำดับ ที่นับได้แบบเวียนซ้ำของสตริงไบนารี การปกคลุม ศูนย์เชิงสร้างสรรค์หรือเซตที่มีการวัดที่มีประสิทธิภาพเป็น 0 คือลำดับที่นับได้แบบเวียนซ้ำของเซตเปิดที่มีประสิทธิภาพ โดยที่และสำหรับจำนวนธรรมชาติi แต่ละ ตัว การครอบคลุมศูนย์ที่มีประสิทธิภาพทุกรูปแบบจะกำหนดเซตที่มีขนาด 0 ซึ่งก็คือจุดตัดของเซตต่างๆ${\displaystyle U_{i}}$${\displaystyle U_{i+1}\subseteq U_{i}}$${\displaystyle \mu (U_{i})\leq 2^{-i}}$${\displaystyle G_{\delta }}$${\displaystyle U_{i}}$

ลำดับจะถูกนิยามว่าเป็นลำดับสุ่มแบบมาร์ติน-โลฟ (Martin-Löf random) หากลำดับนั้นไม่อยู่ในเซตใดๆ ที่กำหนดโดยการครอบคลุมว่างเชิงสร้างสรรค์ (constructive null cover)${\displaystyle G_{\delta }}$

• มาร์ติงเกลเชิงสร้างสรรค์ (Schnorr 1971): มาร์ติงเกลคือฟังก์ชันที่สำหรับสตริงจำกัดw ทั้งหมด โดยที่คือการต่อกันของสตริงaและbนี่เรียกว่า "เงื่อนไขความยุติธรรม": หากมองมาร์ติงเกลเป็นกลยุทธ์การเดิมพัน เงื่อนไขข้างต้นกำหนดให้ผู้เล่นเดิมพันต้องเล่นกับอัตราต่อรองที่ยุติธรรม มาร์ติงเกลdกล่าวได้ว่าประสบความสำเร็จบนลำดับSถ้าโดยที่ คือบิต n ตัว แรกของSมาร์ติงเกลdเป็นแบบสร้างสรรค์ (หรือที่รู้จักกันในชื่อคำนวณได้แบบอ่อน คำนวณ ได้แบบกึ่งล่าง ) ถ้ามีฟังก์ชันที่คำนวณได้ซึ่งสำหรับสตริงไบนารีจำกัดw ทั้งหมด${\displaystyle d:\{0,1\}^{*}\to [0,\infty )}$${\displaystyle d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2}$${\displaystyle a^{\smallfrown }b}$${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$${\displaystyle S\upharpoonright n}$${\displaystyle {\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }}$

1. ${\displaystyle {\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),}$สำหรับจำนวนเต็มบวกt ทุก ตัว
2. ${\displaystyle \lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).}$

ลำดับจะเป็นลำดับสุ่มแบบมาร์ติน-โลฟก็ต่อเมื่อไม่มีมาร์ติงเกลเชิงสร้างสรรค์ใดประสบความสำเร็จกับลำดับนั้น

ลักษณะเฉพาะของความซับซ้อนของ Kolmogorov สื่อถึงสัญชาตญาณที่ว่าลำดับสุ่มนั้นไม่สามารถบีบอัดได้: ไม่มีคำนำหน้าใดที่สามารถสร้างขึ้นได้จากโปรแกรมที่สั้นกว่าคำนำหน้านั้นมาก

นิยามของชุดคลุมศูนย์ (null cover) สื่อถึงสัญชาตญาณที่ว่าจำนวนจริง สุ่ม ไม่ควรมีคุณสมบัติใดๆ ที่ "ผิดปกติ" แต่ละเซตที่มีมาตรเป็น 0 สามารถคิดได้ว่าเป็นคุณสมบัติที่ผิดปกติ เป็นไปไม่ได้ที่ลำดับจะอยู่ในกลุ่มเซตที่มีมาตรเป็น 0 เพราะแต่ละเซตที่มีจุดเดียวจะมีมาตรเป็น 0 แนวคิดของ Martin-Löf คือการจำกัดนิยามให้เหลือเฉพาะเซตที่มีมาตรเป็น 0 ที่สามารถอธิบายได้อย่างมีประสิทธิภาพ นิยามของชุดคลุมศูนย์ที่มีประสิทธิภาพจะกำหนดกลุ่มเซตที่มีมาตรเป็น 0 ที่สามารถอธิบายได้อย่างมีประสิทธิภาพซึ่งสามารถนับได้ และกำหนดว่าลำดับนั้นเป็นแบบสุ่มหากมันไม่อยู่ในเซตที่มีมาตรเป็น 0 เหล่านั้น เนื่องจากการรวมกันของกลุ่มเซตที่มีมาตรเป็น 0 ที่สามารถนับได้จะมีมาตรเป็น 0 นิยามนี้จึงนำไปสู่ทฤษฎีบททันทีว่ามีเซตของลำดับสุ่มที่มีมาตรเป็น 1 โปรดสังเกตว่า หากเราระบุปริภูมิแคนเตอร์ของลำดับไบนารีกับช่วง [0,1] ของจำนวนจริง มาตรในปริภูมิแคนเตอร์จะสอดคล้องกับมาตรของเลเบส

เซตการวัดที่มีประสิทธิภาพ 0 สามารถตีความได้ว่าเป็นเครื่องจักรทัวริงที่สามารถบอกได้ว่าสตริงไบนารีอนันต์นั้นดูสุ่มหรือไม่ที่ระดับนัยสำคัญทางสถิติเซตนี้คือจุดตัดของเซตที่หดตัวและเนื่องจากแต่ละเซตถูกกำหนดโดยลำดับของคำนำหน้าที่นับได้ เมื่อกำหนดสตริงไบนารีอนันต์ใดๆ หากสตริงนั้นอยู่ในเซต เครื่องจักรทัวริงสามารถตัดสินใจได้ในเวลาจำกัดว่าสตริงนั้นอยู่ในเซตดังนั้นจึงสามารถ "ปฏิเสธสมมติฐานที่ว่าสตริงนั้นสุ่มที่ระดับนัยสำคัญ" ได้ หากเครื่องจักรทัวริงสามารถปฏิเสธสมมติฐานที่ระดับนัยสำคัญทั้งหมดได้ สตริงนั้นก็จะไม่ใช่สตริงสุ่ม สตริงสุ่มคือสตริงที่สำหรับการทดสอบความสุ่มที่คำนวณได้ด้วยเครื่องจักรทัวริงแต่ละครั้ง จะยังคงไม่ถูกปฏิเสธที่ระดับนัยสำคัญบางระดับตลอดไป^{[ 8 ]}${\displaystyle U_{1}\supset U_{2}\supset U_{3}\supset \cdots }$${\displaystyle U_{n}}$${\displaystyle U_{n}}$${\displaystyle U_{n}}$${\displaystyle 2^{-n}}$

แนวคิดของมาร์ติงเกลสื่อถึงสัญชาตญาณที่ว่า ไม่มีกระบวนการใดที่มีประสิทธิภาพที่จะสามารถสร้างรายได้จากการเดิมพันกับลำดับสุ่มได้ มาร์ติงเกลdคือกลยุทธ์การเดิมพันdอ่านสตริงจำกัดwและเดิมพันเงินกับบิตถัดไป มันเดิมพันเงินส่วนหนึ่งว่าบิตถัดไปจะเป็น 0 และส่วนที่เหลือเดิมพันว่าบิตถัดไปจะเป็น 1 dจะเพิ่มเงินที่เดิมพันเป็นสองเท่าในบิตที่เกิดขึ้นจริง และเสียส่วนที่เหลือd ( w ) คือจำนวนเงินที่มันมีหลังจากเห็นสตริงwเนื่องจากสามารถคำนวณเงินเดิมพันหลังจากเห็นสตริงwได้จากค่าd ( w ), d ( w0 ) และd ( w1 ) ดังนั้นการคำนวณจำนวนเงินที่มันมีจึงเทียบเท่ากับการคำนวณเงินเดิมพัน แนวคิดของมาร์ติงเกลกล่าวว่า ไม่มีกลยุทธ์การเดิมพันใดที่สามารถนำไปใช้ได้โดยคอมพิวเตอร์ (แม้ในความหมายที่อ่อนแอของกลยุทธ์เชิงสร้างสรรค์ ซึ่งไม่จำเป็นต้องคำนวณได้ ) ที่จะสามารถสร้างรายได้จากการเดิมพันกับลำดับสุ่มได้

มีมาร์ติงเกลเชิงสร้างสรรค์สากลd อยู่ มาร์ติงเกลนี้เป็นสากลในแง่ที่ว่า เมื่อกำหนดมาร์ติงเกลเชิงสร้างสรรค์d ใดๆ แล้ว ถ้าdประสบความสำเร็จกับลำดับใดๆ แล้วdก็จะประสบความสำเร็จกับลำดับนั้นเช่นกัน ดังนั้นdจึงประสบความสำเร็จกับทุกลำดับใน RAND ^c (แต่เนื่องจากdเป็นมาร์ติงเกลเชิงสร้างสรรค์ มันจึงไม่ประสบความสำเร็จกับลำดับใดๆ ใน RAND) (Schnorr 1971)

มีการครอบคลุมศูนย์เชิงสร้างสรรค์ของ RAND ^cซึ่งหมายความว่าการทดสอบความสุ่มที่มีประสิทธิภาพทั้งหมด (นั่นคือ การครอบคลุมศูนย์เชิงสร้างสรรค์) นั้น ในแง่หนึ่งถูกรวมอยู่ภายใต้ การทดสอบความสุ่ม สากล นี้ เนื่องจากลำดับใดๆ ที่ผ่านการทดสอบความสุ่มเพียงครั้งเดียวนี้ จะผ่านการทดสอบความสุ่มทั้งหมด (Martin-Löf 1966) โดยสัญชาตญาณ การทดสอบความสุ่มสากลนี้กล่าวว่า "ถ้าหากลำดับมีคำนำหน้าที่ยาวขึ้นเรื่อยๆ ซึ่งสามารถบีบอัดได้ดีขึ้นเรื่อยๆ บนเครื่องทัวริงสากลนี้" แล้ว ลำดับนั้นก็ไม่ใช่ลำดับสุ่ม" -- ดูส่วนถัดไป

ภาพร่างโครงสร้าง:แจงนับชุดคลุมศูนย์ที่มีประสิทธิภาพเป็น การแจงนับนี้ก็มีประสิทธิภาพเช่นกัน (แจงนับโดยเครื่องทัวริงสากลที่ดัดแปลงแล้ว) ตอนนี้เรามีชุดคลุมศูนย์ที่มีประสิทธิภาพสากลโดยการทำให้เป็นแนวทแยง: ${\displaystyle ((U_{m,n})_{n})_{m}}$${\displaystyle (\cup _{n}U_{n,n+k+1})_{k}}$

หากลำดับข้อมูลไม่ผ่านการทดสอบความสุ่มเชิงอัลกอริทึม แสดงว่าลำดับข้อมูลนั้นสามารถบีบอัดได้ด้วยอัลกอริทึม ในทางกลับกัน หากลำดับข้อมูลนั้นสามารถบีบอัดได้ด้วยอัลกอริทึม แสดงว่าลำดับข้อมูลนั้นไม่ผ่านการทดสอบความสุ่มเชิงอัลกอริทึม

ภาพร่างโครงสร้าง:สมมติว่าลำดับไม่ผ่านการทดสอบความสุ่ม จากนั้นสามารถบีบอัดได้โดยการแจงนับลำดับทั้งหมดที่ไม่ผ่านการทดสอบตามลำดับตัวอักษร จากนั้นเข้ารหัสตำแหน่งของลำดับในรายการลำดับทั้งหมดดังกล่าว วิธีนี้เรียกว่า "การเข้ารหัสแหล่งที่มาแบบแจงนับ" ^{[ 9 ]}

ในทางกลับกัน หากลำดับนั้นสามารถบีอัดได้ ตามหลักการรังนกพิราบจะมีเพียงเศษส่วนเล็กน้อยมากของลำดับเท่านั้นที่เป็นเช่นนั้น ดังนั้นเราจึงสามารถกำหนดการทดสอบใหม่สำหรับความสุ่มได้โดย "มีการบีอัดโดยเครื่องจักรทัวริงสากลนี้" อนึ่ง นี่คือ การทดสอบ สากลสำหรับความสุ่ม

ตัวอย่างเช่น พิจารณาลำดับไบนารีที่สุ่มมาแบบ IID จากการแจกแจงแบบเบอร์นูลลีหลังจากสุ่มตัวอย่างจำนวนมากเราควรจะได้ลำดับไบนารีที่มีค่าเป็น 1 ประมาณ1 ตัว เราสามารถเขียนโค้ดสำหรับลำดับนี้ได้ดังนี้ "สร้างลำดับไบนารีทั้งหมดที่มีความยาวn และมีค่าเป็น 1 ทั้งหมด จากนั้นสร้างลำดับที่ n ตามลำดับพจนานุกรม" ${\displaystyle N}$${\displaystyle M\approx pN}$${\displaystyle N}$${\displaystyle M}$${\displaystyle i}$

โดยการประมาณค่าของสเตอร์ลิงโดยที่คือฟังก์ชันเอนโทรปีไบนารีดังนั้น จำนวนบิตในคำอธิบายนี้คือเทอมแรกใช้สำหรับการเข้ารหัสคำนำหน้าของตัวเลขและเทอมที่สองใช้สำหรับการเข้ารหัสคำนำหน้าของตัวเลข(ใช้การเข้ารหัสโอเมก้าของอีเลียส ) เทอมที่สามใช้สำหรับการเข้ารหัสคำนำหน้าส่วนที่เหลือของคำอธิบาย เมื่อมีขนาดใหญ่ คำอธิบายนี้จะมีเพียงบิต และดังนั้นจึงสามารถบีบอัดได้ โดยมีอัตราส่วนการบีบอัดโดยเฉพาะอย่างยิ่ง อัตราส่วนการบีบอัดจะเป็นหนึ่งพอดี (บีบอัดไม่ได้) ก็ต่อเมื่อ(ตัวอย่าง 14.2.8 ^{[ 10 ]} ) ${\displaystyle \log _{2}{\binom {N}{pN}}\approx NH(p)}$${\displaystyle H}$$${\displaystyle 2(1+\epsilon )\log _{2}N+(1+\epsilon )NH(p)+O(1)}$$${\displaystyle N}$${\displaystyle M}$${\displaystyle i}$${\displaystyle N}$${\displaystyle \sim H(p)N}$${\displaystyle \sim H(p)}$${\displaystyle p=1/2}$

ลองพิจารณาคาสิโนที่เสนออัตราต่อรองที่เป็นธรรมที่โต๊ะรูเล็ต โต๊ะรูเล็ตจะสร้างลำดับตัวเลขสุ่ม หากลำดับนี้เป็นแบบสุ่มโดยใช้อัลกอริทึม ก็จะไม่มีกลยุทธ์กึ่งคำนวณที่ต่ำกว่าที่จะชนะ ซึ่งหมายความว่าไม่มีกลยุทธ์ที่คำนวณได้ที่จะชนะ นั่นคือ สำหรับอัลกอริทึมการพนันใดๆ ผลตอบแทนลอการิทึมในระยะยาวจะเป็นศูนย์ (ไม่เป็นบวกหรือลบ) ในทางกลับกัน หากลำดับนี้ไม่ใช่แบบสุ่มโดยใช้อัลกอริทึม ก็จะมีกลยุทธ์กึ่งคำนวณที่ต่ำกว่าที่จะชนะ

• ความน่าจะเป็นในการหยุดของ Chaitin (Ω)เป็นตัวอย่างหนึ่งของลำดับสุ่ม
• ลำดับสุ่มทุกชุดไม่สามารถคำนวณได้เสมอไป
• ลำดับสุ่มทุกลำดับเป็นแบบปกติสอดคล้องกับกฎของจำนวนมากและสอดคล้องกับคุณสมบัติที่คำนวณได้ทั้งหมดของ Turing ที่สอดคล้องกับสตรีม IID ของตัวเลขสุ่มแบบสม่ำเสมอ (ทฤษฎีบท 14.5.2 ^{[ 10 ]} )

• RAND ^c ( ส่วนเติมเต็มของ RAND) เป็น เซตย่อยที่ มีมาตรเป็น 0 ของเซตของลำดับอนันต์ทั้งหมด สิ่งนี้บ่งชี้ได้จากข้อเท็จจริงที่ว่า การปกคลุมศูนย์เชิงสร้างสรรค์แต่ละแบบจะปกคลุมเซตที่มีมาตรเป็น 0 มีการปกคลุมศูนย์เชิงสร้างสรรค์เพียงจำนวนนับได้และการรวมกันแบบนับได้ของเซตที่มีมาตรเป็น 0 จะมีมาตรเป็น 0 ซึ่งหมายความว่า RAND เป็นเซตย่อยที่มีมาตรเป็น 1 ของเซตของลำดับอนันต์ทั้งหมด
• คลาส RAND เป็นเซตย่อยของปริภูมิแคนเตอร์ โดยที่หมายถึงระดับที่สองของลำดับชั้นทางเลขคณิตเนื่องจากลำดับSอยู่ใน RAND ก็ต่อเมื่อมีเซตเปิดบางเซตในเซตคลุมศูนย์ที่มีประสิทธิภาพสากลที่ไม่ประกอบด้วยSคุณสมบัตินี้สามารถนิยามได้ด้วยสูตร${\displaystyle \Sigma _{2}^{0}}$${\displaystyle \Sigma _{2}^{0}}$${\displaystyle \Sigma _{2}^{0}}$
• มีลำดับสุ่มอยู่ลำดับหนึ่งซึ่งสามารถคำนวณได้โดยสัมพันธ์กับออราเคิลสำหรับปัญหาการหยุดทำงาน (Schnorr 1971) Ω ของ Chaitin เป็นตัวอย่างหนึ่งของลำดับดังกล่าว${\displaystyle \Delta _{2}^{0}}$
• ไม่มีลำดับสุ่มใดที่สามารถตัดสินได้ แจงนับได้ด้วยการคำนวณหรือแจงนับได้ด้วยการคำนวณร่วมกันเนื่องจากสิ่งเหล่านี้สอดคล้องกับระดับ, , และของลำดับชั้นทางคณิตศาสตร์นั่นหมายความว่าเป็นระดับต่ำสุดในลำดับชั้นทางคณิตศาสตร์ที่สามารถพบลำดับสุ่มได้${\displaystyle \Delta _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle \Delta _{2}^{0}}$
• ลำดับทุกลำดับสามารถลดรูปทัวริงได้เป็นลำดับสุ่มบางลำดับ (Kučera 1985/1989, Gács 1986) ดังนั้นจึงมีลำดับสุ่มที่มีดีกรีทัวริง สูง ได้ ตามอำเภอใจ

เนื่องจากนิยามที่เทียบเท่ากันของลำดับสุ่ม Martin-Löf แต่ละแบบนั้นขึ้นอยู่กับสิ่งที่สามารถคำนวณได้โดยเครื่องจักร Turing บางเครื่อง ดังนั้นจึงสามารถถามได้อย่างเป็นธรรมชาติว่าอะไรคือสิ่งที่สามารถคำนวณได้โดยเครื่องจักร Turing oracleสำหรับ oracle A ที่กำหนดไว้ ลำดับBซึ่งไม่เพียงแต่เป็นลำดับสุ่มเท่านั้น แต่ยังตรงตามนิยามที่เทียบเท่ากันสำหรับการคำนวณได้เมื่อเทียบกับA (เช่น ไม่มีมาร์ติงเกลใดที่สร้างได้เมื่อเทียบกับ oracle Aแล้วประสบความสำเร็จกับB ) จะเรียกว่าเป็นลำดับสุ่มเมื่อเทียบกับAลำดับสองลำดับ แม้ว่าจะเป็นลำดับสุ่มในตัวเอง แต่ก็อาจมีข้อมูลที่คล้ายคลึงกันมาก ดังนั้นลำดับใดลำดับหนึ่งจะไม่เป็นลำดับสุ่มเมื่อเทียบกับอีกลำดับหนึ่ง ทุกครั้งที่มีการลดรูป Turingจากลำดับหนึ่งไปยังอีกลำดับหนึ่ง ลำดับที่สองจะไม่สามารถเป็นลำดับสุ่มเมื่อเทียบกับลำดับแรกได้ เช่นเดียวกับลำดับที่คำนวณได้นั้นเองก็ไม่ใช่ลำดับสุ่ม โดยเฉพาะอย่างยิ่ง นี่หมายความว่าΩ ของ Chaitinไม่ใช่ลำดับสุ่มเมื่อเทียบกับปัญหาการหยุดทำงาน

ผลลัพธ์ที่สำคัญอย่างหนึ่งที่เกี่ยวข้องกับความสุ่มแบบสัมพัทธ์คือทฤษฎีบทของแวน แลมบัลเกน ซึ่งกล่าวว่า ถ้า Cคือลำดับที่ประกอบขึ้นจากAและBโดยการสลับบิตแรกของAบิตแรกของBบิตที่สองของAบิตที่สองของBและต่อไปเรื่อยๆ แล้วCจะสุ่มแบบอัลกอริทึมก็ต่อเมื่อAสุ่มแบบอัลกอริทึม และBสุ่มแบบอัลกอริทึมเมื่อเทียบกับAผลที่ตามมาอย่างใกล้ชิดคือ ถ้าAและBต่างก็สุ่มด้วยตัวเองแล้วAจะสุ่มเมื่อเทียบกับBก็ต่อเมื่อB สุ่มเมื่อ เทียบ กับA

ความสุ่มสัมพัทธ์ให้แนวคิดแรกที่แข็งแกร่งกว่าความสุ่มแบบมาร์ติน-โลฟ ซึ่งก็คือความสุ่มที่สัมพันธ์กับออราเคิลA ที่กำหนดไว้ สำหรับออราเคิลใดๆ ความสุ่มแบบนี้จะแข็งแกร่งอย่างน้อยก็เท่ากัน และสำหรับออราเคิลส่วนใหญ่จะแข็งแกร่งกว่าอย่างเห็นได้ชัด เนื่องจากจะมีลำดับสุ่มแบบมาร์ติน-โลฟที่ไม่สุ่มเมื่อเทียบกับออราเคิลAออราเคิลที่สำคัญที่มักนำมาพิจารณาคือปัญหาการหยุดทำงาน (halting problem) และ ออราเคิลการกระโดดครั้งที่ n (nth jump oracle) เนื่องจากออราเคิลเหล่านี้สามารถตอบคำถามเฉพาะที่เกิดขึ้นตามธรรมชาติได้ ลำดับที่สุ่มเมื่อเทียบกับออราเคิลเรียกว่าn -random; ดังนั้น ลำดับจะเป็น 1-random ก็ต่อเมื่อเป็น Martin-Löf random เท่านั้น ลำดับที่เป็นn -random สำหรับทุกnเรียกว่า arithmetically random ลำดับ n -random บางครั้งเกิดขึ้นเมื่อพิจารณาคุณสมบัติที่ซับซ้อนกว่า ตัวอย่างเช่น มีเซตอยู่จำนวนนับได้เท่านั้น ดังนั้นเราอาจคิดว่าเซตเหล่านี้ไม่ควรสุ่ม อย่างไรก็ตาม ความน่าจะเป็นในการหยุดΩนั้นเป็นแบบสุ่ม 1 มิติ และจะเป็นไปไม่ได้เลยที่ชุดสุ่มจะเป็นแบบสุ่ม 2 มิติได้ก็ต่อเมื่อถึงระดับความสุ่ม 2 มิติแล้วเท่านั้น ${\displaystyle \emptyset '}$${\displaystyle \emptyset ^{(n)}}$${\displaystyle \emptyset ^{(n-1)}}$${\displaystyle \Delta _{2}^{0}}$${\displaystyle \Delta _{2}^{0}}$${\displaystyle \Delta _{2}^{0}}$

นอกจากนี้ ยังมีแนวคิดเรื่องความสุ่มอีกหลายประการที่อ่อนกว่าความสุ่มแบบ Martin-Löf บางส่วนได้แก่ ความสุ่มแบบ 1 ที่อ่อนแอ ความสุ่มแบบ Schnorr ความสุ่มที่คำนวณได้ และความสุ่มที่คำนวณได้บางส่วน Yongge Wang แสดงให้เห็น^{[ 11 ]} ว่าความสุ่มแบบ Schnorr แตกต่างจากความสุ่มที่คำนวณได้ นอกจากนี้ ความสุ่มแบบ Kolmogorov–Loveland เป็นที่ทราบกันว่าไม่แข็งแกร่งกว่าความสุ่มแบบ Martin-Löf แต่ยังไม่ทราบว่ามันอ่อนแอกว่าจริงหรือไม่

ในอีกด้านหนึ่งของสเปกตรัมความสุ่ม มีแนวคิดของ เซต K-trivialเซตเหล่านี้เป็นแบบต่อต้านความสุ่ม เนื่องจากส่วนเริ่มต้นทั้งหมดสามารถบีบอัดได้ในเชิงลอการิทึม (กล่าวคือสำหรับแต่ละส่วนเริ่มต้น w) แต่เซตเหล่านี้ไม่สามารถคำนวณได้ ${\displaystyle K(w)\leq K(|w|)+b}$

• ลำดับแบบสุ่ม
• เกรกอรี ไชติน
• สโตแคสติกส์
• วิธีมอนเตคาร์โล
• เซต K-trivial
• ความน่าจะเป็นสากล
• ความสุ่มทางสถิติ

• อีเกิล, แอนโทนี (2021), "โอกาสเทียบกับความสุ่ม"ใน ซัลตา, เอ็ดเวิร์ด เอ็น. (บรรณาธิการ) , สารานุกรมปรัชญาแห่งสแตนฟ อร์ด (ฉบับฤดูใบไม้ผลิ 2021), ห้องปฏิบัติการวิจัยอภิปรัชญา มหาวิทยาลัยสแตนฟอร์ดสืบค้นเมื่อ 2024-01-28
• Downey, Rod; Hirschfeldt, Denis R.; Nies, André; Terwijn, Sebastiaan A. (2006). "การปรับเทียบความสุ่ม" . The Bulletin of Symbolic Logic . 12 (3/4): 411– 491. CiteSeerX  10.1.1.135.4162 . doi : 10.2178/bsl/1154698741 . เก็บถาวรจากต้นฉบับเมื่อ 2016-02-02.
• Gács, Péter (1986). "ลำดับทุกลำดับสามารถลดทอนลงเหลือลำดับสุ่มได้" (PDF) . ข้อมูลและการควบคุม . 70 (2/3): 186– 192. doi : 10.1016/s0019-9958(86)80004-3 . เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2016-03-04 . สืบค้นเมื่อ2015-09-02 .
• Kučera, A. (1985) “วัดครับΠ⁰ ₁-คลาสและส่วนขยายที่สมบูรณ์ของ PA" สัปดาห์ทฤษฎีการเรียกซ้ำ บันทึกการบรรยายทางคณิตศาสตร์ เล่มที่ 1141 สำนักพิมพ์Springer-Verlag หน้า  245–259 doi : 10.1007/BFb0076224 ISBN 978-3-540-39596-6.
• Kučera, A. (1989). "เกี่ยวกับการใช้ฟังก์ชันที่ไม่เวียนเกิดในแนวทแยง" การศึกษาตรรกศาสตร์และรากฐานของคณิตศาสตร์เล่มที่ 129. นอร์ทฮอลแลนด์. หน้า  219–239 .
• Levin, L. (1973). "เกี่ยวกับแนวคิดของลำดับสุ่ม". Soviet Mathematics - Doklady . 14 : 1413– 1416.
• Li, M.; Vitanyi, PMB (1997). บทนำเกี่ยวกับความซับซ้อนของ Kolmogorov และการประยุกต์ใช้ (ฉบับที่สอง). เบอร์ลิน: Springer-Verlag.
• Martin-Löf, P. (1966). "นิยามของลำดับสุ่ม". ข้อมูลและการควบคุม9 (6): 602– 619. doi : 10.1016/s0019-9958(66)80018-9 .
• Nies, André (2009). ความสามารถในการคำนวณและความสุ่ม . คู่มือตรรกศาสตร์อ็อกซ์ฟอร์ด. เล่มที่ 51. อ็อกซ์ฟอร์ด: สำนักพิมพ์มหาวิทยาลัยอ็อกซ์ฟอร์ด. ISBN 978-0-19-923076-1. Zbl  1169.03034 .
• Schnorr, CP (1971). "แนวทางที่เป็นเอกภาพในการนิยามลำดับสุ่ม" ทฤษฎีระบบคณิตศาสตร์5 (3): 246– 258. doi : 10.1007/BF01694181 . S2CID  8931514 .
• Schnorr, Claus P. (1973). "ความซับซ้อนของกระบวนการและการทดสอบแบบสุ่มที่มีประสิทธิภาพ"วารสารวิทยาการคอมพิวเตอร์และระบบ 7 ( 4): 376– 388. doi : 10.1016/s0022-0000(73)80030-3 .
• Chaitin, Gregory J. (1969). "เกี่ยวกับความยาวของโปรแกรมสำหรับการคำนวณลำดับไบนารีจำกัด: ข้อพิจารณาทางสถิติ"วารสารของ ACM 16 ( 1): 145– 159. doi : 10.1145/321495.321506 . S2CID  8209877 .
• วิลล์ เจ. (1939) บทวิจารณ์ Etude เกี่ยวกับแนวคิดของ Collectif ปารีส: Gauthier-Villars.