コンピュータの限界を知る：第2回 チューリング·マシンとBrainf~* ck

摘要

コンピュータは，元を正せば計算を行うために発明された機械で，いわば電卓やそろばんの親戚です．ですが，コンピュータは計算をするという範囲を大きく超えて活用されています．ゲーム機や携帯電話といった，計算とは直接の関係がなさそうなものにも入っています．あらためて考えてみると，不思議な話です．コンピュータが使われるようになった1930年代に，コンピュータができることの限界を探る研究が始まりました．、その研究で重要な役割を果たした道具が，チューリング·マシン（図1）です．