X
トップページ⇒数学
1002コメント517KB
コラッツ予想がとけたらいいな
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
垢版 |
2012/10/14(日) 10:32:39.71
525 名前：１３２人目の素数さん[sage] 投稿日：2012/09/03(月) 18:24:27.22
http://d.hatena.ne.jp/righ1113/
コラッツ予想について、証明を考えてみました。
ご指摘ご意見ご感想など、ぜひよろしくお願いします。
0647righ1113 ◆OPKWA8uhcY
垢版 |
2017/01/18(水) 20:41:25.02ID:ZtV8agPE
・ソース
module Collatz08 where

import Control.Monad.Fix

col :: Integer -> Integer
col 1 = 1
col x = if odd x then 3*x+1 else x `div` 2
af :: [Integer] -> [Integer]
af xs = concat $ map af' xs
af' :: Integer -> [Integer]
af' x = (\z -> z ++ [1])
$ takeWhile (1/=)
-- x*100を任意の関数にする
$ takeWhile (\y -> if x*100 > y then True else error "over!")
$ iterate col x

-- この関数が定義できない
h :: ([Integer] -> [Integer]) -> [Integer] -> Bool
h _ _ = False

m :: [Integer] -> [Integer]
m xs = if h m xs then [1..] else [1]
0648righ1113 ◆OPKWA8uhcY
垢版 |
2017/01/18(水) 20:45:22.64ID:ZtV8agPE
・実行結果
*Collatz08> af [1..]
[1,2,1,3,…,2158,1079*** Exception: over!
*Collatz08> h af [1..]
False
*Collatz08> m (m (fix m))
[1]
実際の挙動とは異なりますが、型が合っている事は確認できます。
0649１３２人目の素数さん
垢版 |
2017/01/18(水) 20:46:08.84ID:Lq/a7iIt
どこに「Ｈがコラッツ予想である」ことが使われてるのかさっぱりわからん。
これじゃコラッツの予想に関しては何も言えないはずと思うが？？？
0650righ1113 ◆OPKWA8uhcY
垢版 |
2017/01/18(水) 20:57:21.21ID:ZtV8agPE
コラッツ遷移を表したAfの停止性を求めるHが存在しないのだから、
コラッツ予想について言えると思うのですが……
0651１３２人目の素数さん
垢版 |
2017/01/18(水) 21:22:58.06ID:Lq/a7iIt
>>646のどこに偶数なら2で割り奇数なら3掛けて1足すというコラッツの要素が出てくるんだよ
Af(xs)で仮定してるのは「発散したら停止し、そうでなければ走り続ける関数」だけだろ？
発散するかどうかだけが問題でコラッツの特性は全く使われてないじゃん？
0652righ1113 ◆OPKWA8uhcY
垢版 |
2017/01/18(水) 21:33:37.02ID:ZtV8agPE
実際に>>647の（colの）ように実装したら
コラッツを使っていると言えるのではないでしょうか。
0653１３２人目の素数さん
垢版 |
2017/01/18(水) 21:47:07.57ID:Lq/a7iIt
col x = if odd x then 3*x+1 else x `div` 2
この部分をほかの式にしても同様の議論が成り立っちゃうんじゃないの？ってこと
同様の議論が成り立つなら特にコラッツの予想について特別なことが言えてるんじゃなくて
もっと一般的なことしか言えてないってことになると思った。
0655righ1113 ◆OPKWA8uhcY
垢版 |
2017/01/20(金) 14:00:43.87ID:+K/zZY0t
Afにはコラッツも例えばゴールドバッハもフェルマーの最終定理も含める事ができて、
フェルマーは停止しないからH(フェルマー)は定義できる。
一般のHが存在しないからといって、個別のH(コラッツ)やH(ゴールドバッハ)が存在しないとは言えないのですね。
ダメということで、ありがとうございました。
0656１３２人目の素数さん
垢版 |
2017/01/24(火) 14:04:30.35ID:3mMuxlu+
馬鹿の考え休むに似たり

個別の知識を振り回しても正しい議論はできない
「この議論にはコラッツ由来の性質が使われてないから何かがおかしい」
という嗅覚が働かない人間はスタートラインにも立てない
コラッツ予想に限らんがね
永遠に低レベルな領域をぐるぐる回り続けて間違え続けるだけ
時間の無駄だな
0658１３２人目の素数さん
垢版 |
2017/01/24(火) 21:00:07.02ID:42SFrieH
でもちょっとした指摘で間違いを修正できたんなら>>1は見込みあるんじゃないか
0659righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/05(日) 04:08:07.85ID:EG9feBO2
>>620-625の細切れCoq証明を書きます。
Require Import Arith.
Require Import Omega.
Require Import Rbase.
は共通です。
0660righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/05(日) 04:11:34.06ID:EG9feBO2
>>621の前段
(** 1<(1+1/3x_0)…(1+1/3x_s-1)=2^t/3^s -> 3^s<2^t *)
Theorem t1:
forall (x_0 x_s multi s t :nat),
x_0=x_s -> x_s<>0 -> 3^s<>0 ->
3^s*multi > 1 ->
multi > 1 ->
2^t * x_s = x_0 * (3^s * multi) -> 2^t/3^s > 1.
Proof.
intros.
rewrite H in H4.
apply Nat.div_unique_exact in H4.
rewrite Nat.div_mul in H4.
assert(forall (a b:nat), a=b -> b=a).
intros.
omega.
apply H5 in H4.
apply Nat.div_unique_exact in H4.
rewrite H4 in H3.
auto.
auto.
auto.
auto.
Qed.
0661righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/05(日) 04:13:20.79ID:EG9feBO2
>>621の後段
(** tlog2>slog3 -> (t-s)/s>log(3/2) *)
Variable log2 : nat -> nat.
Theorem t2:
forall (s t:nat),
s<>0 -> log2 2=1 -> t*log2 2 >= s*log2 3 -> t/s-1 >= log2 3 -1.
Proof.
intros.
rewrite H0 in H1.
ring_simplify in H1.
apply Nat.div_le_lower_bound in H1.
apply (Nat.sub_le_mono_r (log2 3) (t/s) 1) in H1.
auto.
auto.
Qed.
0662righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/05(日) 04:16:31.21ID:EG9feBO2
>>622
(** 0=logx_0+s'log(3/2)-(t-s)/s*s' -> s'=logx_0/(t/s-log3) *)
Variable log2Z : Z -> Z.
Open Scope Z.
Theorem t3:
forall (x0 s t s':Z),
s <> 0 ->
t/s -log2Z 3 <> 0 ->
0=log2Z x0+s'*(log2Z 3 -1)-(t+(-1)*s)/s*s' -> s'=log2Z x0/(t/s-log2Z 3).
Proof.
intros.
rewrite (Z.div_add t (-1) s) in H1.
ring_simplify in H1.
apply (Zplus_minus_eq) in H1.
ring_simplify in H1.
apply (Zplus_minus_eq) in H1.
assert(forall (a b c:Z), -a=-b-c -> a=b+c).
intros.
omega.
assert(forall (a b:Z), -a*b = -(a*b)).
intros.
ring_simplify.
auto.
rewrite H3 in H1.
apply (H2 (log2Z x0) (s'*(t/s)) (-s'*log2Z 3)) in H1.
ring_simplify in H1.
rewrite <- (Zmult_minus_distr_l (t/s) (log2Z 3) s') in H1.
assert(forall (a b:Z), a*b=b*a).
intros.
ring_simplify.
auto.
rewrite H4 in H1.
apply Z.div_unique_exact in H1.
auto.
auto.
auto.
Qed.
Close Scope Z.
0663righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/05(日) 04:19:07.94ID:EG9feBO2
>>625
(** [logx_0+slog(3/2)]-[logx_0]+1 > (s+1)log(3/2) -> 1 > log(3/2) *)
Variable up : nat -> nat.
Theorem t4:
forall (x0 s:nat),
(forall (x y z:nat), up(x)-up(y)+1>z -> x-y+1>z ) ->
up(log2 x0 + s*(log2 3 -1)) -up(log2 x0) +1 > (s+1)*(log2 3 -1) ->
1 > (log2 3 -1).
Proof.
intros.
apply (H (log2 x0 +s*(log2 3 -1)) (log2 x0) ((s+1)*(log2 3 -1))) in H0.
assert(forall (a b c:nat), a+b-a+1>c -> b+1>c).
intros.
omega.
apply H1 in H0.
ring_simplify in H0.
omega.
Qed.
0664righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/05(日) 04:22:12.48ID:EG9feBO2
>>624の前段
(** [logXX_[s']]-[logY_[s']]=0 -> 1/2<(1+1/3x_0)…(1+1/3x_[s']-1)/k *)
Theorem t5:
forall (XX A multi k:nat),
(forall (x y z:nat), up(x+(log2 y)/z)-up((log2 y)/z)=0 -> 1<2*y/z ) ->
XX=A+(log2 multi)/k ->
up(XX)-up((log2 multi)/k)=0 -> 1<2*multi/k.
Proof.
intros.
rewrite H0 in H1.
apply H in H1.
auto.
Qed.
0665righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/05(日) 04:27:02.00ID:EG9feBO2
>>624の後段
(** k<2*multi -> multi*100<271 -> k>=8 -> False *)
Theorem t6:
forall (k multi:nat),
k<2*multi ->
multi*100<271 ->
k>=8 -> False.
Proof.
intros.
omega.
Qed.

以上になります。
0667１３２人目の素数さん
垢版 |
2017/02/05(日) 22:43:20.93ID:DjTDoiGi
sとtの関係ってコラッツの式から出てくるんじゃなかったっけ？
コラッツの式はどこにあるんだろう
0668righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/06(月) 02:56:10.14ID:xKTPqx0h
>>660の8行目の
2^t * x_s = x_0 * (3^s * multi) -> 2^t/3^s > 1.
なのですが、左の式を変形すると
x_s = x_0 * 3^s / 2^t * (1+1/3x_0)…(1+1/3x_s-1)
です。 (1+1/3x_0)…(1+1/3x_s-1)=multiです。
このようなこすい変形が随所に出てきます。
（そうしないと解けなかった）
0669１３２人目の素数さん
垢版 |
2017/02/07(火) 20:39:35.21ID:yLGcFgy0
仮定の一番初めのx_0=x_sというのはどこから来るんだっけ？
スマンなよく分かってなくて
0670righ1113 ◆OPKWA8uhcY
垢版 |
2017/02/08(水) 00:35:51.56ID:tAqU/1jS
もしループがあったら、という背理法を使っているので、
x_0=x_sです。
0673righ1113 ◆OPKWA8uhcY
垢版 |
2017/03/13(月) 05:15:26.67ID:dJYUxFWr
コラッツパターンもチューリング完全、とか分かったら面白いのかなあ。
0674１３２人目の素数さん
垢版 |
2017/03/13(月) 20:50:11.36ID:A8Mi3RiY
まあ望み薄だろうな。
チューリング完全なら計算が停止しないパターンがあるはず？
0675righ1113 ◆OPKWA8uhcY
垢版 |
2017/04/01(土) 15:59:42.74ID:wkby9ngI
左端を伸ばすパターンはチューリング完全と言えるかもだけど、
それをコラッツパターンにどう繋げたら良いか分からないです。
現状なんにも出来てないです。
0676righ1113 ◆OPKWA8uhcY
垢版 |
2017/04/27(木) 03:59:35.58ID:NZOaVTiK
チューリング完全、ムリでした……
ループのほうのpdfはゆっくりと書いています。
0678１３２人目の素数さん
垢版 |
2017/06/03(土) 21:26:11.99ID:5IRlU4Ze
おつ

俺の実力じゃ読み解けないけど読みやすさを意識して書いたんだろなてのは伝わってくるよ。
0679１３２人目の素数さん
垢版 |
2017/06/17(土) 23:08:02.85ID:vqhkVmpO
結局この証明の胆ってどこなんだろうな。よくわからん。
ごちゃごちゃ式変形してるけど一見、そこからは特別な情報は出てこなさそうに見えるんだよなぁ
俺にもうちょっと実力があれば付き合ってやれるんだが、すまんな。
0680righ1113 ◆OPKWA8uhcY
垢版 |
2017/06/18(日) 02:08:58.25ID:xOnz2tO1
>>679

胆は5ページ目の
(1+1/3x_0)...(1+1/3x_{[s']-1})がeより小さい
ところかな、と思います。
0681righ1113 ◆OPKWA8uhcY
垢版 |
2017/06/18(日) 02:43:18.07ID:xOnz2tO1
あと、ループする仮定のもとで、
コラッツパターンの左端傾き(t-s)/sと、 左端を伸ばすパターンの右端傾きlog(3/2)
が交差する事も重要だと思います。
0682１３２人目の素数さん
垢版 |
2017/06/20(火) 21:30:48.98ID:vNJoeLUD
コラッツパターンの左端とか左端を伸ばすパターンの右端ってのは直線なの？
0684１３２人目の素数さん
垢版 |
2017/06/21(水) 18:56:37.20ID:4uYof9II
ループするてことは一周して増えもしないし減りもしないってことだけど
この証明は一周する度に何が減るって議論してるような？
何が減ってるんだろう？
0685684
垢版 |
2017/06/21(水) 21:17:55.31ID:Br1vBJfF
うーん左端と右端の差が減るんだろうか？
0686righ1113 ◆OPKWA8uhcY
垢版 |
2017/06/22(木) 12:42:22.70ID:a+o92jNq
>>684

>>620の前準備2より、ループを重ねるたびに、
コラッツパターンと左端を伸ばすパターンのずれが「増える」のです。
で、コラッツパターンの左端と、左端を伸ばすパターンの右端が交差する所で
ずれが3以上になって、
その場所で矛盾するのです。
0687１３２人目の素数さん
垢版 |
2017/06/23(金) 20:47:11.82ID:Aha3AK9Q
>[logY_s]と[logX_s]
すまん、この記号[ ]の意味はなんだっけ？切り上げ？
0688１３２人目の素数さん
垢版 |
2017/06/23(金) 21:01:44.54ID:8j+4jyzS
>>687
[ ]はガウスの記号、つまり端数を丸めて（絶対値で見た時に切り捨てて）整数にする演算のことじゃないの？
0689１３２人目の素数さん
垢版 |
2017/06/23(金) 21:08:08.37ID:8j+4jyzS
>>688訂正
すまん、ガウスの記号の意味は正負どちらでもそれ以下の最大の整数にする演算、つまりfloorと同じ意味だった
ともかく[ ]はガウスの記号だと思うよ
（なぜかガウスの記号には高校数学だと[ ]を使うのに対して、大学以上の数学だと下だけに爪が出てる記号（つまり」とその左右反転形）を使うよね）
0690１３２人目の素数さん
垢版 |
2017/06/24(土) 10:26:51.33ID:crDj8neM
コラッツパターンは、コラッツの操作によって得られるもともとの情報群。
複雑すぎて手に負えない。

左端を伸ばすパターンは、コラッツパターンから
情報を落とすことで得られるポンコツな指標。
操作を進めるごとに情報が落ちていくので、どんどん精度が悪くなる。
こんなものがコラッツパターンの実態を捉えているなんてあり得ないので、
コラッツパターンと比較したところで大して得るものは無い。

「左端傾き」「右端傾き」といった考え方もゴミである。
離散的な対象に対して、大域的にであれ局所的にであれ「傾き」に相当する量を
定義したところで、それは極めて大雑把な荒い指標にしかならない。
そんな頼りない道具だけでコラッツ予想が制御できるわけがない。
0691１３２人目の素数さん
垢版 |
2017/06/24(土) 10:34:09.83ID:crDj8neM
・・・と、御託はこのあたりにして、具体的に間違いを指摘する。
>>677の(17)の不等式が完全に間違っている。(17)では

[s']＝[(log_2 x_0)/(t/s−log_2 3)] ＜ 3x_0

となっているが、分母の (t/s−log_2 3) が非常にゼロに近い場合、

[s']
＝ [(log_2 x_0)/(t/s−log_2 3)]
＝ [(log_2 x_0)/(ほぼゼロ)]
＝ [(log_2 x_0) * (1/ほぼゼロ)]
＝ [(log_2 x_0) * 滅茶苦茶デカイ係数 ]
＞ 3x_0

となり得るので、この場合、不等号が逆転することになる。

「このような可能性は実際には起こらず、確実に [s'] ＜ 3x_0 が成り立つ」

と言うのであれば、そのことを証明しなければならない。
しかし、末尾の coq では証明されていない。

「図を使って傾きを比較することで [s'] ＜ 3x_0 が成り立つ」

と言っているようにも見えるが、図が無い上に、それぞれのパターンを
どのように配置してどこを原点としてどのようにして直線の傾きを
比較するのか文章からは読み取れないので判断のしようがない。
0692１３２人目の素数さん
垢版 |
2017/06/24(土) 10:40:58.68ID:crDj8neM
なお、きちんと精査はしていないが、
(1)〜(23)のうち、(17),(22),(23)を除く全ての式は
おそらく正しいと思われる。なぜなら、これらの式では

・ 記号の定義
・ 単なる等式の変形
・ 自明な評価による自明な不等式の導出

のいずれかの行為しか行っていないからだ。
パターンのずれとか傾きの違いがどうこうなどと
御託を並べているものの、その実態は上記の3項目のみである。

ちなみに、(22),(23)で間違っている箇所は、途中で(17)を使っているところであり、
それゆえに間違いとなる。従って、実質的には(17)のみが間違いとなる。
そして、それ以外の個所では上記の3項目による自明な行為しか行っていないので、
結局、>>677ではコラッツ予想の難しさを(17)に責任転嫁しているだけということになり、
コラッツ予想について何も言えていないことになる。
0693righ1113 ◆OPKWA8uhcY
垢版 |
2017/06/24(土) 12:53:18.60ID:JGgmjFB8
指摘ありがとうございます。見直したところ、
(t/s−log_2 3) > 0 のところを、
(t/s−log_2 3) > 1 と勘違いしていました。
またしてもダメでした……
お騒がせしました。
0694１３２人目の素数さん
垢版 |
2017/06/26(月) 21:23:01.72ID:1jLGU0ra
乙。
頭の良い奴が来てくれたか。
俺も力になれればいいんだが、なかなか難しい。
0695１３２人目の素数さん
垢版 |
2017/08/06(日) 18:21:21.93ID:oDKJI1vJ
耳栓をしたら世界が変わってワロタ
0696￥ ◆2VB8wsVUoo
垢版 |
2017/08/06(日) 18:21:56.37ID:+CYdGQny
☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆

￥
0697１３２人目の素数さん
垢版 |
2017/08/06(日) 20:09:55.82ID:oDKJI1vJ
耳栓をしたら世界が変わってワロタ
0705１３２人目の素数さん
垢版 |
2017/08/07(月) 03:17:18.68ID:/yQwEvEc
￥さんが数学板に極めて批判的であるのは良く承知していますが、このスレは荒らさないであげて下さいよ
珍しく自分なりに数学をやっている人がその研究経過について報告してくれているのですから

数学板のすべてのスレが腐っているわけではありません
他の板でも腐っているスレもあれば数学板でもこのスレのように「数学」という言葉本来の目的で使用されているスレもあるのですから
また数学板の全てのスレで各スレの投稿者や読者の集合が一致しているわけでもありません
（もしそうだと主張なさるならば数学の証明として通用するレベルの論理的な証明か又は２ちゃんねる数学板のログのような客観的で確実な証拠でもご提示ください）

板で腐っているかいないか決めつけるのは人の知性の有無を国籍や肌の色で判断するのと同じ乱雑で反知性的な判断であって
数学や知性を愛する￥さんに相応しい行動とは思えません

スレ主さんや他の住人の方々、スレ違いの投稿失礼しました
0708￥ ◆2VB8wsVUoo
垢版 |
2017/08/07(月) 06:47:24.69ID:/rspiZFz
☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆

￥
0719１３２人目の素数さん
垢版 |
2017/08/07(月) 08:44:46.18ID:0YzkEl/p
耳栓をしたら世界が変わってワロタ
0720１３２人目の素数さん
垢版 |
2017/08/07(月) 15:14:50.99ID:/yQwEvEc
>>706
現代数学の系譜スレでは￥氏はちゃんと会話をなさってるので
こちらが適切に発言すれば言葉は通じると思ったわけです
0721１３２人目の素数さん
垢版 |
2017/08/07(月) 15:17:03.95ID:0YzkEl/p
耳栓をしたら世界が変わってワロタ
0722righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/08(日) 09:15:13.38ID:StPF7u7V
メルセンヌ素数 2^110503 - 1 って
止まらないことないですか？
0723１３２人目の素数さん
垢版 |
2017/10/08(日) 11:28:20.81ID:Cutv7rfi
計算機でまわしたのか？
単にデカいから時間かかってるだけじゃないのか？
0724righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/08(日) 11:36:26.39ID:V4WPWhh+
2^110503-1が大体30000桁で、
10時間程走らせて、今45000桁ぐらいなのです。
また止まったら報告します。
0725１３２人目の素数さん
垢版 |
2017/10/08(日) 15:27:53.11ID:m0FVLI/3
2^n-1をコラッツの操作かけると3^n-1になるんだろ？30000桁が45000桁になってもさほど特別とは思わんな
0726１３２人目の素数さん
垢版 |
2017/10/08(日) 15:58:04.91ID:Pp5mcjdG
>>725で指摘されてるが、2^n-1から始めたいなら、
バカ正直に2^n-1からスタートさせるのではなく、
3^n-1からスタートさせないと無駄にも程があるな
0727１３２人目の素数さん
垢版 |
2017/10/08(日) 23:28:04.64ID:Cutv7rfi
ちなみに>>1の計算機だと３００００万桁の数値に対して何コラッツステップ/secくらいのスピードで計算できんの？
0729righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 00:59:44.36ID:Vv+x6w6w
奇数→奇数を1ステップとして、
2361コラッツ奇数ステップ/sec　ぐらいですかね。
0730１３２人目の素数さん
垢版 |
2017/10/09(月) 01:11:15.90ID:93q6V3EV
すまん、聞いてはみたものの速いのか遅いのかよくわからんｗ
プログラム言語は何使ってんの？
0731righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 01:19:17.60ID:Vv+x6w6w
僕もよく分からないですw
言語はHaskellを使っています。多倍長整数が標準搭載されているので。
0732１３２人目の素数さん
垢版 |
2017/10/09(月) 01:28:20.34ID:93q6V3EV
Haskellか〜
プロトタイプ作るのには良いかもしれんが計算ぶん回すのにはどうなんだろ？
C++とまではいかなくても速度高めの言語も試してみるといいかもね。
0734１３２人目の素数さん
垢版 |
2017/10/09(月) 01:53:47.71ID:93q6V3EV
ん〜haskell最速ってホンマかいなｗ
どんな理屈でそういう結果になるのか想像つかないｗ
0735１３２人目の素数さん
垢版 |
2017/10/09(月) 02:00:31.03ID:93q6V3EV
haskellだけ多倍長になってないとかかなぁ
うーん。なんか違和感あることはある。
0736righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 02:04:02.85ID:Vv+x6w6w
多分、多倍長整数と並列計算の組み合わせが
低コストで上手くいっているのがHaskellだと思います。
自信は無いですがw
0737righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 17:38:37.95ID:Vv+x6w6w
>>726
3^110503-1で再チャレンジしました。
一日かかって40000桁まで下がったのですが、これ以上続けるのはしんどいです。
グダグダですみません。
0738１３２人目の素数さん
垢版 |
2017/10/10(火) 11:57:48.23ID:ziN8w0WH
停止するかどうかを 3^110503-1 のときに
確かめようとしてる時点で既にグダグダだけどな。

なぜなら、どうせ停止するに決まってるからだｗ

それが 1 になるかは分からないが、少なくとも
停止することは確実だと予想してよいだろう。
無論それ自体も未解決ではあるのだが、
停止「しない」ことが期待されるような良い根拠はどこにも無く、
逆に必ず停止すると思しき良い根拠はいくつもあるわけで。
0739１３２人目の素数さん
垢版 |
2017/10/10(火) 22:17:48.67ID:n27Dzau3
例えばループする自然数があったとして、ループの周期が非常に長く履歴がメモリに納まらないようなことが想定される場合、
ループを検出するアルゴリズムとしてどのようなものが考えられるだろうか？
0740１３２人目の素数さん
垢版 |
2017/10/11(水) 01:44:51.35ID:4RhSgzf6
>>739
1ステップずつ移動するのと2ステップずつ移動するのを用意して
同時に走らせて、両者の値が一致するかどうかを毎回チェックする。
一致したらループに入ってるし、逆にループに入ってたら
必ず一致するタイミングが訪れる。
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況