B01

数理・論理・量子情報/考え方をかんがえる

Computation, Logic, Quantum information

理論計算機科学入門

Introduction to Theoretical Computer Science

理論計算機科学入門: 有限と無限のあいだ ~ オートマトン理論を例に

Introduction to Theoretical Computer Science: Interplay between Finite and Infinite

代表者名

システム設計数理国際研究センター

Global Research Center for Systems Design and Mathematics

共同発表者名

所属分野

研究センター

Research Center

pdf-image

要旨

計算機やプログラムの振る舞いについて、数学を使って研究するのが理論計算機科学という分野です。応用数学の一分野として見た場合、その大きな特徴は「有限と無限のせめぎあい」です。計算機やプログラムといった「機械」や「レシピ」は無限に豊かな振る舞いを持つ一方で、これらを実際に作ったり記述するためには、そのサイズは有限でなければなりません。この「有限と無限のせめぎあい」という一大テーマについて、オートマトン理論を通してお話しします。

One big theme in an academic field called theoretical computer science is the interplay beteen finite and infinite. This theme is discussed in an elementary and accessibility manner, using the language inclusion problem in automata theory as a concrete example.

関連動画