乱数列は存在しない、の証明は可能でしょうか。

ある数列が与えられた時に、その数列が乱数列であることを証明することはできないと習いました。

そこで、質問なのですが、
「いかなる数列も乱数列ではない」という命題の真偽はポジティブに証明可能でしょうか？

この世に乱数列は存在しないのではないかと思いはじめて、ここのところ睡眠不足で困っています。

証明論などのご専門の方より、アドヴァイス頂ければ幸いです。

質問者からの補足コメント

• 

  質問が理解できない人は書き込まないで下さい。
  
  但し、「質問ができません」という書き込みまでは排除しません。

    補足日時：2019/07/24 17:22

• 

  命題が命題であると理解できない人は書き込む必要がありません。
  
  ただの迷惑です。

    補足日時：2019/07/24 17:29

• 

  ある数列が与えられた時点では、
  1.次に来る数が100でも1,000でも特定できるか、
  2.次に来る数は判らない
  のいずれかです。
  
  2.の場合は、
  2-1 今はわからないが、解析を進めるとわかる可能性があるか、
  2-2 今はわからないし、解析を進めても成功しないことがわかった。
  
  ３つの場合分けのうち、2-2のケースは有限時間内に発生するのだろうか？
  
  十分な解析時間を費やすと、1か2-1のいずれかになるのではないか？
  もしそうだとすると（2-2がないとすると）、乱数列が存在しないという結論にならないか？

  No.9の回答に寄せられた補足コメントです。 補足日時：2019/07/24 17:43

No.15 ベストアンサー 回答者： rinkun 回答日時： 2019/07/24 21:54

> 「いかなる数列も乱数列ではない」

数列と乱数の定義が定まらないと命題になってないですが(^-^;)、普通の定義の範囲なら偽な命題です。集合論の基礎的事実により、提示できるかどうかは別として無数の乱数列が存在することだけは証明できます。数列は無限の実数値列とかで良いですね。言い換えると自然数から実数への関数です。この定義による数列は連続濃度で存在します。一方、乱数はアルゴリズムで記述できない数列ですかね。アルゴリズムの厳密な範囲はどうでも良いです。普通の定義の範囲内ならアルゴリズムで記述できる数列は精々可算個しかないことは明らかですから。従って濃度の引き算により乱数(アルゴリズムで記述できない数列)は少なくとも連続濃度だけ存在します。

有限数列を含めて定義する場合は、乱数列は圧縮できない数列とします。要するにその長さの数値列を示すことより短く表現できない数列のことです。この定義の場合も、圧縮手法の記述方法によりどの数列が乱数列になるかが変わるため与えられた数列が乱数列か否かは判定できませんが、ある長さで表現可能な数列の総数は決まっていますので、おおむね数列の二つに一つは乱数列であることは明らかです。
一方、上記の証明法を理解いただければ『ある数列が与えられた時に、その数列が乱数列であることを証明することはできない』ということも理解できるでしょう。実際、具体的な数列が与えられたときその数列だけは圧縮できる圧縮法を作ることは可能です。その数列以外に圧縮できない数列が存在する圧縮法ですけど。またその圧縮法の定義自体が数列より長くなるかもしれませんけど。

そういうわけで、乱数列が存在することは間違いないですが、具体的な有限の数列は何を提示しても少なくとも万人が合意できる形で乱数列とは証明できません。無限長の数列の場合はもっと酷くて、アルゴリズムが存在しないことが定義なので、真の乱数列を有限長で形式的に表現(提示)する方法がありません。従って具体的に提示された数列を乱数列であると証明することはできません。
放射性物質の半減期を利用した乱数発生器で生成した乱数とか、おそらく真の乱数になるだろうとは期待できますが、この乱数の形式的な表現とか不可能でしょう。

数学の世界ではこの例のように存在は証明されるけど具体的に構成的な提示はできない存在は色々とあります。そういうものは存在しないという立場で考えたければ数学基礎論とかやると面白いでしょう。ただ役に立つかは疑問です。

この回答へのお礼

有難うございました。

＞数列は無限の実数値列とかで良いですね。
私は有理数の数列を念頭に置いていましたが、実数列で証明できれば十分です。

＞濃度の引き算により乱数(アルゴリズムで記述できない数列)は少なくとも連続濃度だけ存在します。
具体例に振り回されることなく、濃度の差で存在を証明できるなんて、美しいですね！

＞そういうものは存在しないという立場で考えたければ数学基礎論とかやると面白いでしょう。ただ役に立つかは疑問です。
数学においてさえも、複数の立場をとりうると言うのが基礎論の面白い所ですね。

明快でかつ示唆に富むご回答に感謝致します。

お礼日時：2019/07/24 22:08

No.14 回答者： usa3usa 回答日時： 2019/07/24 21:14

シュレディンガーの猫のような話ですね

ある数列が与えられた瞬間、たとえその数列が乱数列であったとしても、その数列は疑似乱数列になる

ということでは？

この回答へのお礼

そういう事です。

だから（真の）乱数列が存在する、とは言えないのではないか？これが疑問で、
それを証明できるのか、が質問です。

お礼日時：2019/07/24 21:18

No.13 回答者： ありものがたり 回答日時： 2019/07/24 17:45

＞それが回答になってると思うか？

No.１１ は、核心をついた回答だと思っています。
アドバイスが気に入らないなら、どうぞ我が道を行ってください。
出発点が間違っているけどね。

この回答へのお礼

命題は成立している。
その真偽が不明なだけだ。

お礼日時：2019/07/24 17:48

No.11 回答者： ありものがたり 回答日時： 2019/07/24 17:25

＞命題をポジティブに証明出来ないと思っているならそう言えば良い。

そうではなくて、真偽以前に命題になっていない
と言っているのです。
あなたが不快に感じるかどうかはともかく、それが事実であり、
そのことに気がついたほうがいいよというのが、私からのアドバイスです。

この回答へのお礼

命題が理解できないのになぜ書き込むか？

人の邪魔が面白いか？

お礼日時：2019/07/24 17:31

No.10 回答者： ありものがたり 回答日時： 2019/07/24 17:12

＞アルゴリズムは一般の定義を参照しなさい。

＞基本的知識を欠く者の、いたずら書きは迷惑です。

基本的知識を欠いているのは、あなたです。
「乱数列」を定義するのは簡単なことではなく、一般的な定義は知られていません。
あなたが「次に来る数が何であるかを決めるアルゴリズムが存在しない数列」を
乱数列の定義としたいのであれば、「アルゴリズム」を定義しなければ数学になりません。
「アルゴリズム」もまた、定義することが難しい言葉で、一般的な定義は無い。
文脈に即した定義をあなたが示さなければ、数学の議論にはならないのです。
証明論よりも、計算理論の勉強をすることが、問題に近づく道かと思います。←これがアドバイスです。

この回答へのお礼

命題をポジティブに証明出来ないと思っているならそう言えば良い。
なぜワザワザ人を不快にするか？

お礼日時：2019/07/24 17:19

No.9 回答者： usa3usa 回答日時： 2019/07/24 17:01

>＞その数列が乱数列であることを証明することはできませんよね。

>そこからこの問の全てが出発しているのです。

質問者さんの定義では、
　疑似乱数列は乱数列の一部ですか？
それとも、
　疑似乱数列は乱数列ではないのですか？

＞擬似乱数と乱数を混同されていませんか？
という応答から、後者の定義と理解してご説明申し上げています。

No5の回答の繰り返しになります事お許しください
ある数列が与えられた時点で、
　その数列は疑似乱数列になっている
ですから、疑似乱数列は（質問者さんの定義で）乱数列ではないことになり、
　その数列は乱数列ではない
言い換えれば、
　その数列が乱数列であることを証明することはできない
ことになりませんか？

この回答へのお礼

秘匿されたアルゴリズムで生成された一見乱数に見える数列が擬似乱数列です。
従って、秘匿されたアルゴリズムが判明すれば、次に来る数を特定できる為、真の乱数列ではありません。

擬似乱数列は、生成アルゴリズムが発見される可能性があります。別の表現をすれば生成アルゴリズムが判明していない時点でもアルゴリズムが存在しているので、数学で定義される乱数列ではありません。

問いを言い換えるとすれば、生成するアルゴリズムが存在しない数列が存在したとしても、アルゴリズムの不在を立証する（これは「不在証明」になるので証明は困難）事ができない以上、そのような数列が存在すると断言できないのではないでしょうか。
証明論の専門家はこのような一見パラドックスに見える問いに対して証明努力を費やすのか、それとも証明努力が無駄になることを立証できるのか、知りたいと思って質問しています。

お礼日時：2019/07/24 17:17

No.8 回答者： ありものがたり 回答日時： 2019/07/24 16:42

＞蒟蒻問答は不要です。

そのためには、あなたが自身が「アルゴリズム」の定義を示さなければ。
私は、「乱数列」という言葉に定義が無いことを問題視しているのです。

この回答へのお礼

アルゴリズムは一般の定義を参照しなさい。

基本的知識を欠く者の、いたずら書きは迷惑です。

お礼日時：2019/07/24 17:03

No.7 回答者： ありものがたり 回答日時： 2019/07/24 15:46

＞乱数列は、次に来る数が何であるかを決めるアルゴリズムが存在しない数列、と理解しております。

それは、「アルゴリズム」を定義しないと、コンニャク問答にしかならないなあ。

この回答へのお礼

蒟蒻問答は不要です。

乱数列の実例を（証明付きで）一つでも示していただけるとありがたいのですが、、、、。

お礼日時：2019/07/24 15:56

No.6 回答者： tknakamuri 回答日時： 2019/07/24 12:34

乱数と証明出来ない=乱数か判定出来ない。

=本当に乱数であっても判らない。

この回答へのお礼

乱数と証明出来ない=乱数か判定出来ない。
=本当に乱数であっても判らない＝判らないものは存在しているとは言えない。

お礼日時：2019/07/24 12:36

No.5 回答者： usa3usa 回答日時： 2019/07/24 11:48

＞乱数と擬似乱数を混同されていますね。

多分。
ある数列が与えられた時点で、
その数列は疑似乱数列になっているのです。
ですから、
乱数と擬似乱数を区別されるならば、
　その数列が乱数列であることを証明することは
できませんよね。

この回答へのお礼

＞その数列が乱数列であることを証明することはできませんよね。

そこからこの問の全てが出発しているのです。

お礼日時：2019/07/24 12:37