質問など遠慮なくどうぞ→kawamura@kurims.kyoto-u.ac.jp
我々は数学的問題を解くために頭の中で（あるいは紙やコンピュータを使って）計算を行うわけですが、この計算（情報処理）という行為そのものを数学的対象として考察し、計算によって何ができて何ができないか明らかにしようとするのが計算可能性と計算量の理論です。1930年代に生まれた計算理論は、コンピュータの誕生や普及とも互いに影響を与え合いながら発展して来ましたが、素朴な未解決問題も数多く残されています。本講義では、「計算する機械（や人）」をどのように理論的に捉え、その能力や限界をどのように測るのか、例とともに紹介します。