알고리즘 무작위 시퀀스

직관적으로 알고리즘 무작위 시퀀스(또는 무작위 시퀀스)는 범용 튜링 기계(프리픽스가 없는지 여부에 관계없이)에서 실행되는 모든 알고리즘에 무작위로 나타나는 이진수의 시퀀스다. 이 개념은 유한한 알파벳의 순서(예: 십진수)에 유사하게 적용될 수 있다. 무작위 시퀀스는 알고리즘 정보 이론에서 연구의 핵심 대상이다.

실행 시간에 대한 특정 한계가 있는 알고리즘부터 오라클 머신의 질문을 할 수 있는 알고리즘까지 다양한 유형의 알고리즘이 고려되는 경우가 있기 때문에 랜덤성에 대한 개념이 다양하다. 이것들 중 가장 흔한 것은 마틴 뢰프 무작위(K-Röf randomness 또는 1-randomness)라고 알려져 있지만, 무작위성의 강하고 약한 형태도 존재한다. "알고리즘적으로 무작위"라는 용어가 설명 없이 특정 단일(완료 또는 무한) 시퀀스를 지칭할 때, 보통 "압축불능"을 의미하거나, 시퀀스가 무한하고 알고리즘적으로 무작위인 경우(즉, K-incompressible), "Martin-Löf-Chaitin 랜덤"을 의미한다.

알고리즘 무작위성을 확률적 무작위로 모호하게 하는 것이 중요하다. 계산 가능한(따라서 결정론적인) 공정에 대해 정의된 알고리즘 무작위성과는 달리, 확률적 무작위성은 일반적으로 동일한 분포의 독립된 장비 가능 확률적 공정에서 생성되는 것으로 알려진 선행(또는 결과)인 시퀀스의 속성이라고 한다.

2진수의 무한 시퀀스는 단위 간격의 실제 숫자로 식별할 수 있기 때문에 임의의 2진수 시퀀스를 (알고리즘적으로) 무작위 실수라고 부르는 경우가 많다. 또한 무한 이진 시퀀스는 자연수 집합의 특성 함수에 해당하므로, 그러한 시퀀스는 자연수 집합으로 보일 수 있다.

모든 Martin-Löf 랜덤(이진) 시퀀스의 클래스는 LAND 또는 MLR로 표시된다.

역사

무작위 수열의 첫 번째 적절한 정의는 1966년 페르 마틴 뢰프에 의해 주어졌다. Richard von Mises와 같은 초기 연구자들은 무작위성에 대한 모든 테스트를 통과한 것으로 무작위 순서를 정의하기 위해 무작위성에 대한 테스트의 개념을 공식화하려고 시도했지만, 무작위성에 대한 정확한 개념은 모호하게 남아 있었다. 마틴 뢰프의 핵심 통찰력은 계산 이론을 사용하여 무작위성에 대한 시험의 개념을 공식적으로 정의하는 것이었다. 이것은 확률의 무작위성 개념과 대조된다; 그 이론에서, 표본 공간의 어떤 특정한 요소도 무작위라고 말할 수 없다.

설립 이래 마틴 뢰프 무작위성은 원래 정의와 외견상 거의 유사하지 않지만, 무작위 시퀀스가 가져야 하는 속성에 대한 직관적인 개념을 만족시키는 많은 동등한 특성(압축, 무작위 테스트, 도박)을 인정하는 것으로 나타났다.ompressible, 그들은 무작위성에 대한 통계적 테스트를 통과해야 하고, 그들에게 돈을 거는 것을 어렵게 해야 한다. 마틴 뢰프 무작위성에 대한 이러한 다중 정의의 존재와 다른 연산 모델 하에서의 이러한 정의의 안정성은 마틴 뢰프 무작위성이 수학의 근본적인 속성이지 마틴 뢰프의 특정 모델의 사고가 아니라는 증거를 제시한다. 마틴 뢰프 무작위성의 정의가 "정확히" 무작위성의 직관적 개념을 포착한다는 논문은 마틴 뢰프-카이틴 논문으로 불리며, 교회-튜링 논문과 다소 유사하다.^[1]^{[further explanation needed]}

세 가지 등가 정의

마틴 뢰프의 원래 무작위 시퀀스에 대한 정의는 건설적인 null 커버에 관한 것이었다. 그는 시퀀스가 그러한 커버에 포함되지 않을 경우 무작위로 정의했다. Gregory Chaitin, Levin, Clos-Peter Schnorr는 알고리즘의 복잡성 측면에서 특성화를 증명했다: 초기 세그먼트의 압축성에 균일한 한계가 있다면 시퀀스는 랜덤이다. 슈노르는 마팅세일즈의 관점에서 세 번째 동등한 정의를 내렸다. 리와 비타니의 책 콜모고로프 복잡성과 그것의 적용에 대한 소개는 이러한 아이디어에 대한 표준 소개다.

알고리즘 복잡성(Chaitin 1969, Schnorr 1973, Levin 1973): 알고리즘 복잡성(예: (프리픽스 없는) Kolmogorov 복잡성 또는 프로그램 크기 복잡성으로도 알려져 있음)은 유한 시퀀스(문자 또는 이진수)의 알고리즘 압축성에 대한 하한으로 생각할 수 있다. 그것은 자연수 K(w)를 가진 각 시퀀스에 할당하며, 직관적으로 입력되지 않고 실행될 때 w를 출력하는 컴퓨터 프로그램(일부 고정 프로그래밍 언어로 작성됨)의 최소 길이를 측정한다. 복잡성에는 접두사가 없어야 한다. 프로그램(시퀀스 0과 1)에 이어 무한 문자열 0s가 나오고, 프로그램의 길이(정지된 것으로 가정)에는 유니버설 튜링 기계가 읽는 프로그램 오른쪽에 0의 수가 포함된다. 우리는 부분 문자열에 대한 길이 코드 정보를 선택할 수 있기 때문에 추가적인 요구사항이 필요하다. 자연수 c와 시퀀스 w를 주어, $K(w)\geq |w|-c$ 는 K $K(w)\geq |w|-c$ ( $K(w)\geq |w|-c$ ) $K(w)\geq |w|-c$ w - $K(w)\geq |w|-c$ ${\displaystyle K(w)\geq$ w $-c$ 이면 w는 c-압축 가능하다고 말한다.

무한 시퀀스 S는 S의 모든 유한 접두사가 c-incompressible로 되어 있는 상수 c가 존재하는 경우에만 Martin-Löf 랜덤이다.

건설적인 null 커버(Martin-Löf 1966): 이것이 마틴 뢰프의 원래 정의다. 유한 이항 문자열 w에 대해 우리는 C가_w w에 의해 생성된 실린더를 나타내도록 한다. 이것은 칸토어 공간의 기본 오픈 세트인 w로 시작하는 모든 무한 시퀀스의 집합이다. w에 의해 생성된 실린더의 측정 μ(C_w)는 2로^{− w} 정의된다. 칸토어 공간의 모든 오픈 서브셋은 분할된 기본 오픈 세트의 카운트 가능한 시퀀스의 조합이며, 오픈 세트의 측정치는 그러한 시퀀스의 측정값의 합이다. 유효 오픈 세트는 이진 문자열의 재귀적으로 열거된 순서에 의해 결정되는 기본 오픈 세트 순서의 조합인 오픈 세트다. A constructive null cover or effective measure 0 set is a recursively enumerable sequence $U_{i}$ of effective open sets such that $U_{i+1}\subseteq U_{i}$ and $\mu (U_{i})\leq 2^{-i}$ for each natural number i. 유효 null 커버마다 $G_{\delta }$ $G_{\delta }$ ${\$ 측정값 $G_{\delta }$ 0 집합, 즉 U $U_{i}$ ${\$ 집합의 교차점이 결정된다 $U_{i}$

시퀀스는 건설적인 null 커버에 의해 결정된 $G_{\delta }$ $G_{\delta }$ ${\$ 에 포함되지 않은 경우 Martin-Löf 랜덤으로 정의된다.

건설적인 마팅게일(Schnorr 1971): A martingale is a function $d:\{0,1\}^{*}\to [0,\infty )$ such that, for all finite strings w, $d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2$ , where $a^{\smallfrown }b$ is the conca현악 a와 b의 교번 이것을 "공정성 조건"이라고 한다: 만약 마팅게일을 베팅 전략으로 본다면, 위의 조건은 벳터가 공정한 승산에 대항할 것을 요구한다. A martingale d is said to succeed on a sequence S if $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ where $S\upharpoonright n$ is the first n bits of S. A martingale d is constructive (also known as weakly computable, lower semi-computable) if there exists 계산 가능한 함수 ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ : ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ { ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ → ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ Q {\ $displaystyle {\d}:\{0,$ 1\}^{*}\ $time \mathb {N}$ \to {\ $mathb$ {Q $\widehat{d}:\{0,1\}^*\times\N\to{\mathbb{Q}}$ $}}}}:$ w.

${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ( w ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ , ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ) ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ( ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ , ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ + ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ) ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ( ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ w ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ ) ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ , ${\displaystyle {d}(w,t)\leq {d}(w,t+1)}<d$ (w $)},$ 모든 ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ 양의 정수 t,
$\lim _{t\to \infit }{\widehat{d}(w,t)=d(w).$

어떤 건설적인 마팅게일이 그것에 성공하지 않는 경우에만 시퀀스는 마틴 뢰프 무작위다.

정의의 해석

Kolmogorov 복잡성 특성화는 무작위 시퀀스는 압축할 수 없다는 직관을 전달한다: 접두사보다 훨씬 짧은 프로그램에 의해 접두사가 만들어질 수 없다.

null cover 특성화는 무작위 실수에는 "공통하지 않은" 속성이 없어야 한다는 직관을 전달한다. 각 측정치 0 집합은 흔치 않은 속성으로 생각할 수 있다. 각 원포인트 집합에는 측정값 0이 있기 때문에 시퀀스가 측정값 0 집합이 없는 것은 불가능하다. Martin-Löf의 아이디어는 효과적으로 설명할 수 있는 0 세트를 측정하도록 정의를 제한하는 것이었다; 유효 null 커버의 정의는 효과적으로 설명할 수 있는 측정치 0 세트의 카운트 가능한 컬렉션을 결정하고, 이러한 특정 측정치 0 세트 중 하나에 속하지 않는 경우 시퀀스를 무작위로 정의한다. 측정값 0 집합의 계수 가능한 집합의 조합은 측정값 0을 가지므로, 이 정의는 즉시 측정값 1 집합의 무작위 시퀀스가 있다는 정리로 이어진다. 우리가 실제 숫자의 간격[0,1]으로 이진 시퀀스의 칸토어 공간을 식별한다면 칸토어 공간에 대한 측정은 르베그 측정에 동의한다.

마팅게일 특성화는 어떤 효과적인 절차도 무작위적인 수순에 돈을 걸 수 없다는 직관을 전달한다. 마팅게일 d는 베팅 전략이다. d는 유한 문자열 w를 읽고 다음 비트에는 돈을 베팅한다. 다음 비트는 0이 될 것이고, 그 다음 비트는 1.d가 될 나머지 돈은 실제로 발생한 비트에 놓았던 돈의 2배가 될 것이고, 나머지는 잃게 될 것이다.d(w)는 끈 w를 본 후에 가진 돈의 일부분이다. 문자열 w를 보고 배치된 내기는 d(w), d(w0), d(w1) 값에서 계산할 수 있기 때문에, 가지고 있는 금액을 계산하는 것은 내기를 계산하는 것과 같다. 마팅게일 특성화는 어떤 컴퓨터에서도 실행할 수 있는 베팅 전략(계산 가능한 것이 아닌 건설적인 전략의 약점에서도)은 무작위 순서에 따라 돈을 거는 전략을 만들 수 없다고 말한다.

Martin-Löf 랜덤 시퀀스의 특성 및 예

차이틴의 정지 확률 Ω은 무작위 시퀀스의 예다.
LAND^c(LAND의 보완)는 모든 무한 시퀀스 집합의 측정값 0 서브셋이다. 이는 각 건설적인 null 커버가 측정치 0 집합을 포함하며, 계산 가능한 null 커버만 많으며, 측정치 0 세트의 조합은 측정치 0을 포함한다는 사실에 의해 암시된다. 이는 LAND가 모든 무한 시퀀스 집합의 측정 단위 1 하위 집합임을 의미한다.
임의의 순서는 모두 정상이다.
랜드의^c 건설적인 무효표지가 있다. 이것은 임의성에 대한 모든 유효 시험(즉, 건설적인 null covers)은 어떤 의미에서 이 단일 시험에서 임의성에 대한 모든 시험을 통과하므로, 이 보편적 시험에서 임의성에 대해 요약한 것이라는 것을 의미한다. (Martin-Löf 1966)
보편적인 건설적인 마팅게일이 있다. 이 마팅게일은 어떤 건설적인 마팅게일 d가 시퀀스에 성공한다면 d도 그 시퀀스에 성공한다는 점에서 보편적이다. 따라서 d는 랜드의^c 모든 시퀀스에서 성공한다(그러나 d는 건설적이기 때문에 랜드에서는 어떤 시퀀스에서도 성공하지 않는다). (Schnorr 1971)
랜드는 $\Sigma _{2}^{0}$ $\Sigma _{2}^{0}$ 0 ${\$ 칸토어 공간의 서브셋으로 $\Sigma _{2}^{0}$ 여기서 where $\Sigma _{2}^{0}$ $\Sigma _{2}^{0}$ ${\$ 은 산술적 계층의 두 번째 수준을 가리킨다 $\Sigma _{2}^{0}$ . 이는 S를 포함하지 않는 범용 유효 null 커버에 일부 열린 세트가 있는 경우에만 시퀀스 S가 랜드에 있기 때문이다. 이 속성은 property $\Sigma _{2}^{0}$ $\Sigma _{2}^{0}$ ${\$ 공식으로 $\Sigma _{2}^{0}$ 정의할 수 있다고 볼 수 있다.
$\Delta _{2}^{0}$ $\Delta _{2}^{0}$ $\Delta _{2}^{0}$ ${\$ 즉, Halting 문제에 대한 Oracle에 대해 계산 가능한 랜덤 시퀀스가 있다. (슈노르 1971) 차이틴의 Ω은 그러한 수열의 예다.
무작위 시퀀스는 해독할 수 없고, 계산적으로 열거할 수 없으며, 동시에 계산할 수 없다. Since these correspond to the $\Delta _{1}^{0}$ , $\Sigma _{1}^{0}$ , and $\Pi _{1}^{0}$ levels of the arithmetical hierarchy, this means that $\Delta _{2}^{0}$ is the lowest level in the arithmetical hierarchy where 무작위 시퀀스를 찾을 수 있다.
모든 순서는 임의 순서에 따라 튜링할 수 있다. (쿠체라 1985/1989, Gaccs 1986). 따라서 임의적으로 높은 튜링 수준의 무작위 시퀀스가 있다.

상대 랜덤성

마틴 뢰프 무작위 시퀀스의 각 등가 정의는 어떤 튜링 기계가 계산할 수 있는 것에 기초하므로, 튜링 신탁 기계로 계산할 수 있는 것이 무엇인지 자연스럽게 물어볼 수 있다. 고정 오라클 A의 경우, 무작위적일 뿐만 아니라 실제로 A에 상대적인 계산가능성에 대한 동등한 정의(예: A가 B에 성공하는 오라클 A에 상대적인 건설적인 마팅게일은 없음)를 만족하는 시퀀스 B는 A에 상대적인 랜덤이라고 한다. 두 시퀀스 자체는 랜덤이지만 매우 유사한 정보를 포함할 수 있으며, 따라서 두 시퀀스 모두 다른 시퀀스에 비해 랜덤하지 않다. 한 시퀀스에서 다른 시퀀스로 튜링 감소가 있을 때마다 두 번째 시퀀스는 계산 가능한 시퀀스 자체가 랜덤하지 않은 것처럼 첫 번째 시퀀스에 대해 무작위일 수 없다. 특히 이는 차이틴의 Ω이 중단 문제에 대해 랜덤하지 않다는 것을 의미한다.

상대적 무작위성과 관련된 중요한 결과는 판 람발겐의 정리인데, 만약 C가 A의 첫 번째 비트, B의 첫 번째 비트, A의 두 번째 비트, B의 두 번째 비트 등을 인터리빙하여 A와 B로 구성된 시퀀스라면, C는 알고리즘적으로 무작위적이며, A가 알고리즘적으로 랜덤한 경우에만, B는 알고리즘적으로 랜덤하다고 기술하고 있다.y A에 상대적인 랜덤. 밀접하게 연관된 결과는 A와 B가 둘 다 랜덤 그 자체인 경우, B가 A에 상대적인 랜덤인 경우에만 A가 B에 상대적인 랜덤인 것이다.

Martin-Löf 랜덤성보다 강함

상대적 무작위성은 우리에게 마틴 뢰프 무작위보다 강한 첫 번째 개념을 주는데, 이것은 어떤 고정된 신탁 A에 대한 무작위성이다. 어떤 오라클의 경우라도 이것은 최소한 그만큼 강하고, 오라클 A에 대해 무작위적이지 않은 마틴-뢰프 랜덤 시퀀스가 있기 때문에 대부분의 오라클의 경우 엄격하게 더 강력하다. 종종 고려되는 중요한 웅변은 정지 문제인 $\emptyset '$ $\emptyset '$ ${\$ 과 $\emptyset '$ $\emptyset ^{(n)}$ ) n번째 점프 오라클 $\emptyset ^{(n)}$ (n $){\$ 이다 $\emptyset ^{(n)}$ 이러한 웅변들은 자연스럽게 발생하는 특정한 질문에 대답할 수 있기 때문이다. 오라클 $\emptyset ^{(n-1)}$ ( $\emptyset ^{(n-1)}$ - $){\$ 에 상대적인 랜덤 시퀀스를 $\emptyset ^{(n-1)}$ n-랜덤이라고 하며, 따라서 시퀀스는 마틴-뢰프 랜덤인 경우에만 1랜덤이다. 모든 n에 대해 n-랜덤인 시퀀스를 산술적으로 랜덤이라고 한다. n-랜덤 시퀀스는 더 복잡한 특성을 고려할 때 때때로 발생한다. 예를 들어, $\Delta _{2}^{0}$ $\Delta _{2}^{0}$ 0 $\Delta _{2}^{0}$ {\ $displaystyle \Delta _{2}^{0}$ 집합만 $\Delta _{2}^{0}$ 셀 수 있으므로, 이러한 집합은 랜덤하지 않아야 한다고 생각할 수 있다. 그러나, 정지 확률 Ω은 $\Delta _{2}^{0}$ 2 $\Delta _{2}^{0}$ {\ $displaystyle \Delta _{2}^{0}}$ 및 $\Delta _{2}^{0}$ 1-랜덤이며, 무작위 집합이 $\Delta _{2}^{0}$ 2 $\Delta _{2}^{0}$ {\ $displaystyle \Delta _{2}^{0}$ 이 되는 것은 2-랜덤에 도달한 후에만 가능하다 $\Delta _{2}^{0}$

마틴 뢰프 임의성보다 약함

또한 마틴 뢰프 무작위보다 약한 무작위 개념도 몇 가지 있다. 이들 중 일부는 약한 1-랜덤성, Schnorr 랜덤성, 계산 가능한 랜덤성, 부분 계산 가능한 랜덤성이다. 융게 왕은 슈노르의 무작위성이 계산 가능한 무작위성과 다르다는 것을 보여주었다. 덧붙여 콜모고로프-러블랜드의 무작위성은 마틴 뢰프 무작위보다 강하지 않은 것으로 알려져 있으나, 실제로 더 약한지는 알려져 있지 않다.

랜덤성 스펙트럼의 반대쪽 끝에는 K-trivial 집합의 개념이 있다. 이러한 세트는 모든 초기 세그먼트가 로그로 압축될 수 있다는 점에서 반랜덤이지만(즉, 각 초기 세그먼트 w에 $K(w)\leq K(|w|)+b$ $K(w)\leq K(|w|)+b$ K ( $K(w)\leq K(|w|)+b$ ) $K(w)\leq K(|w|)+b$ K $K(w)\leq K(|w|)+b$ ( $K(w)\leq K(|w|)+b$ + $K(w)\leq K(|w|)+b$ $(\displaystyle$ K $(w)\leq$ K $(w )+b)))$ 를 계산할 수 없다.

참고 항목

참조

^ Jean-Paul Delahaye, Randomness, Predictibility and Without of Order, 확률 철학, 페이지 145–167, Springer 1993.
^ 용게 왕: 무작위성과 복잡성. 박사 논문, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf

추가 읽기

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

[1] Jean-Paul Delahaye, Randomness, Predictibility and Without of Order, 확률 철학, 페이지 145–167, Springer 1993.

[2] 용게 왕: 무작위성과 복잡성. 박사 논문, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf

[1]

Search