チューリングマシン: しくみの模型

計算を、5つの小さな動作に分ける

チューリングマシンは、テープ・ヘッド・状態・ルール表の4つだけで「計算とは何か」を表した、考えるための機械です。コンピューターの部品を再現するのではなく、1つの命令が「読む → ルールを選ぶ → 書く → 動く → 状態を切り替える」の順に進むようすを、1手ずつ追えるようにしています。まずは、テープ・ヘッド・状態・ルール表の表示が、同じ瞬間を指していることを確かめましょう。

チューリングマシンの基本的なつくりは、Stanford Encyclopedia of Philosophy: Turing Machines でも、テープ・ヘッド・状態・命令表の関係として説明されています。