前スレ コラッツ予想がとけたらいいな
https://rio2016.5ch.net/test/read.cgi/math/1350178359/
>>1の証明（未検証）
https://github.com/righ1113/collatzProof
それより弱い成果もあります（未検証）
コラッツのループはあるとしてもとても長い
https://github.com/righ1113/collatzLongLoop
探検
コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
前スレ コラッツ予想がとけたらいいな
https://rio2016.5ch.net/test/read.cgi/math/1350178359/
>>1の証明（未検証）
https://github.com/righ1113/collatzProof
それより弱い成果もあります（未検証）
コラッツのループはあるとしてもとても長い
https://github.com/righ1113/collatzLongLoop
たぶん新しめのブラウザでないと動かない
最上位の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;
}
ん、これコラッツのプッシュダウンオートマトンなの？
ただのオートマトン
コラッツってそんな弱いの？
「ある整数からコラッツ問題の通りに計算を続けて1に到達する」と
「ある整数に対応する初期状態から開始すると止まる」が同値になるオートマトンは作れるかな？
というわけで作ってみたのだが
パッと見、チューリングマシンのようにも見える。LとかRとかあるし。
チューリングマシンだったねこれ
チューリングマシンをオートマトンの一種とするならオートマトンといえなくもないかもですが……
有限オートマトンではありません
なんかごっちゃになってましたねー
コラッツ予想が真なら究極的には1状態有限オートマトンでもおｋなわけだから無い話ではないはず。
私の方はなかなか次の話ができる見込みがないので、
私から剰余コラッツ予想についての話題を出すのは一旦休みたいと思います。
ここまでお付き合い下さった皆様、ありがとうございました。
アラン・チューリングがチューリング・マシンの論文を
発表したのが一九三六年で、ローター・コラッツが
コラッツ予想を提出したのが一九三七年だろ？
なんかしらの関係はあったんだろうかね？
証明不能であるかもしれないという疑惑が出てきた。
>>244 >>245
で話題になってたのは Wolfram が提出した問題なんだが
コラッツ過程を実行するチューリングマシン
（テープ上に、1, 0, -（データなし）の三状態が記録できる。
で、二往復すると、コラッツ過程が１ステップ進む）が、
万能チューリングマシンであることが示されたらしい
（>>245 の動画は、その実行例のデモ）。
そうなると、コラッツ予想は万能チューリングマシンの
停止性問題に帰着しそうな気がするんだが、どうだろう。
それとも「遷移規則をうまく構成する」ことで万能チューリングマシンを
実現することができるだけなので、「コラッツ予想を説くための
具体的な遷移規則」を与えたときに停止性が謂えるかどうかは、
まったくの別問題なのかな？
Wolframが提示して学生が解いたチューリングマシンは2状態3色で、8状態3色のコラッツとは別物ですね。
https://ja.osdn.net/projects/descartes/wiki/ExPzWTuring
またおっしゃる通り、万能チューリングマシンに具体的な遷移規則を与えると、ある1つのチューリングマシンと等価になるので、万能性は消失すると思います。
ありがとう。安心した。
（テープ上に、1, 0, -（データなし）の三状態が記録できる。
で、二往復すると、コラッツ過程が１ステップ進む）が、
万能チューリングマシンであることが示されたらしい
これソースあるなら教えてくれる？
ひょっとしたら万能性が消失してないという話なのかもしれないので。
可能性は低いと思うけど。
論文はこちら
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#
ttp://www.wolframscience.com/prizes/tm23/
ttp://mathworld.wolfram.com/CollatzProblem.html
コラッツがチューリング完全とは書いてないっぽい
「こういうアプローチはどうだろう？」みたいな
雑談っぽい話はあってもいいように思う。
このスレの住民は、悪戦苦闘したあげくに
このスレにいるわけだから、
たぶんバカにしたりとはしないぞ？
中学生とかが「こんな感じなんですけど、どうでしょうか？」
みたいな話をしたら、たぶん懇切丁寧に説明してくれるはずだ
（逆に、そういう初心者をバカにしたりしたら、総がかりで
ボコられると思う）。
このスレは数学板の中では、かなり優しいスレのうちに
入ると思う。
すぐに思いつくのは反例を見つけることだけど見つかる気がしない
この予想が正しかったら証明する方法なくね？って思ってしまう
とりあえず、ルートを逆に辿ることはできるんだから、
一意性は成り立っているわけだ。
だから、「任意の『４で割って１余る数』について、
なんかしらの順序的な保存量が定義できる」というのが表せれば、
証明になるんじゃないか？
現状、コラッツ操作によって値が上がったり下がったりするから、
「順序的な保存量」というのが定義できないわけだから。
あ、保存量として「何ステップで１に到達するか」を取るってのは
ナシだぞ？（笑） 「有限のステップで、必ず１に到達する」って
いうのが証明されてないわけだから。
問題構造としては、「原始ピタゴラス数が三分木で表される」って
いうのと、ほぼ逆なんだよな。あっちは「最小の元から初めて、
三つの操作によってすべての元が一意に表せる」ことが解ってて、
「任意の元から最小の元へのルートが求められない」つーのが
問題だった。
コラッツ問題の場合は、「任意の元から最小の元へのルートが求められる
ことは、かなり確からしい（ただし、本当に最小の元へのルートがあるかは、
不明）」。で、「最小の元に二種類の操作を行なうことによって、
すべての元（任意の自然数）が一意に表される」かどうかは、
いまのところ不明であると。
なんか、自然数域から何か別の空間への写像を考えて、その別空間の
なかで、ある量に対する半順序構造が成り立つ、みたいなアプローチに
なるのかな？
たとえば f(128) < f(31) とか。
なってしまうが、いちおう書いてみる。すまぬ。
2^∞＝∞で、「２で割る」操作が無限回必要だから、これは考えない。
したがって、[1, ∞) という自然数の開集合の中で考える。
n が偶数の場合は、n/2 に帰着するので、
「[1, ∞)の中の奇数」（{n|n は奇数かつ n∊[1, ∞)}）について考えれば足りる。
で、たしか
n が n≡3(mod 4) のときは、そこから先に奇数が出てこないので、
「{n|n ≡ 1(mod 4) ∧ n∊[1, ∞)}」について考えれば足りる。
みたいな話になってたような気がするんだけど、これで議論は
足りてるかな？
あ、ぜんぜん足りてねぇな。
n ≡ 0 (mod 3) のケースについての話がなんにもない。
そのあたり、真面目に（高校生にも解るように）書いてると、
なんかしらスレを消費するだけなんだよな。
誰か（スレ主とか）が「やれ」って言ってくれりゃあ、
やるけど。
自分で考えてて思いついたのは数学的帰納法くらいで
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余る場合を考えればいい
でもその先はパターンが無限の組み合わせになりそうだからこの方法では解けなさそう
ここってどういう意味?
> n が n≡3(mod 4) のときは、そこから先に奇数が出てこないので、
> ごめん保存量とか知らない単語が出てきて自分には理解できなかった
いや、数学的には正確になんというか知らんのだが、
全部の要素が順番に並んでて、
「最初のものについて成り立つ」
「あるものについて成り立つならば、“その次のもの”について成り立つ」
「だったら、全部のものについて成り立つ」
っていうのが、数学的帰納法だろ？
現代数学って、「次の数」ベースで成立してる（ペアノの公準。「数え主義」
あるいは「順序数による」定義）で成り立っているので、「加法が成立する」っていう「量に基づく
考え方」（基数による定義）とは、ちょっと相性が悪いんだ。
「１は自然数である」「自然数＋自然数は自然数である」みたいなやりかたは、
現代数学じゃなくって、むしろ「算数」の考え方なんだよ。
すまん。言葉が足りなかった。
そのあたりは、いちおう前のほうのエントリで議論は尽くされて
いると思うので、あらためて整理してからまた書く。
しばらく待っててくれ。
コラッツ予想は、“すべての有限な自然数”は、「偶数だったら２で割る」
「奇数だったら三倍して１を足す」という操作を繰り返してゆくと、
“有限回で” “必ず”１に到達する（そして１→４→２→１という
ループに落ちる）という話だ。
コラッツ予想の対偶は、逆操作である「２倍する」「１を引いて３で割る」という
操作を、１に対して有限回おこなうことで、“すべての数”に到達することができる、
というものだ。つまり、有限な自然数は、「２倍する」「１を引いて３で割る」
という二つの操作によって、１を根とした（有限の高さの）二分木構造を
なす、ということだ。
ここまでは、変なことは言ってないと思う。
２^∞を除く2の冪乗数は、プリミティブだから考えなくていい。
すべての偶数は、根のほうから見ると、奇数に2の冪乗数を
乗じたもので表されるから、「奇数の先にある」し
「奇数と奇数の間に出てくる」わけだから、考えなくていい。
このとき、 n が奇数のとき、3n + 1 は必ず偶数になるので、
コラッツ操作 3n + 1 は (3n + 1)/2 とし、逆問題が
「すべての有限な自然数」ではなくて「少なくともすべての有限な
基数（途中に出てくる偶数は、勘定に入れなくていい）」について
証明すれば足りる。
3 の倍数になる。そうすると、(3n + 1)/2 の逆操作が行なえない
（結果が自然数でなく分数になってしまう）ので、
「（n ではなく d（odd の d）と表記するとして）3 の剰余群
{0, 1, 2} のうち、d ≡ 1 または 2 のすべての有限な奇数が、1 を
根とした木の上にあることが示されれば、コラッツ予想は肯定的に
証明されることになる」と謂える。
場合にだけ注目すればいい、という話にならないか？ということ。
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 で考えても一般性を失わないはず。
ただし、それで証明ができるかは別問題なんだが (-_-!)
× > n が n≡3(mod 4) のときは、そこから先に奇数が出てこないので、
〇 > n が n≡0(mod 3) のときは、そこから先に奇数の枝が出てこないので、
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みたいなのはこういうパターンを踏んで大きくなるのか
厄介なんですよ。
11 11 11 0### みたいなパターンを
[11 11 1 ]+[10###] と分けたとするでしょう？
そうすると、全体に五回 3x+1 操作を加えることは、
[10###] に５回 3x+2 操作を行なうのと等価になる。
それで 1 への収束が遅れるらしい。
だから、コラッツ予想を (m, n) という２変数に対する操作と
考えて、有限回で (0, 1) に到達するかどうか、と
言い換えるのはどうだろうか、と考えたことがある。
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 の連続が出てくるんで、なかなか収束しない。
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)になる、と。
なんというか……振り出しに戻された感が。
> なんというか……振り出しに戻された感が。
あるある（笑）
連分数とかやってると、なんだかんだで
また φ に戻ってくるとかな。
とはいえ数学って、「既存のアイディアの世界から
出る」つーのがエポックメーキングな仕事になる場合が
多いみたいな気がするから、そのあたりは宿命だと
思って諦めるしかないと思う。
ひょっとして、けっこう昔からプログラマやってる方？
「:=」って、Pascal とかでしょ。
数学屋さんだったら、
b_k:=2^k-1 (k>1)
より
Me(n) = 2^n - 1 (n = 0 のとき偶数。0 < n のとき奇数)
とか書きそうな気がした。私も元がプログラミング畑だから、
数学の分野の言い回しに慣れるのに時間がかかったな。
数学でも定義で:=表記を使うことはあるよ
卒論はどうだったかなー、とレジュメ見たら使ってたし
そうか。深読みしすぎてゴメン。
なんにせよ数学畑の人が、
このスレに興味を持ってくれているのが
嬉しい（個人的な感想だから、そのあたりは
スレ主との合意が必要なんだが）。
コテハン（＝固定ハンドル）のほうが、たぶん分かりやすいので、
使っちゃっていいかな？
（別板から変なのが来て、荒れると不本意なので）
使っても良いですよ
ありがとうございます。
お婆ちゃんだけど、よろしこ。
前のエントリを明らかにしようと思ったら、
「レスアンカーが多すぎます！」とか言われてハネられちゃったわ。
「梅干し婆」と呼ばれるけれど
鶯泣かせた春もある
たとえば 10 = 0101(2)と表すことにする。
これを左右ひっくり返したものを 「(r2)」と
表記することにすると、10 = 0101(2) = 1010(r2) と
なる。
Me(k) = 2^k - 1
とおいて、
X(n) = {Me(p) + 2^p × q}
を、
(p, q)
と表記することにする。
q ≡ 3 (mod 4) のとき、q は (r2) で表したときに、
q は 11### … #(r2) で表される。このとき、
操作 A について、A(p, q) は (p + 1, (q - 1)/2) であるとする。
また、q が偶数であるとき、
操作 B について B(p, q) は (p, q / 2) であるとする。
さらに、1 < p のとき、
操作 C について、C(p, q) は (p - 1, (q × 3) + 2) であるとする。
n = 1 のとき、n = (p, q) = (0, 1) である。これをかりに e とおく。
コラッツ予想は、すべての有限の自然数である n について、
n = BBABCAB……e が有限長の記号列である、という主張と
同義である。
―― みたいなコトを考えたんだけど、これって方向性として、
どう思います？
あ、ごめんなさい。
q = 0 かつ q ≡ 1 (mod 4)のとき、
D(p, q) = (p, q) = (p, 3×q + 1) = (0, 3×q + 1) っていうのが
抜けてた。
× q = 0 かつ q ≡ 1 (mod 4)のとき、
〇 p = 0 かつ q ≡ 1 (mod 4)のとき、
う〜ん、今の時点では何とも……
剰余コラッツ予想の時みたいに、何か部分的な成果があると良いのですが……
肝心なことを書き忘れていました。
A・B・C・D は、演算子あるいは作用素みたいなものなんです。
これに対して、ノルム（絶対値みたいなものです）を (p, q) に
対して与える関数 N((p, q)) を考えます。
このとき、操作 A・B・C・D に対してノルムが単調減少し、
すべての有限な量 (p, q) に対して N() が有限であるということが
証明されれば、コラッツ予想は肯定的に証明された、と
謂えるように思います。
もっとも、N が実数に対して写像されちゃうと、
「１／２ を何回掛けても 0 にはならない」みたいに
底抜けになってしまうので、N() はあくまで
整数域に対する関数でないと困るわけですが。
> 何か部分的な成果があると良いのですが……
p は上下しながら 0 に向かっているというのは
数値実験上は傾向として掴んでいるのですが、
メルセンヌ数を与えたときに、初期値の p を超えちゃう
場合があるんですよね。
>>287 における p = 5 から p = 6 とか。
ただ、>>287 を見てもらえれば お分かりになると
思うんですけど、この逆転が起きるのは、q に
(3n + 1) / 2 操作を施した場合に限られていそうに
思うんですよ。
そうなると、「p が増加しない」が謂えて、
「無限ループが存在しない」が謂えれば、
なんとか抑えこめそうな気がしています。
剰余コラッツ予想の場合でも、
「かりに無限ループが存在しても、
その周期は 5×2^60 より長い」みたいな
下限は与えられそうに思うんですが。
なお、仮に N() が具体的に求められたとしても、μ再帰関数である
アッカーマン関数のように、とんでもなく大きい値を与える
関数になってしまい、具体的な上限値が計算できるようなシロモノ
ではなかろう、と予想しています。
だけど有限は有限なので、「少なくとも無限ではない」という意味で、
証明に結びつきうるのではないかと考えています。
(上から目線でｽﾏﾅｲ)
いくつかの「思う」を『定理』『補題』として言えれば、もっと素晴らしくなると思います。
念のため。
じつは、このアイデアは「原始ピタゴラス数は三分木をなす」という
Barning と Hall の定理（小林吹代『ピタゴラス数を生み出す
行列のはなし』参照）が元ネタです。e = {3, 4, 5} に行列
U・D・A を順次掛けてゆくと、すべての原始ピタゴラス数が
一意に表されます。
原始ピタゴラス数は、「互いに素で偶奇が異なる自然数 (m, n)
（0 < m < n）」、または「互いに素な奇数 (p, q)（0 < p < q）」
で表されます。ここで、m × n または p × q が単調減少し、
その減少のしかたが三通りあって、それぞれが U・D・A を掛ける
操作と対応することを示しました。
この定理の “泣きどころ” は、任意の原始ピタゴラス数を与えたときに、
それを e と U・D・A の列の積の形に分解できない（逆問題が解決
されていない）点だったのですが、このアプローチで解決できました。
コラッツ問題は、問題の設定としてはこの逆で、任意の n から
e へのルートがあるのは確からしいのに、それが e に収束するか
どうかが（途中の値が一見カオティックに上下するために）、
「（Barning = Hall 問題のような m × n や p × q のような）
単調減少するノルムに対応させることができていない」という
ところに難関があると考えています。
なお、「泣きどころ」うんぬんの話は、細矢治夫『トポロジカル・インデックス ー
フィボナッチ数からピタゴラスの三角形までをつなぐ新しい数学』
にありました。同書には細矢先生が Barning = Hall 問題
にどのようにアプローチしたかが丁寧に書かれていて、興味ぶかく
読ませていただきました。
x^2 + y^2 = z^2 のとき、
{x, y, z} = {n^2 - m^2, 2× m × n, m^2 + n^2}
がいえて、
{m, ABS(n - 2m)} が新しい m, n の値（順不同。小さいほうが m）に
なります。
なお、e = {3, 4, 5} = (1, 2) です。2 - 1×2 が 0 になっちゃうので、
行きどまりになり、ここが三分木の根になります。
（「２倍する」と「２倍して１を引いてから３で割る」）が
実質的に同じものと見なせる」ことを示す、というアプローチも
考えられます。
(m, ABS(n - 2m)) → (m, n)
がなぜ三分木に対応するかというと、この操作の逆操作が
・m に n の二倍を足す
・n に m の二倍を足す
・n の二倍から m を引く
という三つの操作に対応するからです（m × n の長方形を
考えるとわかりやすいです。互除法の変形です。互除法
なので、連分数とかかわってきます）。
ただ、このアプローチはせめて「コラッツ操作によって、
任意の n についての中間値が最大どこまで大きくなるか」の
上限値を n の関数として表せないと無理筋なので、
攻めるとすればここかな？と思っています。つまり、「最下位の
オンビット列の連鎖が、どう現れるのか」です。
連投ごめんなさい。m(_ _)m
佐藤 郁郎先生（ttp://www.geocities.jp/ikuro_kotaro/）に
「コラッツ予想も、Barning = Hall 問題のノリで
解けるかもしれない」みたいな話をしちゃったのが
きっかけなんですよ。
みなさん、期待されてます。
xから始まってコラッツの操作で到達できる数のうち最大のものをcollatz_max(x)とする
あるnとcが存在しn<xならばlog(collatz_max(x))/log(x)<=cが言える。
それって、かなり確からしいけど、
リーマン予想みたいに「例外がない」ことを示すのが
難しいっていうのが泣きどころなのよねぇ ……
コテ名乗るならトリつけたほうがよくない？
ひょっとしたらこのスレから世紀の発見ってこともかんがえられるしｗ
蒸し返しです。
オートマトンに関連する話題なんだけど、
「一斉射撃の問題」というのがあって、これはいろいろ研究されてて
コラッツ問題の解決のヒントになるかもしれないな、と思っています。
「オートマトンが 0 番から m 番まで (m + 1) 個並んでいる。左端の
A0 から、時刻 0 で、ある信号が発せられた。一定の時間後に (m + 1)個が
すべてのオートマトンが同時に特別の状態（「射撃」状態）にはいるように、
オートマトンの動作表を設計せよ。」
これを変形すると、「0 から、ある状態にセットされたオートマトンが
あったときに、その状態は無限遠（m が無限）まで到達できない」ことが
示されるかどうかという話に持ってゆけます。これだと、「２で割る」という
操作は「先頭位置がズレてゆく」ことになりますので、また違った面から
議論できそうに思います。
「歴史的な背景などについては、後藤英一：一斉射撃の問題。数理科学
１１−１０、４２−４６（１９７３）を参照のこと。また、小林考次郎：
オートマトン理論のパズル、数理科学１９７６年１１月増刊「パズルＩ」にも
解説がある。」とのこと。
出典は 有澤誠『プログラミング レクリエーション ー ソフトウェア実習の
ガイド』（近代科学社）、p.132。
べつにいいじゃない。このスレがきっかけになるんなら。
だいたい、独立に発見された定理なんか、山ほどあるでしょうに。
まあ無理強いはしませんがね。
いる」とはおそらく関係しないけど、「先頭位置が、必ずしも
「一回一回の操作が終了する」まで待たなくてよくて、先頭から
次々とシグナルが送られてゆく、と考えてもいいわけですよね？
だったら、テープワームみたいな形でネットに放して、
空いてるコンピュータ・リソースを総動員して「どこまで正しいか」を
検証するという手はあるかと思います（犯罪っぽいけど）。
数学板だと、誰が喋ってんのかわかんないと文脈っつーか
脈絡っつーか、そういうのが分かりにくいんじゃないかなー、という
配慮です。
だいたい、あたしの騙りとかって、難しいと思うよ？
n以下の自然数の中にlog(collatz_max(x))/log(x)>=3を満たすようなxが存在するか？
という問いはNP問題になると思う。
これをSATとしてあらわしてSATソルバに食わせて一気にデカいnについて解くというのはどうだろうか？
コラッツの過程を計算するのに指数リソース食うかも
xを入力としてxとcollatz_inverse_min(x)が等しいかどうかは多項式時間で判定できるか？
Me(k) についてプロットしてみる、とかいうのも
面白そう。
『【好調】Java の宿題ここで答えます【三巡目】』
（ttps://pc5.5ch.net/test/read.cgi/tech/1100565043/）
＞＞38 以降とか。
兄者は件のサーバーアプリを再興しようと、
マ板でのさばっておりますわん。
Coqに移植できました。
Coqの関数は全て停止するので、例のプログラムも停止する事になって、
『剰余コラッツ予想は真！』
……と言いたいところですが、怪しさ満載ですので、今しばらく調査します。
Coq については名前を聞いたことがあるぐらいで詳しくは知りませんが、
なにか手伝えることがあればおっしゃってください。
Coqというプログラミング言語(定理証明支援系)では、再帰関数を作る際に、停止性をチェックされて、それをパスした関数だけが定義されます。
手伝って欲しいことは後々出てくると思うので、よろしくお願いします。
> Coqというプログラミング言語(定理証明支援系)では、再帰関数を作る際に、停止性をチェックされて、それをパスした関数だけが定義されます。
最近のCoqの現状は全く知らないのですが、そもそもCoqの文法に従って（チェックされなければ）停止しない関数を書けるような構文になってましたっけ？
Coqは構成的型理論と呼ばれるものに属する形式的体系の１つに基づいているので、その基づいている型理論に即して素直に項の構文（関数はこの構文を使って定義することになるので
この構文がその構成的型理論の体系が与えるプログラミング言語に相当する）を作ると、そもそも停止するか否かがわからないような関数を定義することは構文的に不可能だと理解しているのですが
それとも最近のCoqは書きやすさとかのためにgeneral recursionのような書き方を許す構文も導入しているのかなあ
おかえりなさ〜い！
質問の答えになっているか分からないですが、
今回の方法だと、再帰関数を書き終えた時点で証明モードに入って、そこでの証明を終えると、関数が定義されます。
具体的には、Coq.Program.Wfをインポートして、減少する引数をmeasureで指定して、Program Fixpointで関数を書きます。
https://www.google.com/url?q=http://d.hatena.ne.jp/airobo/touch/20130729/1375109706&sa=U&ved=0ahUKEwiAtI7aq_fbAhUIjpQKHc5jA0wQFggLMAA&usg=AOvVaw0Z5Y7z7Pexxi_2FgNFFFX2
あれは高度な数学力とプログラミング力を要するからな。
前スレで教えてもらいました。
レスありがとうございます。
> 今回の方法だと、再帰関数を書き終えた時点で証明モードに入って、そこでの証明を終えると、関数が定義されます。
> 具体的には、Coq.Program.Wfをインポートして、減少する引数をmeasureで指定して、Program Fixpointで関数を書きます。
例を拝見しました。なるほど、関数そのものは構文としては文字通りのfixpointつまりgeneral recursionで定義するのを許す代わりに
停止性を保証するmeasureを自分で与えて停止性証明を正しく構成しなければ関数定義として認めないということですか。
構造帰納法で上手く定義できない関数を扱う上では強引な印象もありますが、実用的にはとても役に立ちそうなアプローチですね。
御教示どうもありがとうございました。
問題点は、19x+1版にしても、Coqは「停止する」って言っているのです。
19x+1版は、>>92で反例が出ています。
以下が考えられます。
・Coqの停止性の証明が間違っている
・オールNothingが出ても無限走行するとは限らない
これらを調査しないといけないのですが、
すみませんがマイペースでやらせて下さいf(^_^;
>>272が言ってたことだよね？
ホントならかなりすごいよね？
>>786氏に見て欲しいことがあるのです。
・オールNothingが出ても無限走行するとは限らない
オールNothingが出た後、本当に無限走行するのか、アルゴリズムで見ていただけないでしょうか。
なるほど了解です。考えてみます。
>>338
これは剰余コラッツ予想(>>2)についての話なので>>272は関係ないかと…
例えば
「C の元を 3 倍して 1 を加えて C' のどのグループに属するか調べる」
のときにオールNothingが出たとします。
この後に「上の作業で得られた C' のグループ」を用いて組を探すことになりますが、
これは空集合なので再びオールNothingとなります。
以下同様に繰り返し、延々とオールNothingが繰り返さることになります。
ありがとうございます。
ということは、僕のCoqの証明がどこか間違っているのですね。お騒がせしました。
剰余系で考えると関係ないですねぇ。順序性が成り立たないので。
ちなみに >>272 は私。
移植の際になにかアルゴリズム変えたとか考えられないの。
これは「あんたが真面目にプログラム書いて、結果を出して書け」って
いうことなのよね？
雑談レベルでもいいから、進捗でも聞きたいわぁ。
■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 政府、コロナワクチン啓発に「YouTuber起用動画9本・3200万円支出」認める「接種の重要性など、正しい情報を知っていただくために」 ★2 [Hitzeschleier★]
- 「ドンドンショボくなる」大阪万博にまたまた“ガッカリ”報道、軟弱地盤のため「乗り物型」展示ゼロ [バイト歴50年★]
- 他候補者に「おい売国奴」拡声器で罵声、「凸」と称して迷惑行為も…東京15区補選で何が起きているのか [バイト歴50年★]
- 【鉄道】女性「電車で隣に座ってくる男キモい」SNS“炎上”…男女で《賛否》真っ二つ、それぞれの言い分とは ★3 [ぐれ★]
- 【文春】「相合い傘で自宅マンションへ…」内田理央と人気YouTuberヒカルの寿司デート＆お泊まり愛“スクープ撮 [Ailuropoda melanoleuca★]
- 【人口】全体の４割超の７４４自治体が「消滅可能性」 ３０年間で２０～３９歳の女性半減で該当 [ぐれ★]
- あえ・・・・・？？？？？ …おいたんたち、おねんねちないの？？？？？
- 【悲報】日本のテレビアニメが北朝鮮製だった問題、思ったよりもヤバそう [455830913]
- スクリプとに負けないお🏡!
- 長谷川亮太 ちばけんま 唐澤貴洋 無能弁護士
- 二次元以上の正常な哺乳類でなく、その行為は非倫理的に言えば生肉君もヴィーガンだけど
- あむあむと俺どっちか一人だけ助けられます