コンピュータはどんな問題も解けるのか？

「答え」があっても解けない問題

私たちはコンピュータに「答えの計算」と要求します。例えば、「バイトのシフトを組め」「迷惑メールを振り分けろ」といった要求です。では、コンピュータは答えがある問題ならばなんでも解けるのでしょうか？
答えは「否」です。例えば、「与えられた方程式が整数解を持つかどうか」という問題は、いかにも計算機でたちどころに答えが出せそうな問題ですが、実は完璧にこの問題を解くプログラムが存在しないことが証明されています。計算可能性・複雑性の理論は「コンピュータにとって難しい問題とはなにか？」を探求する学問分野です。

計算モデルと計算の効率性

問題の難しさについて考えていくと、コンピュータが解くことができる問題に対して、「どのような問題には、どの程度の計算機パワーや計算時間が必要か」という問いが自然に生まれます。また、ひと口にコンピュータと言っても、さまざまな計算モデルがあります。例えば、1台のコンピュータで解く場合と複数台で並列協調的に解く場合では、計算モデルは異なります。データの持ち方が異なりますし、後者の場合には計算を振り分ける必要があるからです。どの計算モデルはどういう問題が得意なのかを明らかにする、また、さまざまな計算モデルに対して、それに適した求解方法（アルゴリズム）を作成する、といった研究が進められています。

「計算」を理解するための理論計算機科学

ここまでの話はすべて、広い意味では理論計算機科学と呼ばれる学問分野に含まれます。理論計算機科学は「数理的なモデル」を考えて、その上の計算技法を考えたり、モデルの能力の限界を数学的に明らかにする分野です。現実のシステムの性能向上や安全性、信頼性を支える縁の下の理論として、情報科学にとどまらない、広範な応用分野と関わりがあります。

※夢ナビ講義は各講師の見解にもとづく講義内容としてご理解ください。

※夢ナビ講義の内容に関するお問い合わせには対応しておりません。

先生情報 / 大学情報

大阪大学大学院情報科学研究科コンピュータサイエンス専攻准教授泉泰介先生

興味が湧いてきたら、この学問がオススメ！

アルゴリズム理論、離散数学、グラフ理論

先生が目指すSDGs

メッセージ

流行している分野は魅力的に見えますが、華やかな成果の裏には地味な作業の積み重ねがあります。そういう地味な作業が続いても、流行が下火になったとしても、その分野を学ぶことに幸せを感じるかどうかもよく考えてみましょう。社会も同様で、地味で誰も見向きもしないような仕事がとても重要なことも多々あります。一見面白くなさそうなものも、わかってくれば面白くなりますし、さまざまなことから面白さを見いだす努力も大切です。広い視点を持って、複雑な現代をしなやかに生きていってほしいと思います。

大阪大学に関心を持ったあなたは

自由な学風と進取の精神が伝統である大阪大学は、学術研究でも生命科学をはじめ各分野で多くの研究者が世界を舞台に活躍、阪大の名を高めています。その理由は、モットーである「地域に生き世界に伸びる」を忠実に実践してきたからです。阪大の特色は、この理念に全てが集約されています。また、大阪大学は、常に発展し続ける大学です。新たな試みに果敢に挑戦し、異質なものを迎え入れ、脱皮を繰り返すみずみずしい息吹がキャンパスに満ち溢れています。