Consider a concrete case. If we flip a fair coin and note the occurrences of heads and tails in order, denoting heads by 1 and tails by 0, then a sequence of 100 coin flips looks as follows:
具体的な例を考えよう。フェアなコインを投げて、表と裏を順に記録する。表は1でウラは0で、100回投げたら次のようになった：
(R) 11000011010110001101111111010001100011011001110111
00011001000010111101110110011111010010100101011110.
This is in fact a sequence I obtained by flipping a coin 100 times. The problem algorithmic information theory seeks to resolve is this: Given probability theory and its usual way of calculating probabilities for coin tosses, how is it possible to distinguish these sequences in terms of their degree of randomness? Probability theory alone is not enough. For instance, instead of flipping (R) I might just as well have flipped the following sequence:
これは私が100回コインを投げた結果である。アルゴリズム情報理論が可決しようとする問題はこれだ。
所与の確率論とコイン投げの普通の確率計算では、これらの系列のランダムさの程度をどうやって識別できるだろうか。確率論だけでは十分ではない。たとえば、コイン投げ(R)ではなく、同じようにコイン投げをして次のような系列が出たとしよう：
(N) 11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111.
Sequences (R) and (N) have been labeled suggestively, R for "random," N for "nonrandom." Chaitin, Kolmogorov, and Solomonoff wanted to say that (R) was "more random" than (N). But given the usual way of computing probabilities, all one could say was that each of these sequences had the same small probability of occurring, namely, 1 in 2100, or approximately 1 in 1030. Indeed, every sequence of 100 coin tosses has exactly this same small probability of occurring. To get around this difficulty Chaitin, Kolmogorov, and Solomonoff supplemented conventional probability theory with some ideas from recursion theory, a subfield of mathematical logic that provides the theoretical underpinnings for computer science and generally is considered quite far removed from probability theory.
系列(R)と(N)は、RandomのRとNonrandomのNの意味である。Chaitin,とKolmogorovとSolomonoffは、(R)は(N)よりも、よりランダムであると言いたかった。しかし、普通の確率計算では、これらの系列の確率は同じ小さな確率で、1/2100あるいは近似的に1/1030である。実際、100回のコイン投げの系列はまったく同じの確率である。この問題を解決するために、Chaitin,とKolmogorovとSolomonoffは、コンピュータサイエンスの基礎をであり、一般的に確率論から懸け離れていると考えられている数理論理学の一分野である再帰論からの考えで従来の確率論を補った。
What they said was that a string of 0s and 1s becomes increasingly random as the shortest computer program that generates the string increases in length. For the moment, we can think of a computer program as a short-hand description of a sequence of coin tosses. Thus, the sequence (N) is not very random because it has a very short description, namely,
彼らが言ったことは、文字列を生成する最も短いコンピュータプログラムが長いほど、0と1の列が、よりランダムだということだ。ここでは、コンピュータプログラムを、コイン投げの系列の速記とみなせる。従って、系列(N)は非常に短い記述を持つので、それほどランダムではない：
repeat ‘1’ a hundred times.
'1'を100回繰り返せ
Note that we are interested in the shortest descriptions since any sequence can always be described in terms of itself. Thus (N) has the longer description
copy ‘11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111’.
But this description holds no interest since there is one so much shorter. The sequence
しかし、この説明はあまりに短いので興味が持てない。次の系列
(H) 11111111111111111111111111111111111111111111111111
00000000000000000000000000000000000000000000000000
is slightly more random than (N) since it requires a longer description, for example,
は少し(N)よりも長い目の説明なので、少しランダムである。たとえば
repeat ‘1’ fifty times, then repeat ‘0’ fifty times.
'1'を50回繰り返し、'0'を50回繰り返せ
So too the sequence (また、次の系列は）
(A) 10101010101010101010101010101010101010101010101010
10101010101010101010101010101010101010101010101010
has a short description,
短い説明を持つ。
repeat ‘10’ fifty times.
'10'を50回繰り返せ
The sequence (R), on the other hand, has no short and neat description (at least none that has yet been discovered). For this reason, algorithmic information theory assigns it a higher degree of randomness than the sequences (N), (H), and (A).
一方、系列(R)は短くて適切な説明はない（少なくとも発見されていない）。この理由から、アルゴリズム情報理論は(R)に系列(N)や(H)や(A)よりもランダム度が高いとする。
Since one can always describe a sequence in terms of itself, (R) has the description
系列それ自体について記述できるので、(R)は説明を持っている
copy '11000011010110001101111111010001100011011001110111
00011001000010111101110110011111010010100101011110'.
Because (R) was constructed by flipping a coin, it is very likely that this is the shortest description of (R). It is a combinatorial fact that the vast majority of sequences of 0s and 1s have as their shortest description just the sequence itself. In other words, most sequences are random in the sense of being algorithmically incompressible. It follows that the collection of nonrandom sequences has small probability among the totality of sequences so that observing a nonrandom sequence is reason to look for explanations other than chance.
(R)はコイン投げで得られたので、これが(R)の最も短い説明であると考えられる。
大多数の0と1の系列はその系列自体が最も短い説明となっていることは、組み合わせられて事実である。言い換えるなら、大半の系列はアルゴリズム的に不可能だという意味でランダムだ。従って、ノンランダムな系列の集合は全系列の中で小さな確率となり、ノンランダムな系列を観測することは、偶然ではない説明をさがすべき理由となる。
さらに、"Specified"すなわち"意味ありげなもの"は、コルモゴロフ複雑性の定義では単純なものだということをDembskiは主張したことになる。しかし、それでは"複雑で指定された情報"というDembski用語とはマッチしない。単純なほど"複雑で指定された情報"ということになるのだから。
