アカウント名:
パスワード:
広告文に「解法は証明または反証」とあるけど、「決定不能と証明される」って落ちもあるよね。普通に停止問題だし、コラッツの初期値でゲーデル文を構成するだとか、実はチューリング完全だ(んなわけないが)と証明するとかそんな雰囲気の。
ついでに言えば公理系を指定しないのもちょい怖い。適当な公理系をでっち上げれば証明できるだろうけど、あとはどうやって「世界の数学界に一般的に受け入れられ」たと認めさせるか。数学者の興味を引く面白い公理系を頑張って作ると言うルートもあるかもね。
個人的には「実は全て停止するけど、証明も反証も決定不能と証明することもできない停止問題」ってパターンだと思う。
決定不能と証明されたら、それはイコール成り立つことの証明だよ。
たった一つでも成り立たない数値を見つけたらそれが反証になるし、決定できるという証明になる。つまり決定不能と証明されるというのは、成り立たない数値を見つけることができないという証明でもあり、成り立たない数値を見つけれないならそれは成り立つことになる。
> 成り立たない数値を見つけれないならそれは成り立つことになる。これを認める公理系と認めない公理系があるでしょ。
「決定不能」ってのは「実際に反証になる初期値が見つかるか、そんなものがないか」ってことでしょ。で仮にそんなものがなければ本当に決定不能。要は実際に計算するまで分からないという停止問題の定番。例えば「3.14以下の円周率に~兆回(適当な大きい数字)の0の連続が存在するか」という命題みたいなもん。小さけりゃ普通に見つかるけど十分大きいとおそらく存在しないがそれをたぶん証明できない。
十分大きいと存在しない、のかな十分探せばあるんじゃないのかな
コラッツ予想はΠ_1文で書けるから決定不能なら真だよ
検索したけど「Π_1文」が何か分からなかった。数学用語って検索しづらい。
算術的階層を見ればいい。https://ja.wikipedia.org/wiki/%E7%AE%97%E8%A1%93%E7%9A%84%E9%9A%8E%E5%B1%A4 [wikipedia.org]
π1はπ0 1と同じと考えていい。
よく考えるとコラッツ予想が偽の場合、コラッツ数列の長さが無限になる可能性があるからΠ_1文で書けるかどうかはそれほど自明じゃないな
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
にわかな奴ほど語りたがる -- あるハッカー
惜しい (スコア:0)
広告文に「解法は証明または反証」とあるけど、「決定不能と証明される」って落ちもあるよね。
普通に停止問題だし、コラッツの初期値でゲーデル文を構成するだとか、実はチューリング完全だ(んなわけないが)と証明するとかそんな雰囲気の。
ついでに言えば公理系を指定しないのもちょい怖い。
適当な公理系をでっち上げれば証明できるだろうけど、あとはどうやって「世界の数学界に一般的に受け入れられ」たと認めさせるか。
数学者の興味を引く面白い公理系を頑張って作ると言うルートもあるかもね。
個人的には「実は全て停止するけど、証明も反証も決定不能と証明することもできない停止問題」ってパターンだと思う。
Re: (スコア:0)
決定不能と証明されたら、それはイコール成り立つことの証明だよ。
たった一つでも成り立たない数値を見つけたらそれが反証になるし、決定できるという証明になる。
つまり決定不能と証明されるというのは、成り立たない数値を見つけることができないという証明でもあり、成り立たない数値を見つけれないならそれは成り立つことになる。
Re: (スコア:0)
> 成り立たない数値を見つけれないならそれは成り立つことになる。
これを認める公理系と認めない公理系があるでしょ。
Re: (スコア:0)
「決定不能」ってのは「実際に反証になる初期値が見つかるか、そんなものがないか」ってことでしょ。
で仮にそんなものがなければ本当に決定不能。要は実際に計算するまで分からないという停止問題の定番。
例えば「3.14以下の円周率に~兆回(適当な大きい数字)の0の連続が存在するか」という命題みたいなもん。
小さけりゃ普通に見つかるけど十分大きいとおそらく存在しないがそれをたぶん証明できない。
Re: (スコア:0)
十分大きいと存在しない、のかな
十分探せばあるんじゃないのかな
Re: (スコア:0)
コラッツ予想はΠ_1文で書けるから決定不能なら真だよ
Re: (スコア:0)
検索したけど「Π_1文」が何か分からなかった。
数学用語って検索しづらい。
Re: (スコア:0)
算術的階層を見ればいい。
https://ja.wikipedia.org/wiki/%E7%AE%97%E8%A1%93%E7%9A%84%E9%9A%8E%E5%B1%A4 [wikipedia.org]
π1はπ0 1と同じと考えていい。
Re: (スコア:0)
よく考えるとコラッツ予想が偽の場合、コラッツ数列の長さが無限になる可能性があるからΠ_1文で書けるかどうかはそれほど自明じゃないな