アルゴリズム的ランダムな無限列
マルチンゲールdが構成可能(弱計算可能、下方半計算可能、下計算可能とも言われる)であるとは、ある計算可能な関数 d ^ : { 0 , 1 } ∗ × N → Q {\displaystyle {\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }} があってすべての二進有限列wに対して以下を満たすことを言う。
すべての正の整数tに対して d ^ ( w , t ) ≤ d ^ ( w , t + 1 ) < d ( w ) {\displaystyle {\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w)}
lim t → ∞ d ^ ( w , t ) = d ( w ) {\displaystyle \lim _{t\to \infty }{\widehat {d}}(w,t)=d(w)}
ある列がマルティンレーフランダムであることは、どんな構成可能なマルチンゲールでも成功しないことと同値。
(ここでのマルチンゲールの定義は確率論で使われるものと微妙に異なる。確率論で使われるマルチンゲールは似たような公平な条件で定義される。すなわち、事前観察の歴史が与えられたときに、ある観察後の期待値が観察前の期待値と同じであることを要求する。確率論では事前の観察の歴史が資産の歴史であるのに対し、ここでの歴史は具体的な0と1の文字列である。)
列がマルティンレーフランダムであるとは、構成可能なヌル被覆で決められるどんな G δ {\displaystyle G_{\delta }} 集合にも含まれないことを言う。
構成可能なマルチンゲール(シュノア1971): マルチンゲールは関数 d : { 0 , 1 } ∗ → [ 0 , ∞ ) {\displaystyle d:\{0,1\}^{*}\to [0,\infty )} で、すべての有限文字列wに対して d ( w ) = ( d ( w ⌢ 0 ) + d ( w ⌢ 1 ) ) / 2 {\displaystyle d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2} となるものを言う。ここで a ⌢ b {\displaystyle a^{\smallfrown }b} は文字列aとbの連結である。これは「公平な条件」とも呼ばれる。マルチンゲールを賭けの戦略と見ると、上記の条件は公平なオッズであることを要求していると思えるからである。マルチンゲールdが列Sで成功するとは、 lim sup n → ∞ d ( S ↾ n ) = ∞ {\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty } となることを言う。ここで S ↾ n {\displaystyle S\upharpoonright n} はSの最初のnビットである。