チューリングマシンとかチューリング完全という言葉を一度は聞いたことがあると思います。
基本情報技術者試験のハードウェアでも二進法の計算等で出題されます。
浮動小数点数に関する表現等でもこのチューリングマシンの計算可能性が前提となっています。
アラン・チューリングという科学者の名前から取っているのですが、
コンピュータの基本構造と言ってもなんだかイメージがしにくいものでもあります。
計算を行う自動機械の数学的なモデル。形式的な記号操作の組み合わせ、
繰り返しで構成されるすべての計算を実行することができる、
最も単純化されたコンピュータのモデルとして知られる。
e-word.jp
チューリングマシンの特徴は極めて単純です。
$$qSS’q’$$
この式が表す意味は「qという内部状態において、外部の特定変数を観察して、それがSならば、
外部にS’という働きかけを行い、内部状態をq’に変化させる」ということです。
このときqとSの組み合わせに対してことなるS’とq’はあってはなりません。
例えば「1という状態において+1という働きかけを行い内部状態を2に変化させる」みたいなことです。
このとき何度繰り返しても+1をしたらいくつ変化するかは同にならなくてはなりません。
そして、内部状態が観察する変数を選んでいるということも特徴です。
あくまでヘッドのある場所に書き込まれている0か1という記号を見て判断します。
計算機械としてはS’という働きかけはヘッドを左右に動かして、
指定された記号、0又は1を書き込むことで行います。
qは次々に変化していくので、チューリングマシンはこの記号をテープを用いて、
新しい課題をどんどんと達成していくことになります。
動作の規則が適切に定められることによって一見複雑な計算を実行させることができます。
ちょっと難しいかもしれませんが非常に詳細に解説しているものを見つけました。
基本情報技術者試験には不要な知識ですが関心がある方は読み込んでみると楽しいかもしれません。
改めてこちらの教科書を読んでみると曖昧な理解なところが多くて、
今回の記事ももっとわかりやすく説明できるように更新したいので（作成中）とさせて頂きました。
電子情報通信学会「知識ベース」4章チューリング機械
http://www.ieice-hbkb.org/files/06/06gun_02hen_04.pdf