茜ちゃんのひとくち数学

[@Adimash05]

ここで紹介されてるビジービーバー関数はすべての計算可能な関数を支配する(如何なる計算可能な関数より急激に解の値が増大する)強さがあるけど、それでも計算不可能関数の中ではほぼ最弱クラスなんよね……

[@すーぱーぜっと]

プログラムの中には「計算が終わって答えを出力するもの」と「計算する中でループしちゃったりして永遠に答えが出力されないもの」の2つがあるんですよね。プログラムがこの2つのうちのどっちなのかを調べるために「このプログラムは計算が終わって答えを出力しますか？はい/いいえ」というプログラムを考えたくなるんですが、これは後者だった場合に「まだ計算が終わってないだけかもしれない...」ってずっと待っちゃって永遠に答えをくれないんですよね。なので、動画で紹介されてるビジービーバー関数みたいな「プログラムの計算がちゃんと終わるかどうかが分からないと答えを出力できない関数」は永遠に答えをくれなくて、計算不可能になるんですよね(間違ってたらごめんなさい)。

[@ringo2872]

そう考えたらコラッツ予想の関数も計算不可能関数の可能性があるってことか

[@BigEDOLine]

ワイならつよつよのPCいらんで！(ラマヌジャン並感)

[@hachi8833]

質問「加法性を持たない概念って数学にありますか？」

[@AC-cs2sx]

自然数から自然数への関数のうち、計算可能関数を集めた集合の濃度と、計算不可能関数を集めた集合の濃度は、どっちが大きいのかな。
（どっちも連続体濃度だったり？）
　超越数の方が代数的数よりも多いのに、まだe,πしか人類は知らない（証明されてない）ってのを思い出して。
　案外、数学ってそういうのが多かったりするのかなと思いました。
（境界線の引き方次第か？）

[@ucejvfakrcjuwqbnhl_nlacq6476]

良い着眼点ですね！
計算可能関数って、要するに有限文字からなるプログラムで書けるということですよね。プログラムが '0' と '1' の2種の文字列から出来ることを考えると計算可能関数は自然数と対応することがわかり、計算可能関数の濃度は可算であることが分かります。計算不可能関数の集合は計算可能関数集合の補集合なので連続体濃度であることが分かります。

[@channel-1224]

@@ucejvfakrcjuwqbnhl_nlacq6476 横から返信失礼します。　例えば、1を足すという自然数上の関数を考えます。 これは明らかに計算可能関数です。
ですが、その始域を任意に取ることが出来ます。　その始域が無限だろうと有限だろうと自然数を返せるからです。
この場合、おそらく計算可能関数全体の集合は非加算濃度になると思われます。 なぜなら、その始域は自然数の任意の部分集合であって、
つまりそれ全体の集合は自然数全体の冪集合と同一視できるからです。
非常に面白く整理された動画だと思います。　つい話してしまいましたが、これからも応援しています!

[@VOICEROID-vd4cz]

@@channel-1224
始域を変更すれば非可算個の関数が作れるんですね…
とすると計算可能関数は非可算個あるのでしょうか？それともチューリングマシンで指定できる始域集合は可算個なのでしょうか？

[@channel-1224]

@@VOICEROID-vd4cz
少なくとも計算可能関数は非加算個(だそう)です。　
チューリングマシンで指定できる始域集合ってのはよくわかりませんが、制限のないチューリングマシンの個数は定義を見る限り非加算個だと思われます。

[@VOICEROID-vd4cz]

@@channel-1224
任意の自然数m,nに対してm記号n状態チューリングマシンの遷移関数は有限個なので、チューリングマシンの種類(遷移関数の種類)は可算だと思ってました。
なんで非可算なんだろう……

[@frametyrant]

アカネチャン賢い可愛いヤッター！