コラッツ予想がとけたらいいな その2

1righ1113 ◆OPKWA8uhcY 2018/05/10(木) 22:10:23.74ID:ogyKPvh0
コラッツ予想に挑戦するスレです。

前スレ コラッツ予想がとけたらいいな
https://rio2016.5ch.net/test/read.cgi/math/1350178359/

>>1の証明(未検証)
https://github.com/righ1113/collatzProof

それより弱い成果もあります(未検証)
コラッツのループはあるとしてもとても長い
https://github.com/righ1113/collatzLongLoop

245righ1113 ◆OPKWA8uhcY 2018/06/13(水) 21:27:55.75ID:RdFyYz3+
>>243
チューリングマシンなら、あるんだがなあ。
https://m.youtube.com/watch?v=t9nbkS-5bv8#

246132人目の素数さん2018/06/13(水) 21:33:44.48ID:9eZXXRM3
そりゃチューリングマシンはあるだろうさ

247132人目の素数さん2018/06/13(水) 22:05:18.39ID:6aITicNF
JavaScript で実装してみた
たぶん新しめのブラウザでないと動かない
最上位の1は暗黙の存在とし、内部的には全部'_'になって止まる

第1引数は下位を先頭とする2進数の文字列
(※最上位の1は入力からは除外する)
第2引数は途中で止めたい時用に処理する最大桁数
出力は途中経過の配列(最上位の1は補完)

function collatz(a,m){
const STT=[
['___','___','___'], // 停止
['10L','11L','6_R'], // 最下位まで戻る
['___','___','10L'], // 繰り上がり処理
['30R','41R','11L'], // ×3+0
['31R','50R','20R'], // ×3+1
['40R','51R','21R'], // ×3+2
['6_R','5_R','0_R'], // 割る2
];
let s=6, i=0, r=[a+1];
a=[...a];
while(s>0&&i<m){
let c='01'[a[i]]||'2';
let n=STT[s][c];
s=n[0]; // 状態
a[i]=n[1]; // 文字
i+=(n[2]=='R')?1:-1; // 移動
if(s==6)r.push(a.join('')+1);
}
return r;
}

248132人目の素数さん2018/06/13(水) 22:08:23.72ID:xW9095UW
>>247
ん、これコラッツのプッシュダウンオートマトンなの?

249132人目の素数さん2018/06/13(水) 22:12:54.50ID:6aITicNF
なお出力の途中経過は×3+1,÷2のいずれかが完了したところだけ出してる

250132人目の素数さん2018/06/13(水) 22:13:28.53ID:6aITicNF
あ、プッシュダウンではないね
ただのオートマトン

251132人目の素数さん2018/06/13(水) 22:14:59.61ID:xW9095UW
有限オートマトンのこと?
コラッツってそんな弱いの?

252132人目の素数さん2018/06/13(水) 22:25:22.86ID:6aITicNF
弱い強いはよくわからんが
「ある整数からコラッツ問題の通りに計算を続けて1に到達する」と
「ある整数に対応する初期状態から開始すると止まる」が同値になるオートマトンは作れるかな?
というわけで作ってみたのだが

253132人目の素数さん2018/06/13(水) 23:07:39.84ID:xW9095UW
うーん、プログラムが正しくオートマトンの制限を守ってるかどうか判断できない orz
パッと見、チューリングマシンのようにも見える。LとかRとかあるし。

254132人目の素数さん2018/06/13(水) 23:23:40.12ID:6aITicNF
オートマトンは進む一方か……
チューリングマシンだったねこれ

255132人目の素数さん2018/06/13(水) 23:34:57.10ID:6aITicNF
とりあえずwikipediaで定義を見直してきましたが、チューリングマシンと呼ぶべきですね
チューリングマシンをオートマトンの一種とするならオートマトンといえなくもないかもですが……
有限オートマトンではありません
なんかごっちゃになってましたねー

256132人目の素数さん2018/06/15(金) 19:53:54.10ID:uqoBws9V
まあ、プッシュダウンオートマトンでコラッツを実装で来たらそれはそれで一定の成果なのかな?
コラッツ予想が真なら究極的には1状態有限オートマトンでもおkなわけだから無い話ではないはず。

257132人目の素数さん2018/06/15(金) 21:09:22.84ID:uqoBws9V
プッシュダウンオートマトンで実装で来たら無限に発散しないことが言えてしまう?

258132人目の素数さん2018/06/15(金) 21:10:02.85ID:uqoBws9V
いや、そうともかぎらんか。スマソ

259前786 ◆5A/gU5yzeU 2018/06/18(月) 00:49:33.21ID:R9ITlpR3
すっかり別の話が進んでいるようですし、
私の方はなかなか次の話ができる見込みがないので、
私から剰余コラッツ予想についての話題を出すのは一旦休みたいと思います。
ここまでお付き合い下さった皆様、ありがとうございました。

260righ1113 ◆OPKWA8uhcY 2018/06/18(月) 03:15:08.94ID:WdqZRIIM
残念ですぅ

261132人目の素数さん2018/06/18(月) 08:13:14.97ID:M5JNYBjP
解決に結びつくような話ではないのでスレ違いなんだが、
アラン・チューリングがチューリング・マシンの論文を
発表したのが一九三六年で、ローター・コラッツが
コラッツ予想を提出したのが一九三七年だろ?
なんかしらの関係はあったんだろうかね?

262132人目の素数さん2018/06/18(月) 08:44:33.72ID:M5JNYBjP
やべぇ。コラッツ予想は連続体仮説や選択公理みたいに、
証明不能であるかもしれないという疑惑が出てきた。
>>244 >>245
で話題になってたのは Wolfram が提出した問題なんだが
コラッツ過程を実行するチューリングマシン
(テープ上に、1, 0, -(データなし)の三状態が記録できる。
で、二往復すると、コラッツ過程が1ステップ進む)が、
万能チューリングマシンであることが示されたらしい
>>245 の動画は、その実行例のデモ)。
そうなると、コラッツ予想は万能チューリングマシンの
停止性問題に帰着しそうな気がするんだが、どうだろう。
それとも「遷移規則をうまく構成する」ことで万能チューリングマシンを
実現することができるだけなので、「コラッツ予想を説くための
具体的な遷移規則」を与えたときに停止性が謂えるかどうかは、
まったくの別問題なのかな?

263righ1113 ◆OPKWA8uhcY 2018/06/18(月) 10:36:46.36ID:qNaPdH2s
>>262
Wolframが提示して学生が解いたチューリングマシンは2状態3色で、8状態3色のコラッツとは別物ですね。
https://ja.osdn.net/projects/descartes/wiki/ExPzWTuring
またおっしゃる通り、万能チューリングマシンに具体的な遷移規則を与えると、ある1つのチューリングマシンと等価になるので、万能性は消失すると思います。

264132人目の素数さん2018/06/18(月) 13:50:07.33ID:M5JNYBjP
>>263
ありがとう。安心した。

265132人目の素数さん2018/06/18(月) 21:39:43.70ID:mGDl57cN
コラッツ過程を実行するチューリングマシン
(テープ上に、1, 0, -(データなし)の三状態が記録できる。
で、二往復すると、コラッツ過程が1ステップ進む)が、
万能チューリングマシンであることが示されたらしい

これソースあるなら教えてくれる?
ひょっとしたら万能性が消失してないという話なのかもしれないので。
可能性は低いと思うけど。

266132人目の素数さん2018/06/19(火) 06:40:39.47ID:EReiwMfo
>>126
論文はこちら
ttp://www.wolframscience.com/prizes/tm23/TM23Proof.pdf
あとはこことか
ttp://reference.wolfram.com/language/example/VisualizeTheEvolutionOfATuringMachine.html.ja
動画はガイシュツだけどこれ
ttps://m.youtube.com/watch?v=t9nbkS-5bv8#

267132人目の素数さん2018/06/19(火) 06:46:57.18ID:EReiwMfo
あとはこれも
ttp://www.wolframscience.com/prizes/tm23/

268132人目の素数さん2018/06/19(火) 06:53:13.41ID:EReiwMfo
オートマトン関係ないけど、本筋的にはこんなのも
ttp://mathworld.wolfram.com/CollatzProblem.html

269132人目の素数さん2018/06/19(火) 22:10:02.87ID:3mIZP/N3
>>266
コラッツがチューリング完全とは書いてないっぽい

270132人目の素数さん2018/06/21(木) 13:52:02.84ID:qX+RK+7d
「何か進展はあるか?」みたいな話だとスレが進まないだろうけど、
「こういうアプローチはどうだろう?」みたいな
雑談っぽい話はあってもいいように思う。
このスレの住民は、悪戦苦闘したあげくに
このスレにいるわけだから、
たぶんバカにしたりとはしないぞ?
中学生とかが「こんな感じなんですけど、どうでしょうか?」
みたいな話をしたら、たぶん懇切丁寧に説明してくれるはずだ
(逆に、そういう初心者をバカにしたりしたら、総がかりで
ボコられると思う)。
このスレは数学板の中では、かなり優しいスレのうちに
入ると思う。

271132人目の素数さん2018/06/21(木) 19:09:13.28ID:3VWwsuqs
この手の問題は何をしたら証明したことになるのかが難しい
すぐに思いつくのは反例を見つけることだけど見つかる気がしない
この予想が正しかったら証明する方法なくね?って思ってしまう

272132人目の素数さん2018/06/21(木) 20:42:50.94ID:qX+RK+7d
>>271
とりあえず、ルートを逆に辿ることはできるんだから、
一意性は成り立っているわけだ。
だから、「任意の『4で割って1余る数』について、
なんかしらの順序的な保存量が定義できる」というのが表せれば、
証明になるんじゃないか?
現状、コラッツ操作によって値が上がったり下がったりするから、
「順序的な保存量」というのが定義できないわけだから。

273132人目の素数さん2018/06/21(木) 20:46:10.50ID:qX+RK+7d
>>271
あ、保存量として「何ステップで1に到達するか」を取るってのは
ナシだぞ?(笑) 「有限のステップで、必ず1に到達する」って
いうのが証明されてないわけだから。

274132人目の素数さん2018/06/22(金) 09:22:26.66ID:fZs8skv2
>>271
問題構造としては、「原始ピタゴラス数が三分木で表される」って
いうのと、ほぼ逆なんだよな。あっちは「最小の元から初めて、
三つの操作によってすべての元が一意に表せる」ことが解ってて、
「任意の元から最小の元へのルートが求められない」つーのが
問題だった。
コラッツ問題の場合は、「任意の元から最小の元へのルートが求められる
ことは、かなり確からしい(ただし、本当に最小の元へのルートがあるかは、
不明)」。で、「最小の元に二種類の操作を行なうことによって、
すべての元(任意の自然数)が一意に表される」かどうかは、
いまのところ不明であると。
なんか、自然数域から何か別の空間への写像を考えて、その別空間の
なかで、ある量に対する半順序構造が成り立つ、みたいなアプローチに
なるのかな?
たとえば f(128) < f(31) とか。

275132人目の素数さん2018/06/22(金) 09:46:11.31ID:fZs8skv2
わかりきったことを雑多に書くので落書きみたいなことに
なってしまうが、いちおう書いてみる。すまぬ。

2^∞=∞で、「2で割る」操作が無限回必要だから、これは考えない。
したがって、[1, ∞) という自然数の開集合の中で考える。
n が偶数の場合は、n/2 に帰着するので、
「[1, ∞)の中の奇数」({n|n は奇数かつ n∊[1, ∞)})について考えれば足りる。

で、たしか
n が n≡3(mod 4) のときは、そこから先に奇数が出てこないので、
「{n|n ≡ 1(mod 4) ∧ n∊[1, ∞)}」について考えれば足りる。
みたいな話になってたような気がするんだけど、これで議論は
足りてるかな?

276132人目の素数さん2018/06/22(金) 17:03:30.74ID:fZs8skv2
>>275
あ、ぜんぜん足りてねぇな。
n ≡ 0 (mod 3) のケースについての話がなんにもない。
そのあたり、真面目に(高校生にも解るように)書いてると、
なんかしらスレを消費するだけなんだよな。

誰か(スレ主とか)が「やれ」って言ってくれりゃあ、
やるけど。

277132人目の素数さん2018/06/22(金) 20:03:26.94ID:iMFpB+6q
ごめん保存量とか知らない単語が出てきて自分には理解できなかった

自分で考えてて思いついたのは数学的帰納法くらいで
1〜kの自然数が1に収束するならk+1も1に収束する、ということが言えれば証明できるのかなと
k+1が偶数なら次が(k+1)/2 < kだから1に収束する
k+1が4で割って1余るならkは4の倍数で次の3k+4も4の倍数
次の次が(3/4)k+1 < kだから1に収束する
あとはk+1が4で割って3余る場合を考えればいい
でもその先はパターンが無限の組み合わせになりそうだからこの方法では解けなさそう

278righ1113 ◆OPKWA8uhcY 2018/06/22(金) 20:38:25.49ID:8OiWJMk5
>>275
ここってどういう意味?
> n が n≡3(mod 4) のときは、そこから先に奇数が出てこないので、

279132人目の素数さん2018/06/22(金) 21:02:12.79ID:fZs8skv2
>>277
> ごめん保存量とか知らない単語が出てきて自分には理解できなかった
いや、数学的には正確になんというか知らんのだが、
全部の要素が順番に並んでて、
「最初のものについて成り立つ」
「あるものについて成り立つならば、“その次のもの”について成り立つ」
「だったら、全部のものについて成り立つ」
っていうのが、数学的帰納法だろ?
現代数学って、「次の数」ベースで成立してる(ペアノの公準。「数え主義」
あるいは「順序数による」定義)で成り立っているので、「加法が成立する」っていう「量に基づく
考え方」(基数による定義)とは、ちょっと相性が悪いんだ。
「1は自然数である」「自然数+自然数は自然数である」みたいなやりかたは、
現代数学じゃなくって、むしろ「算数」の考え方なんだよ。

280132人目の素数さん2018/06/22(金) 21:11:12.96ID:fZs8skv2
>>278
すまん。言葉が足りなかった。
そのあたりは、いちおう前のほうのエントリで議論は尽くされて
いると思うので、あらためて整理してからまた書く。
しばらく待っててくれ。

281132人目の素数さん2018/06/23(土) 07:13:55.05ID:if8U6rKp
話はかなり基礎的な話になる。
コラッツ予想は、“すべての有限な自然数”は、「偶数だったら2で割る」
「奇数だったら三倍して1を足す」という操作を繰り返してゆくと、
“有限回で” “必ず”1に到達する(そして1→4→2→1という
ループに落ちる)という話だ。
コラッツ予想の対偶は、逆操作である「2倍する」「1を引いて3で割る」という
操作を、1に対して有限回おこなうことで、“すべての数”に到達することができる、
というものだ。つまり、有限な自然数は、「2倍する」「1を引いて3で割る」
という二つの操作によって、1を根とした(有限の高さの)二分木構造を
なす、ということだ。

ここまでは、変なことは言ってないと思う。

2^∞を除く2の冪乗数は、プリミティブだから考えなくていい。
すべての偶数は、根のほうから見ると、奇数に2の冪乗数を
乗じたもので表されるから、「奇数の先にある」し
「奇数と奇数の間に出てくる」わけだから、考えなくていい。
このとき、 n が奇数のとき、3n + 1 は必ず偶数になるので、
コラッツ操作 3n + 1 は (3n + 1)/2 とし、逆問題が
「すべての有限な自然数」ではなくて「少なくともすべての有限な
基数(途中に出てくる偶数は、勘定に入れなくていい)」について
証明すれば足りる。

282132人目の素数さん2018/06/23(土) 07:21:29.24ID:if8U6rKp
ある奇数が 3 の倍数のとき、「×2」の操作を何度行なっても、
3 の倍数になる。そうすると、(3n + 1)/2 の逆操作が行なえない
(結果が自然数でなく分数になってしまう)ので、
「(n ではなく d(odd の d)と表記するとして)3 の剰余群
{0, 1, 2} のうち、d ≡ 1 または 2 のすべての有限な奇数が、1 を
根とした木の上にあることが示されれば、コラッツ予想は肯定的に
証明されることになる」と謂える。

283132人目の素数さん2018/06/23(土) 07:31:26.76ID:if8U6rKp
これをもう一段絞りこんで、4 の剰余群 {0, 1, 2, 3} のうち、d ≡ 1 (mod 4) の
場合にだけ注目すればいい、という話にならないか?ということ。
d ≡ 0 (mod 4) と d ≡ 2 (mod 4) は偶数なので、(逆操作の途中には
出てくるけれども)、証明の本質にはかかわってこない。
d ≡ 3 (mod 4) ということは、「下位ビットが 2 個以上の連続した
オンビット」なので、途中には出てくるけれど、d ≡ 1 (mod 4) の場合に
帰着する(つまり、d ≡ 1 (mod 4) の場合に吸収される)はずだ。

その結果、コラッツ予想は 3 と 4 の剰余群の直積集合上で考えていいわけで、
mod 12 で考えても一般性を失わないはず。

ただし、それで証明ができるかは別問題なんだが (-_-!)

284132人目の素数さん2018/06/23(土) 07:48:51.66ID:if8U6rKp
>>278
× > n が n≡3(mod 4) のときは、そこから先に奇数が出てこないので、
〇 > n が n≡0(mod 3) のときは、そこから先に奇数の枝が出てこないので、

285132人目の素数さん2018/06/23(土) 21:10:19.57ID:kMgEMQAn
以下、左が下位の2進表現とする
x→3x+1
10→00 10
01→11 10
10 01→00 11 10
10 01 01→00 11 11 10
10 01 01 01→00 11 11 11 10


27みたいなのはこういうパターンを踏んで大きくなるのか

286132人目の素数さん2018/06/24(日) 06:22:55.46ID:JZQSNXZT
最下位に 1 が連続して出てくると、そこからが
厄介なんですよ。
11 11 11 0### みたいなパターンを
[11 11 1 ]+[10###] と分けたとするでしょう?
そうすると、全体に五回 3x+1 操作を加えることは、
[10###] に5回 3x+2 操作を行なうのと等価になる。
それで 1 への収束が遅れるらしい。

だから、コラッツ予想を (m, n) という2変数に対する操作と
考えて、有限回で (0, 1) に到達するかどうか、と
言い換えるのはどうだろうか、と考えたことがある。

287132人目の素数さん2018/06/24(日) 06:32:53.97ID:JZQSNXZT
31 だと、
11111
*111101
**1110001
***1101011
****10000101
(中略)
*****/*/1101101
*****/*/*10010001
*****/*/**/1110011
*****/*/**/*11011001
*****/*/**/**10010111
*****/*/**/***/11110101
*****/*/**/***/*111000001
*****/*/**/***/**110100011
*****/*/**/***/***1000101001
(中略)
*****/*/**/***/****/*//***/**/111111001
*****/*/**/***/****/*//***/**/*111110111
*****/*/**/***/****/*//***/**/**1111001101
*****/*/**/***/****/*//***/**/***11101100001
*****/*/**/***/****/*//***/**/****11001010011
*****/*/**/***/****/*//***/**/*****101111101001
*****/*/**/***/****/*//***/**/******//1111000111
*****/*/**/***/****/*//***/**/******//*11101010101
*****/*/**/***/****/*//***/**/******//**110000000001
*****/*/**/***/****/*//***/**/******//***101000000011
と、途中で何度も 1 の連続が出てくるんで、なかなか収束しない。

288132人目の素数さん2018/06/24(日) 09:49:32.99ID:Ke8Ud7bS
f(x):=(3x+1)/2
b_k:=2^k-1 (k>1)
とおくと
f(2^(k+1)x+b_k)
=3 2^(k+1)x+3 2^k-2
=2^(k+1)×(3x+1) + (2^k-1) -1
=2^(k+1)f(x)+b_k-1

k>1の場合は
f(2^(k+1)x+b_k)=2×(2^(k)f(x)+b_(k-1))
2で割って以下繰り返すと最後(k=1)は
2f^k(x)になる、と。

なんというか……振り出しに戻された感が。

289132人目の素数さん2018/06/24(日) 10:36:18.55ID:JZQSNXZT
>>288
> なんというか……振り出しに戻された感が。
あるある(笑)
連分数とかやってると、なんだかんだで
また φ に戻ってくるとかな。
とはいえ数学って、「既存のアイディアの世界から
出る」つーのがエポックメーキングな仕事になる場合が
多いみたいな気がするから、そのあたりは宿命だと
思って諦めるしかないと思う。

290132人目の素数さん2018/06/24(日) 10:45:37.45ID:JZQSNXZT
>>288
ひょっとして、けっこう昔からプログラマやってる方?
「:=」って、Pascal とかでしょ。
数学屋さんだったら、
b_k:=2^k-1 (k>1)
より
Me(n) = 2^n - 1 (n = 0 のとき偶数。0 < n のとき奇数)
とか書きそうな気がした。私も元がプログラミング畑だから、
数学の分野の言い回しに慣れるのに時間がかかったな。

291132人目の素数さん2018/06/24(日) 13:11:45.44ID:Ke8Ud7bS
プログラマでもあるけど、
数学でも定義で:=表記を使うことはあるよ
卒論はどうだったかなー、とレジュメ見たら使ってたし

292132人目の素数さん2018/06/24(日) 14:11:36.72ID:JZQSNXZT
>>291
そうか。深読みしすぎてゴメン。
なんにせよ数学畑の人が、
このスレに興味を持ってくれているのが
嬉しい(個人的な感想だから、そのあたりは
スレ主との合意が必要なんだが)。

293132人目の素数さん2018/06/24(日) 14:38:08.41ID:JZQSNXZT
スレ主の 78righ1113 氏と相談なんだが、
コテハン(=固定ハンドル)のほうが、たぶん分かりやすいので、
使っちゃっていいかな?
(別板から変なのが来て、荒れると不本意なので)

294righ1113 ◆OPKWA8uhcY 2018/06/24(日) 14:40:49.97ID:prj5qOCW
>>293
使っても良いですよ

295M.B.2018/06/24(日) 15:06:01.07ID:JZQSNXZT
>>294
ありがとうございます。
お婆ちゃんだけど、よろしこ。

前のエントリを明らかにしようと思ったら、
「レスアンカーが多すぎます!」とか言われてハネられちゃったわ。

                  「梅干し婆」と呼ばれるけれど
                  鶯泣かせた春もある

新着レスの表示
レスを投稿する