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