10 - 一般名無し質問者 2022/02/06(日) 03:28:20 ID:b2+J0ksG0
計算可能性の話をしたら次は計算量理論がいいかな。みなさんよろしくお
で計算可能でない関数を紹介しましたが、証明で現れた具体的構成がそうであるように計算可能でない関数は結構変なものばっかりで、当職や貴職らが普段想定するような関数はだいたい計算可能です。
では計算可能関数であればなんでもコンピュータで解決できるのかというと、そうではありません。人間の寿命が有限だからです。コンピュータの計算には必ず時間を使いますので、計算可能であっても膨大な時間がかかるならそれは問題が解決不可能であるのと同じことです。
つまり、具体的にある問題をコンピュータで解こうとしたときにどれくらい時間がかかるかを知るのは非常に重要な問題のわけです。実際に動かしてみるのが一番確実ですが、動かしている間に人生が終わってしまってはそれこそ意味がありません。
ここでプログラムとその入力を見て計算時間の予想を立てる動機が生まれ、計算量理論はこの問題を解決するために発展しました。
多くのプログラムの実行時間は入力の大きさが重要な決定要因であるという経験則があり、計算量理論でもあるプログラムと入力に対してかかる時間をその入力の長さの関数で表現することが多いです。
抽象的な物言いになってしまったので具体的な例を出しましょう。
今、コンピュータとして1桁の足し算と掛け算をわかっている子共を想定します。これも椿森日東師のいうところの立派な計算模型です。計算量理論においては想定する計算モデルを固定するのが一般的です（暗黙のうちに現代のCPUのようなものを仮定することも多いです）。
この子共がn桁の整数同士の掛け算を筆算するとき、何回の掛け算をする必要があるでしょうか？ お互いの整数の各桁を掛け算する必要があるのでn^2回ですね。
ということは計算時間もおおよそnの2乗に比例しそうなので、たとえば5桁の筆算にこの子共が1分かかったとすると、4倍の20桁のときにはその16倍の16分くらい掛かりそうだということが予想できるわけです。
ランダウの記号とか P vs. NP とか計算量的安全性の話をしたかったけど長くなったので一旦ここまで。