真の乱数について結論が出た。
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2008/07/06(日) 18:49:01「任意の数列に対し、それよりランダム性の高い数列が存在する。」
要するに、真の乱数などというものを定義しようとするのは
最大の自然数を定義しようとするようなもので全く無意味だ。
おめでとう、俺！
>>2
削除依頼よろしく。
0002１３２人目の素数さん
2008/07/06(日) 19:51:24, o ', こ っ l. {@ @ i 日 は
ﾚ､ヮ __/ う こ l } し_ / も よ
/ ヽ う l > ⊃ < い う
_/ l ヽ へ l. / l ヽ い
しl i ｉ l / /l 丶 .l 天
l ┌襾┐ l / / l } l 気
| ├─┤ l ／ユ¨‐‐- ､_ l ! だ
￣￣ ¨¨¨ー─‐‐--- ,,＿／＿＿｀ヽ __`-{し|
も ぱ て ￣￣¨¨｀ ー──---
ぐ く （ |.|. |! |／ ヽ き
も ぱ (｀ ｀ｰ /..:::::＼≧,,,､:::）::: ゃ
ぐ く （―――――――‐ （:::::::＞'´ == ＼:: あ
_ ！ ！ (⌒￣￣￣￣￣￣￣￣ﾉ く彡/// ∪,ﾉ |
.ﾚ⌒Y^'⌒｀＼＿＿_ ／" ￣ ｀､＿_ く:::::∧ '_,. -､ く／::: っ
|:::| ＼xく / >>1 ヽ ＼:::::l､ヽ ,ノ ＼∠ ！
＼|:::| _,....!,,_ ＼ / ● ● l ｌF〒｀ヾ.＼,,..イ |:::::::ヽ
｀7´ ＿,,.ｨ l U し Ｕ l | || _,.-／7ﾞｈ _|:::::://
＼.｛ｎ|.ｨｧ it} l u ＿__ u lr'"三¨7´＼| |´.|:::://
|:::ﾄl、 rｭｊ . > u､_` --' _Uィ/ ﾟ`.|ｎ./ .イl ,∧ |:://
|::,| 'ーｹﾄr'T 0 ￣ uヽﾞtっ r'lﾞ /⌒`lくミV /
,r1´|｀'六´ //｀￣u 0 └┬ｼｊ .／ 7ヽ〈 /ヾ)＜
./ | ∨|::|∨ ! ｛ r ,､ ＿,ｼ ／ﾞ丁〈 / } { ｛ ＼
| ',|::|/ ! ,ゝ-＜ ( / .| |/ ∧ ＼|
l .Ｙ。 .| |` 〃￣￣⌒ / 〈 /! ', __,,....::-‐
.∧. |。 ｛ ﾞ爪｀ ' ‐- ､..,,,...イ '、 / .| ｀|:::::::::::::
＼/ ｌ |。./ ,l | l, .| . || ｀'ｰ' i | j::::::::::::::
ヽ､｀'::､L.∧/ / |.｛ u 〈.| イ 〈 /::::/::::::::
::::::::｀ヽ､ ∨ /￣| | ､ / l:l. | j /::::/::::::::::
0003１３２人目の素数さん
2008/07/06(日) 20:37:44量子力学使えば、真の乱数が手に入るんじゃないの？
0004１３２人目の素数さん
2008/07/06(日) 20:41:08まずはこれを定義しろ。話はそれからだ。
00051
2008/07/06(日) 20:45:07観測前の状態は真にランダムかもしれない。
しかし我々が得られるのは観測後の情報だ。
観測後も真にランダムであることを保っていられるか？
そこが問題だ。
0007１３２人目の素数さん
2008/07/06(日) 20:50:22量子力学は、観測前は原理的に位置や速度を確定できないってだけの話で、
観測後は完全に粒子の位置はランダム（そりゃ、どこに現れるかの確率は
方程式通りかもしれんが）だと思うぞ。
電子スピンの上下なんて使用すると、事実上トインコスみたいなコトできる
んじゃないのか？
0008１３２人目の素数さん
2008/07/06(日) 20:54:100009１３２人目の素数さん
2008/07/06(日) 20:55:350010１３２人目の素数さん
2008/07/06(日) 20:57:390012１３２人目の素数さん
2008/07/06(日) 21:16:48それはジャンケンだ。
2人で無限回のジャンケンをすることを考える。
自分はあらかじめ無限回分の出す手を勝負の前に決めておく。
この情報が相手に漏れることは無い。
相手は過去のこちらの手を見て、出す手を変えることが出来る。
つまりこちらの手に何らかの法則があり、それに気づかれたとすればジャンケンに負ける確率が高まる。
相手が法則に気づくかどうかは相手の能力にもよるだろうが、
ようするにジャンケンに負ける確率が低いほど、ランダム性が高いといえる。
0013１３２人目の素数さん
2008/07/06(日) 21:38:34１からnまでの値をとる数列 a_0,a_1,....が乱数であるとは次を満たす事である。
⇔
各k∈Ｎについて、
k次元点列 A_{k,0}=}(a_0,...a_{k-1}),A_{k,1}=}(a_k,....a_{2k-1}).....を考え、その点列全体をA_kとする。
1≦x_i≦nとなる自然数の座標x=(x_0,x1....x_k)を考えると
全てのｘに対して、確率測度 P(x|x∈A_k)が等しくなる場合である。
要するに、
・任意の数字の出る確率は同じで、
・任意のkについて、k周期性を持たない
という事で。
00141=12
2008/07/06(日) 22:05:25能力Pを持つ相手がジャンケンに勝つ確率を上げる法則を見つけられないとき、その手はPにとってランダムである。
と、定義しておこう。
0015１３２人目の素数さん
2008/07/06(日) 22:54:52そんなの自然数のn進展開を順に並べてけばそれで終わりだろ
少しは考えろよ
0016１
2008/07/06(日) 23:24:39ネタスレのつもりが、なんだか本当に大発見をしたような気になってきた…。
ところで俺はkingのファンなのだ。
せっかくのアイディアなので君の意見を聞きたい。
君のレスを待つ。
00171
2008/07/07(月) 17:52:31ネタが悪いのか？
しかし今度のネタは極上だ。
「計算可能が有限長記号列の限界」であるのと同様、
「真の乱数は無限長記号列の限界」である。
真の乱数が無限長記号列で記述できないのはそのためだ。
キーワードはランダム性だ。
ランダム性を真に理解するなら「実数を完全に列挙できる」
00181stVirtue ◆.NHnubyYck
2008/07/07(月) 19:03:3800191
2008/07/07(月) 21:41:50あるいは無限長記号列でも表記できないかもしれない。そこはよくわからない。
そもそもランダム性を真に理解しているわけではない。すまない。
ところでこんなことを考えている。
チューリングマシンで計算不能なルールがあるということは有限長記号列で記述出来ないほど複雑なルールがあるということだ。
では無限長記号列でルールを記述できるとしたらどうだろう。
チューリングマシンの停止問題を解く手順を具体的に表記できるかもしれない。
さらにその無限長記号列ですら記述できないほど複雑なルールはあるだろうか。
また、そのようなルールを解く手順を具体的に表記するにはどれだけのスペースが要るだろうか
0020１３２人目の素数さん
2008/07/07(月) 21:48:45うん。とりあえず数列の収束問題。
0021１
2008/07/07(月) 22:01:06無限長記号列で足りないとすれば、その先にはなにがあるか。
0022１３２人目の素数さん
2008/07/07(月) 22:07:57いや、だからそのための統計
0023１３２人目の素数さん
2008/07/07(月) 22:10:50とりあえず、潰し合いしてるくらいなら、本読もうな。
0024１３２人目の素数さん
2008/07/07(月) 22:21:36これはひどい
0025１
2008/07/07(月) 22:24:05無限長記号列を扱うためのマシンはどのようなものになるか
そのようなマシンを定義するためには無限長記号列が必要になるか？
そのようなマシンを構築するためにランダム性の概念は使えるのか？
なんだかまとまらなくなってきた。
0026１３２人目の素数さん
2008/07/07(月) 22:31:32無限長の演算に関しては知りません
情報を 7 つくらいに落とせば良いのでは?
0027１３２人目の素数さん
2008/07/07(月) 22:42:340028１３２人目の素数さん
2008/07/07(月) 22:51:09ちょw。バーボンハウス
0029１
2008/07/07(月) 23:49:05俺はそのスレ出身だ。
そこではいかに巨大な数を作るか、ということをやっている。
実際、いかに巨大な数を作るか、ということといかにランダムな数列を作るか、
というのは非常に密接に関係している。
というかほぼ同義だ。
ランダムとは何かを理解するために巨大数探索スレは素晴らしいインスピレーションを与えてくれるに違いない。
もし本気でこのスレをオチするなら巨大数探索スレの過去ログを漁ってくれ。
よろしく。
0030１
2008/07/08(火) 00:16:45ランダム性とランダムな数列を生成する方法にもおそらくこのような階層が存在する。
そしてこのような階層こそ実数の列挙を可能にする鍵となるかもしれない。
0031１３２人目の素数さん
2008/07/08(火) 00:33:04適当にそれらしい言葉を並べて喜んでいるだけじゃん
00331
2008/07/08(火) 01:57:08こんなことを思いついた。
チューリングマシンのテープ長がチューリングマシン停止問題を記述するのに必要な長さが必要であるのと同様に、
無限長記号列を扱うマシンのテープ長は真の乱数を具体的に記述できるほどの長さが必要である。
我ながら最高傑作ではないだろうか。
0034１３２人目の素数さん
2008/07/08(火) 02:36:5300351
2008/07/08(火) 03:06:33そしてたとえばP＝NP問題を決定するにはこの長さの記号列が必要である、などという議論は出来ないだろうか。
もしかしたら人類は真理に到達するのかもしれない。
ひひひ、気が狂いそうだ。
0036１３２人目の素数さん
2008/07/08(火) 07:18:03意味が分からない。
具体例で判例よろしく
0037１３２人目の素数さん
2008/07/08(火) 07:18:49ランダム性の定義が無いから、
語りようが無い訳だが。
00381
2008/07/08(火) 08:48:18１だ。
俺はランダム性をも完全に定義してしまったようだ。
「ランダム性とはテープの内容間の距離のである。」
簡単のためハミング距離を考えよう。
ｎビットの情報があり、一回の操作で1ビットフリップできるならAからBへ変換するのに何回のフリップが必要になるか。
このような距離がハミング距離だ。
チューリングマシンのテープの内容がAであり、この内容をBへと変換するにはチューリングマシンの状態数はいくつ必要か
0039１
2008/07/08(火) 08:52:26ランダム性とはチューリングマシンを移動手段と考えたときのテープの内容間の距離の概念である。
実際、俺はチューリング賞をもらってもおかしくないと思う。
0040１３２人目の素数さん
2008/07/08(火) 10:49:350041１３２人目の素数さん
2008/07/08(火) 11:01:020042１３２人目の素数さん
2008/07/08(火) 15:59:56数式で書けよ。
0043１３２人目の素数さん
2008/07/08(火) 19:19:55この手の人は勉強したがらないのが普通。
勉強して自分の発想が無価値であることに気付いてしまいたくないから。
現実逃避の一種。
0044１３２人目の素数さん
2008/07/08(火) 20:41:49要するに、
「お前の定義だとチャンパーノウン定数みたいな自然数列も乱数的ってことになっておかしいじゃん」
ということだろ
例として、各項が0以上9以下の値をとる無限数列として以下のものを考える。
1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, …
これは、10進表記された自然数を小さいものから順に並べ、
さらに各位の数（つまり0以上9以下の自然数）を一つの項として定めた数列である。
詳しいことはチャンパーノウン定数について調べたほうが早いかもしれないが、
この数列について、
「数字が一様に分布しており、数字の列が現れる頻度に偏りがない」
ということが知られている。
特に、数字の列として項数が1の数列 {0}, {1}, …, {9} を取れば、
これは>>1の言うところの「任意の数字の出る確率は同じ」なる条件を満たすことを意味する。
また、この数列が周期的でないこともほぼ自明。
よって、>>1の定義がまともだと仮定すると、この数列は乱数列のはずである。
しかし数列の各項の定め方を見ると、この数列は明らかに乱数的でない。
（任意の項に対して、直前までの有限列を見れば、その項の値が容易にわかってしまう）
よって仮定が誤りで、>>1の乱数列の定義はまともでない。
∴>>1は数学の勉強不足であることが示された。
0045１３２人目の素数さん
2008/07/08(火) 21:53:09>1みたいなのは勉強しても勝手な解釈しかしないからなぁ。
勉強するだけ無駄
>44
そういう数があるのね。
超越数にもなるとはすごい
0046１３２人目の素数さん
2008/07/08(火) 23:38:38http://pc11.2ch.net/test/read.cgi/prog/1167397021/
00471
2008/07/09(水) 05:54:58加算無限の世界で許される演算を加算無限回行っても実数無限には到達しない。
実数無限の世界で許される演算を実数無限回行っても真の乱数には届かない。
このような構造を想像して欲しい。
君たちは加算無限なるものや実数無限なるものさえ本当に理解しているか？
もし理解しているというならこのスレに書き込んでくれ。
よろしく。
0048１３２人目の素数さん
2008/07/09(水) 08:08:38形式冪級数環とか理解して無いんだろうなぁ
ｐ進数とか知らなさそう。
0049１３２人目の素数さん
2008/07/09(水) 08:58:14真の乱数（笑）
そういう言葉遊びで一人ﾆﾔﾆﾔしてる暇があるなら、
せめて初等的な集合論だけでももうちょっと真面目に勉強してきな。
そうすれば、皆も少しは君の話を聞いてくれるかもよ？ 暇つぶしに。
よろしく。
0050１３２人目の素数さん
2008/07/09(水) 09:28:56彼らは絶対数を集める事で目的を達成するので。
0051１３２人目の素数さん
2008/07/09(水) 09:43:23http://www.news.janjan.jp/business/0402/0402161130/1.php
とか、見てみ?
0052１３２人目の素数さん
2008/07/09(水) 09:51:55想像しても、矛盾しか出てこない気がする。
というか、「真の〜」って数学じゃないよね？
0053１３２人目の素数さん
2008/07/09(水) 10:03:28ネタバレするなってば
ディテールに拘るのが職人だろうよモンテカルロ
0054１３２人目の素数さん
2008/07/09(水) 11:33:20日本は書き言葉の文化ですので。
00551
2008/07/09(水) 18:13:29どうやら欠けていた最後のパーツをとうとう理解したようだ。
ランダム性がいかに生み出された概念であるかもわかった。
いまや全ての情報が等価となって美しい計算の構造をなしている。
先人の言わんとしているところをようやく理解したようだ。
おめでとう、俺！
PS、調子こいてすいませんでした。
00561
2008/07/10(木) 18:10:24ランダム性という概念は実に恐ろしい概念であるな。
世界の成り立ちについていろいろ考えさせられた。
我々が、時間を過去にさかのぼることが出来るようになったら何が起こるだろうか。
量子の振る舞いが観測前に決定できないのは深い理由があるのだろうか。
量子力学の多世界解釈が本当だとして、それを行き来できるようになったら？
核融合というのがあるだろう。質量がエネルギーに変わるという奴だ。
人類が質量をエネルギーに、エネルギーを質量に自在に変えられる技術を開発したとして、
それをコンピュータに応用したら何が起こるだろうか？
人間がクオリアによって世界を認識し、自由意志によって行動を起し、新たな法則を発見できる。
これは何を意味するか？
物体が光の速さを超えられないのは意味があるのか？
光の速さを超えると、時間を過去にさかのぼれるという概念は正しいのかもしれない。
エントロピー増大の法則という奴があるだろう。
あれこそが世界の法則を記述する真実かもしれない。
エントロピー増大の法則が宇宙の熱的死を意味するなんていってる奴は馬鹿だ。
もっと恐ろしいメッセージが秘められているはず。
00571
2008/07/10(木) 18:15:05いくらなんでも電波過ぎた。
スルーしてくれ。
00581
2008/07/10(木) 19:42:11真のランダムの前ではエントロピー増大の法則すら法則性ありすぎｗということらしい。
なるほど、人類の思考はここまで達していたか。
俺の中の真理の探究へのフラグが、いま何者かによって０から１への書き換えられたようだ。
00591
2008/07/10(木) 20:07:38もし、俺が何を理解したのかわかってる奴がいたら、俺のことをほめてくれ。
ちょっとぐらい、ほめられてもいいと思う。
00601
2008/07/10(木) 20:35:50かゆ
うま・・・
00611
2008/07/10(木) 21:39:04ランダムを理解すると、宇宙の果てまでも想像を広げることが出来る。
我々が宇宙の果てに向かって進んでいくと物理法則が少しずつ変化していく。
進めば進むほど物理法則が変化し、我々は、我々であることを保っていられなくなる。
我々が、我々のまま宇宙の果てに到達することはない。
このような冗談が生まれること自体、実に面白い概念であるな。ランダムは。
君たちにこのような冗談を考え付く能力があるだろうか。
0062１
2008/07/10(木) 21:53:51しかしそれでは、光の速度の限界がある。
なるほど、それが我々の物理法則の成り立つ宇宙のサイズであるか。
ランダム性とはかような冗談が次々と生まれてくるものである。
君もこのような冗談の背景を知りたくないか？
0063１
2008/07/11(金) 08:05:19旧約聖書で神は「光あれ」といって世界を作ったらしい。
そして、光は物理法則の限界である。
昔の人が何の知識もなしに、偶然たまたま物理法則の限界を言い当てた？
おかしくないか？
それに旧約聖書とランダムの発想は「あまりにも辻褄が合いすぎる」
なるほど、超古代文明なるオカルトがいまだに否定しきれないのもわかるきがする。
0064１
2008/07/11(金) 18:56:07我ながら、最高に電波な空気を作り出すことに成功したと思ったんだが、お前ら電波嫌いだっけ？
あるいは肥料が濃すぎても草木は育たぬということか。
まあいい。
こんどはランダムなる概念を武器にNP問題にどこまで迫れるかチャレンジするとしよう。
ポイントは「一度得た情報を圧縮し、再活用できるか。」
これだ。
これが可能になるならばあるいはNP問題も落とすことが出来るかもしれない。
まだわからないが。
0065１
2008/07/11(金) 19:46:37仮にチューリングマシンでの計算1回を足し算とするならそれに対応する掛け算は何になるであろうか。
あるいはそんなものは存在しないのか？
00661
2008/07/11(金) 20:25:07ならば人間には理解不能だ。
しかし擬似乱数を使って掛け算の真似事をすることは出来まいか？
00671
2008/07/11(金) 20:29:03これにするとしよう。
00681
2008/07/12(土) 07:38:05P=NPになるなんてことがいかにありそうでないか、以前より強く感じられるようになったしだいだ。
ところでグレイコードというものがあるが、何かの足しにならないだろうか。
0069１３２人目の素数さん
2008/07/12(土) 16:15:07ランダム性の研究は現在も活発に研究されてるし、いくらでも専門書の類はあるんだがな。
本を読まないまでも、
Kolmogorov Complexity
Martin-lof random
とかのワードを検索してみたらどうだろう。
んで、>>1のことは確かに大昔に証明されている事実だ。
0070１３２人目の素数さん
2008/07/12(土) 16:30:42お、このアイデアを自分で思いついたなら大したもんだ。
実際、ランダム性の一種で、こういう風に定式化するものもあるぞ。
（正確には、マルチンゲールを使って定義する）
チャイティンのオメガ（Chaitin's Omega）とか、>>1は興味ありそうだ。
検索してみれば、面白いかもしれないよ。
あと、スレの後半は妄想が入り込んで、でたらめな発言になっているから、
>>1にはちゃんとした本を読んでもらって、軌道修正してもらいたいところ。
00711
2008/07/12(土) 17:39:47妄想こそ真理への原動力なのだ。
だが、先人に学ぶことは大事だ。
これは車の両輪だ。
とりあえず、Kolmogorov Complexityは検索してみる。
チャイティンという人も少しは知ってるが、詳しく知ってるわけではない。これも調べてみる。
ありがとう。
確かに電波なレスもしたが、あの辺のことは
「宇宙を計算機に見立てて物事を考えるとそういう発想が出てくる」
とだけいっておく。俺なりに根拠があるのだ。すまない。
しかし、完全否定の罵声しか来ないと思ってたのに、部分的であれ認められるレスが付くとは。
やべ、マジ泣きそうｗ
00721
2008/07/13(日) 18:20:07とりあえず、チャイティンの数学の限界という本を買ってきた。
黒くて薄い奴だ。
まだ全部読んでないが、なるほど俺の欲しかったことが沢山書いてある。
正直に告白すれば、俺は勉強は嫌々やるタイプの人間なんだが…
チャイティンのような天才の長年の研究の成果のエッセンスを
本という形でただ同然で得られるとはありがたいことである。
ところでNP問題について考えていたんだが、NP問題は素因数分解の拡張版であるという解釈もできる。
実際、素因数分解はNPの一種だ。
素因数分解は掛け算と素数でもって全ての整数を表すという発想だが、実数についても同じことが出来ないだろうか。
実数における掛け算に対応する何かと素数に対応する何かを定義し、全ての実数を表す。
それができたらNP問題を考察するためのインスピレーションが得られるのではないかとおもった。
ところでNP問題に対して対角線論法は無力であるという結果があるらしい。
であれば、俺はNP問題に対して有効な武器を全くもっていないということだ。
NP問題はひとまず保留にしよう。
とりあえず、素因数分解について調べようかと思っている。
量子コンピュータなんか面白そう。
0073１３２人目の素数さん
2008/07/13(日) 20:53:39PCP(probabilistically checkable proof) 関係を調べてみたら？
00741
2008/07/14(月) 20:20:31>>73
了解。
調べてみる。
THX。
しかしTODOがちょっとづつ溜まってきてしまったな。
さてどうするか。
まあ、マイペースでやるしかあるまい。
00751
2008/07/14(月) 21:16:37WikiのPCPのページを見てみたが、いまいち心に響くものがないのはなぜだ？
俺が悪いのか、Wikiが悪いのか、PCPが悪いのか。
俺は神託機械の内側を見たいのに、PCPは神託機械の外側をみているからか？
外側からどう見えるかは内側を推測するヒントを与えてくれるはずなんだが…。
いまいち、ピンとこないのだ。
PCPの重要性が低いということはあるまい。
俺が悪いと思うのも癪だ。
Wikiが悪いということにして、別のページを探すとしよう。
0076１
2008/07/16(水) 19:29:19>>73
すまないがPCPとランダムオラクル仮説について、
詳しく書かれたサイトか書籍を教えてもらえないだろうか。
できれば日本語のやつで。
俺は検索能力が低いのでろくなサイトが見つからない。orz
0077１３２人目の素数さん
2008/08/23(土) 23:46:430078１３２人目の素数さん
2008/10/26(日) 11:59:540079１３２人目の素数さん
2008/11/27(木) 01:00:3000801
2008/12/17(水) 18:19:01このスレはこのままひっそりとdat落ちさせるつもりだったが、やりたいことが一個出来たので再利用させてもらう。
とりあえず、http://science6.2ch.net/test/read.cgi/math/1209732803/ の427を見てくれ。
0081１
2008/12/17(水) 18:22:34残念ながらわかってる奴から見ればあれは真の乱数とは呼べないものだということだ。
てことであれは擬似乱数の一種になる。
じゃあ、擬似乱数としてあれを評価した場合、他の擬似乱数と比べてどうなの？てのが気になる。
00821
2008/12/17(水) 18:26:15次のような非常に制限の強いプログラム言語X_1を考える。
1.使用できるデータ型（変数、定数とも）はC言語で言うところのunsigned charのみである。
2.使用できる演算は代入、足し算、引き算、論理演算(AND,OR,NOT,XOR,右シフト、左シフト)のみである。
3.if,while,goto,関数呼び出し等の制御構造は一切なし。プログラムは上から下へ順番に実行されるのみである。
4.unsigned char型の変数を使うことが出来る。個数に制限はない。
5.一ステップで代入一回、演算一回行うことが出来る。つまり１ステップは以下のどれか。
a=b;
a=~b;
a=b+c;
a=b-c;
a=b&c;
a=b|c;
a=b^c;
a=b<<c;
a=b>>c;
(※単項の-は禁止）
6.プログラムの終わりに次のような値を返す文を入れる。
return a;
この値をプログラムの値と呼ぶ。
7.プログラム中で使用できる定数は0x01のみである。
問題1
プログラム言語Pにおいてプログラムの値がaになるもので
最小ステップのプログラムを、Pにおけるaを返すエレガントなプログラムと呼ぶ。
0〜255についてそれぞれその値を返すX_1におけるエレガントなプログラムを一つ挙げよ。
問題2
プログラム言語X_1に対してプログラム中で使用できる定数を0x01では無く、他の値aに変えたものをプログラム言語X_aと呼ぶ。
また、エレガントなプログラムのステップ数が最も大きくなるような値をそのプログラム言語の最悪の値と呼ぶ。
プログラム言語X_0〜X_255の内、最悪の値に対するエレガントなプログラムのステップ数が最も小さくなるプログラム言語はどれか。
0083１３２人目の素数さん
2008/12/17(水) 20:01:2600841
2008/12/17(水) 22:28:39できればunsigned shortのデータが欲しいところだ。
まずは自力でunsigned charの場合を解くか。
0085１３２人目の素数さん
2008/12/18(木) 13:58:25たとえ「０と１と２」の３パターンしかなかったとしても、それは然り、
出現確率が歪んでいたとしても、それも然り。
一様であるとか、すべての状態に変化しえるとか、それは人が決めた
扱いやすさという意味で描くランダムにすぎないだろう。
前の出現と、後の出現の値に因果関係が無い、そして将来の値も同じ、
予測不可能で何かを基準として値を生むということではないものがランダムでしょう。
秩序が無いという意味で、どのような高次の捉え方であっても規則性を見つける
ことが不可能な挙動をする何かですよ。
故にランダムは>>1のいう結論と同じで無意味。
意味があるものは人が扱いやすいこと、
扱う対象の秩序と、乱数の結果は無関係であること。（つまり秩序や周期があっても問題ない）
予測できても問題はない。前の値から算出されても問題はない。
しかし、マクロ的な流れでは完全に近い乱数であってもミクロ、つまり部分的な
時間であっても周期性が見られるようなものは乱数としては好ましくない。
似た値が近い状態で連続するのはランダムでは許されるが人が好む乱数では
好ましくない。
>>1
真の乱数ではなく、擬似乱数の必要条件としての結論を出してくれ。
00861
2008/12/18(木) 20:24:07>>85からは、なんていうのかな、かなりの量の人生のリソースを
乱数の探求に突っ込んだ人間、そんな雰囲気を感じるといったら言い過ぎか？
とりあえず告白するんだが俺が興味があるのは物事の複雑性を測る尺度だ。
どうやら、ランダムはこれに深くかかわってるらしい。
役に立つ擬似乱数を探すとかはあんまり興味ないんだ。
もうちょっと勉強が進めば実はつながってるのかもしれないが。
0087１３２人目の素数さん
2008/12/18(木) 21:36:42複雑度を測るのなら、オカルトをお勧め。
オカルトの本質にはそれがある。まあ君程度が覗けるのは表面的な
オカルトだけだろうけどね。
0088１３２人目の素数さん
2008/12/19(金) 06:53:02＿＿＿＿＿＿ / ヽ＿＿/ ヽ
| ＿＿＿＿ ／ :::::::::::::::＼
| | /／ ＼ :::::::::::::::| えー終わりなの…
| |King氏ね | ● ● ::::::::::::::| じゃここも数板1番人気の
| | .| :::::::::::::| King氏ねスレにしよっと
| | | （__人__丿 .....:::::::::::::::::::/
| |＿＿＿＿ ヽ .....:::::::::::::::::::::::<
└＿＿＿／￣￣ :::::::::::::::::::::::::|
|＼ | :::::::::::::::::::::::|
＼ ＼ ＼＿＿＿ ::::::::::::::::::::::::|
0089KingMind ◆KWqQaULLTg
2008/12/19(金) 07:47:5300901
2008/12/19(金) 08:37:14せっかくならkingの乱数に対する見解でも披露してくれ
0091KingMind ◆KWqQaULLTg
2008/12/19(金) 11:23:06Reply:>>90 一様乱数のことをさすことが多い。
0093１３２人目の素数さん
2008/12/19(金) 21:14:240095１３２人目の素数さん
2008/12/19(金) 21:28:08とんでもない無限に近い周期ならば、同じ値が１億回連続していても
それは乱数と呼べる罠。
乱数集合全体に対しての乱数だからな。母体が無限に近い数ならば同じ値が連続しても
それは必然なり。
利用できる周期が不定で一様な雰囲気なものならば、円周率などの無限級数の
ことだろ。
00961
2008/12/20(土) 12:31:09>>82を解くプログラムが出来たのでうｐしてみる。
http://www.hsjp.net/upload/src/up55804.zip
面白い問題スレの結果とも一致したようなので多分大丈夫だろう。
ただ、unsigned charの場合は解けてもunsigned shortははっきりいって今のままでは絶望的ということが判った。
さて、どうしたものか。
00971
2008/12/20(土) 12:41:48常識なのかも知れんが一応。
>>96のファイルを解凍したら拡張子なしのファイルが出てくる。
そのファイルの拡張子をzipに直してから解凍するとプログラムが出てくるみたい。
言語はC++なんでよろしく。
00981
2008/12/20(土) 19:04:02個人所有PCのマシンパワーじゃ如何ともしがたいきがするぜ。
>>96のプログラムは幅優先探索なんでメモリ馬鹿食いでunsigned shortじゃとても動かない。
とりあえず、深さ優先探索に切り替えるか。
なんつーか、これはまったくの妄想なんだけどさぁ、
πとかってスパコン使ってすごい桁数計算してるじゃん？
素数とかもさぁ、すごいマシンパワーつかってモリモリデータ取ってるじゃん？
>>82の問題もさぁ、実は>>82の問題のデータがNP問題の解析に革新的な前進をもたらします！
みたいな論理的結果がもし万が一得られたらさぁ、どこかの大学で「うちのスパコンで計算しましょう！」
とかって話が出ないとも限らないジャン？
そんな夢のような展開ないかなぁ…
0099１
2008/12/20(土) 19:17:23とかって話になってIBMあたりが>>82の問題にチャレンジしてくれないかなぁ
これも十分夢のような展開だが…
0100１
2008/12/21(日) 11:22:03unsigned shortの計算量を大雑把に楽観的に見積もってみたが、
どうやら俺のPCで１００万年〜１０００万年くらい計算すれば解けるかもしれない、という感じだ。
仮にコンピュータの速度が１０年で１００倍になるとしたら３０年後には１００万倍の性能のPCが手に入る。
この問題を解くのは全くの不可能ってワケでもなさそうだ。
01011
2008/12/22(月) 10:59:37どうやら高速化の余地はまだまだ、たっぷり残ってるようだ。
もうすこしがんばるか。
01021
2008/12/26(金) 19:54:16深さ優先だと時間がかかる。
折衷案はどうだろう？
たとえば最終的に深さ１０まで読みたいとする。
まずは幅優先で深さ５まで読む。
深さ５まで読んだらさらにそれぞれの候補に対し個別に深さ５の幅優先探索をかける。
こうすることで現実的なメモリ量で単純な深さ優先探索より計算時間を短縮できると思う。
これの正式な呼び名は知らないがとりあえず２段幅優先探索と呼んでおこう。
01031
2008/12/26(金) 21:17:22足らんわっ・・・・・・ まるで・・・・・・！！(メモリが）
せめて１６GBは欲しいところだ。
0104１３２人目の素数さん
2009/01/08(木) 05:12:29では…コスト最適ランダム
0105１３２人目の素数さん
2009/01/11(日) 10:32:35根性で計算するんだ
01061
2009/01/11(日) 10:56:36意外と現実的なリソースで計算できるかも。
0107１３２人目の素数さん
2009/01/11(日) 20:50:24■ このスレッドは過去ログ倉庫に格納されています