What Computers Can Never Do [English Subtitles]

[@sakamiyari]

この証明が1936年に解かれていたのが驚きでしかありません...。

[@ねぎとろ餅]

なお、兵庫県警を使うことでこの問題は解決（？）できるらしい
(「兵庫県警　停止性問題」で検索)

[@warokihami]

あーｗあれかｗ

[@integlim]

「自己言及のパラドックス」だったか「天使と悪魔のパラドックス」で聞いたのと似たような話に感じました

[@okmen6186]

ディオファントス方程式の一般的な解法が存在しないこともこれを使って示しますね。

[@シュウェップスビターレモンの復刻を]

いつもよりプログラム寄りだから一時停止しなくても理解できたけど、逆にいつものやつの圧縮っぷりにビビる

[@pemen-m3z]

「ピノキオ君、君の鼻は10秒後に伸びているかい？」

[@nobreads_456]

-10cm伸ばして「伸ばした(-10cm)けど伸ばしてない(縮めた)」って言い張れば…

[@タンガンちゃん]

ぜ、ぜんぜん分かんないかった…
えっと、アレ？全能神に｢誰にも持ち上げられない岩を作って｣って言った後｢それを持ち上げて｣って言うみたいなこと…なのかな？合ってる…？

[@evimalab]

はい。
持ち上げられたら岩を作るのに失敗していて、持ち上げられなかったらもちろん全能ではありません。

[@タンガンちゃん]

@@evimalab
よかった、ちゃんと理解できていたようです！
助かります〜

[@magurofly]

レベルαのプログラムはレベルβ（

[@1つ星]

（強）正規化定理から、β簡約を繰り返せば、必ず正規形にたどり着きますからね。なので型付きラムダ計算は（強）停止性を持ちます。
しかし、型付きラムダ計算で定義できる関数のクラスは、全ての帰納関数のクラスより小さくなりますね。再帰表現ができません。演算子を加えていき、帰納関数全てを表現出来てしまうとやはり、停止性がなくなります。
つまり、表現の強さと停止性がトレードオフみたいな関係になっています。

[@ああ-r9e1d]

@@1つ星日本語でお書きください。

[@なすなすび-k3i]

「絶対」は「絶対」存在しない、みたいな

[@閬闅闋闑闣闤闥闦闧閷]

[あなたはこの質問にいいえと答えますか?]
▷はい
▷いいえ

[@吉吉良良]

自分が持ち上げることのできない石を作ることができるか？
作れる→石を持ち上げられないため全能ではない
作れない→石を作れないため全能ではない

[@三法印静]

人間ならチマチマ枠を組んで１トンのコンクリ塊作れば良いんだから別に作れるよな……

[@kgames8633]

「この文は嘘である。」に似たものを感じますね。

[@MillayNagatsuki]

しかし数学者はそれだけでは飽き足らず、停止問題を瞬時に正しく解答できる「神託機械」が存在する世界について考え始めた。

[@るり-f9q2y]

これ、入力を自身を参照しないものに限ればできるんかな？

[@NumAniCloud]

たしかに。ゲーデル文とかクラスとかの話に発展していくのかな？

[@mashimo486]

掛け算とループ文が有るとだいたい無理。自身を参照するのを禁止したところで、プログラムの能力が激減するわけじゃないから等価な無限ループは作れる

[@若ノ崎]

終了する、終了しない、決定不能の3値で判断する場合はコンピュータでも無矛盾で解けるのかな？

[@けしごむ-k2z]

すべて「決定不能」(終了するかもしれないし、しないかもしれない) と出力すればその要件は満たせるかと思います。
ただ、「決定不能」以外の判断を正しく返す**精度を高める** 試みは既に例があって、静的解析ツールやコンパイラの無限ループ検出などが該当するでしょうか。

[@rk2179]

んにゃぴ……よくわかんない

[@KawaiiNegi-]

不完全性定理ってやつですか？

[@evimalab]

ゲーデルの不完全性定理はまた別の話ですが、停止性問題が決定不能であることを利用して第一不完全性定理を示すことができるようです。

[@うにかも]

自分自身以外に対し全知全能にはなれちゃうよね。。。

[@Coda-2]

ほえー自己言及を使って必ず矛盾する状況が作れるのか
自己言及じゃないからいい喩えかわかんないけど無理数^無理数が有理数になる場合がある証明を思い出した

[@guraion_NO.1]

よくわからんかった。有限•無限の判定を正しく行うことができるプログラム「ホールト」を作れると仮定する。しかし、人間があえて間違わせるような意地悪なコードpだと、ホールトは正しく判定できない。よって仮定がおかしく、正しいホールトは実現できないてこと？
現実的にはホールトに渡す前に、aiに中身見てもらい、意地悪なコードかどうか聞くのがいい？

[@evimalab]

はい。「この機械は『何を入力しても』正しく判定できる」と言うととんでもないものを入力されてしまうという話です。

[@づとりん]

chatgpt最初に触った時にみんなクレタ人のパラドックス試したよね

[@rubi_Agent4]

クレタ人｢クレタ人は嘘つき!｣

[@Satou_Takashi]

我々がAIに求めているのは100%の全知全能ではなく、全知全能に近い存在なので。多少の間違いや結果のバラつきはむしろ人間らしさとして捉えられる。

[@タマナカとキュー]

コンピューターが賢くなると、性能の低い旧世代機に対する愛着や生存権とかを考えるようになるため、
シンギュラリティの先にはちょっとした停滞が待っているのかも・・・しれないね

[@tf2anticringe]

古い世代に愛着を感じてシンギュラリティが渋滞するようなAIは賢くないやろ

[@Ghhgggggg]

性能が高い＝執着を持つ、だと思う理由はなぜ？
答えを導き出すプログラムにアイデンティティはいらないぞ

[@aket2989]

@@Ghhgggggg賢さ=我々のように感情を抱くことと思う人間の驕り

[@1つ星]

出たな形式化の極義『対角線論法』！！
(P≠NPもこれで解けたらねどれだけ楽だったか...)

[@Zab_n]

排中律を捨てなさい

[@TNTSuperMan]

よく考えたら実行ファイルを'p'と仮定すと、
pがpを実行
pに実行されたpがpを実行
pに実行されたpに実行されたpがpを実行...って無限ループするのが自分の予想です。

[@娯楽屋]

コンピュータだけじゃなくて、人間含めたどんな知能を持つ存在にも永久に出来ないですねこれ...
神がもし存在したとしても不可能ですね。論理的に不可能な事は神にも不可能なので。

[@romuser6248]

論理的に不可能なことは神にも不可能っていうのは詭弁ですよ
有名な話ですが、全知全能の神は絶対に持ち上げられない石を作れるか？という問いで「その石を持ち上げられないなら神は全能ではないし、持ち上げられたらそれは持ち上げられない石ではない」を根拠に神を否定する論理がありますが、これは「神は石を持ち上げられないし、持ち上げられる」という状態はあり得ないということを前提としています。しかし実際にそれが確実にありえない保障なんてどこにもありません。人類の誰も「神は石を持ち上げられないし、持ち上げられる」ということは否定できません。なのでこれは神の存在は否定できていないです。
こんな感じで、そもそも論理っていうのは実は根底には感覚があるのですから、論理的に不可能という主張も遡ると、感覚的に不可能に思えるという段階に前で還元できます。

[@娯楽屋]

@@romuser6248
勘違いされているようですが私は神の存在はそもそも否定していません。
存在していようがいまいが不可能という話をしただけです。
それと全能者のパラドックスは別に神を否定してるわけではなく、「全能者」の存在を否定してるだけです。
論理と感覚は別物です。論理的に可能かどうかと、感覚的に可能に思えるかどうかは別の話です。
そこを混同していると、どんな盾でも斬れる剣とどんな剣でも斬れない盾を売ろうとする商人に騙されますよ。
まあ論理を理解出来る人もいれば理解出来ない人もいます。
数学の証明を理解出来る人もいれば理解出来ない人もいるのと同じですね。
論理を理解出来ない人が存在する事は論理的に矛盾しないので。
あなたが論理を理解し、他人が騙る詭弁や矛盾に騙されないことを祈りましょう。

[@muwi-p4w]

​@@娯楽屋
盾は剣で斬るものではありません。矛で突くものです。

[@romuser6248]

@@娯楽屋 あなたこそ勘違いしておられるようですが私はあなたが神の存在を否定しているとは一言も言っていません。『有名な話ですが』と例を挙げただけです
『論理と感覚が別物』とおっしゃいましたが、なぜそう考えるのでしょうか？
あなたは僕の主張への反論の根拠に論理と感覚が別という主張を用いましたが、そもそも僕はその主張の真偽を最初のコメントの中で疑っているのであって、それを反論の根拠に使うのは詭弁です。
果たして'論理'を理解していないのはどちらでしょうか？
あなたが例挙と断定の違いが判別できるようになること、そして論理を理解し、自らが詭弁を語り人を騙そうとすることがなくなるように祈ります。

[@romuser6248]

@@娯楽屋 ちなみにですが、数学の証明を理解できる人もいればできない人もいるように、僕の書いた簡潔な文章で理解できる人もいれば、解説が足りず理解できないあなたのような人もいるので、僕がなぜ論理は感覚であると考えているかを詳説しておきます。
ソクラテスは人間である。
全ての人間は必ず死ぬ。
よってソクラテスは死ぬ。　
これは有名な三段論法です。しかし僕はこれを正しいとは思いません。正確には正しいかどうかを判別できないと考えています。
なぜなら3行目の「よって」を説明できていないからです。なぜ上二つが成り立つなら３つ目が成り立つと言えるのでしょうか？あなたはこれを説明できますか？おそらくこれは全ての人間が説明することはできません。なぜならこの論理の正しさは感覚によって裏付けされているからです。
「我思う故に我あり」これはデカルトが哲学を数学のように確実に正しい事実を一つ求め、そこから確実に正しい論理を積み重ねれば真理を明らかにできるという思想のもとで発見された命題です。これは哲学の第一原理とも呼ばれ、論理のプロであり哲学者に広く受け入れられました。これが哲学者の中で、どのような評価を得た上で受け入れられたかご存知でしょうか？色々ありますが、最も主な評価は「確かに、これには反論できる点が"見当たらない"」です。分かりますか？「見つけることができない」ことをこの命題の正しさの根拠にしているんです。あの哲学者達がですよ？誰一人、「我思う故に我あり」という命題の論理的正しさそのものを直接証明していないんです。この事実からも、論理を理解している人々の間ではすでに「論理を感覚抜きで確立する」ことは不可能だとするのが妥当だとされてきたことは明らかでしょう？
それとも論理と感覚を別にできる(笑)あなたは、この命題を証明できますか？
あるいはソクラテスの三段論法を証明できますか？　僕はあなたのように論理と感覚を別にできないので、感覚に基づかない証明ができるのならぜひ見せてください。見せてくれたら負けを認めますよ。

[@ringo2872]

ラッセルのパラドックスだっけ？

[@こけひろみち2]

おじいさんとおばあさんがおせっせとお洗濯を？！

[@study_math]

天使と悪魔

[@Yurufuwa8192]

ラッセルのパラドックスみたいや

[@Zejgar]

Self-referential paradoxes daisuki

[@パリーンパリ]

入力が無いプログラムは「開始しない」ので「ループ」も「停止」もしないのでは？
p()にp()を入れたらp(p())になるけど一番内側のp()は何を判定してるの？
空箱に空箱を入れても中身がないよ

[@ybk1940]

最初のcount.exeを考えてみれば分かると思うけど、count.exeの入力にcount.exeを入れればcount.exeが何バイトか判定してくれるので、入力のプログラムに入力がないことは特に問題になりません

[@フラウンスに狂う]

外側のpに渡された内側のpは関数の名前渡しではなく、ただの「プログラムとして実行できる文字列」です。内側のpは外側のpに入力された後、1行目のhalt(input,input)に渡され、この中でhalt関数にp(p())(つまり"このプログラムと入力の組"自身)が停止するかどうかをエミュレートされる、という形で実行されています。

[@zouo-from-Taikonotatsujin]

人は低脳を完全下位互換と無視をせず笑うんだぞ(代表例:ネットミーム)
必ず解答の逆を正解としてくるなら無理ゲーよ

[@dxg4204]

自己言及のパラドックスってやつか

[@twentyyears5407]

停止問題おもしろいね

[@Cat-pv1zz]

いや、ChatGPTにソースコードとデータを食わせて「無限ループしますか？」って聞けばいいじゃん

[@自由律俳句とかいう無法地]

ただの自己言及のパラドックスじゃん。
そういう話が聞きたいんじゃないんだけどなぁ。

[@GamerOfAll9thGenConsoles]

俺にとってはこの手の話は屁理屈にしか思えないな…
0.9999999………が1になるのを計算で示された時みたいな。

[@evimalab]

（別の話になりますが）0.9999999………は厳密に1に等しいです。