演算処理の原理

演算処理の原理 (Text p.51, 4.1 節)
チューリングマシン (TM) : CPU の動作原理の数学的なモデル
テープ : 左右に無限続く、書き換え可能なマスの並び (メモリ)
有限制御部(オートマトン) : マスを指すヘッドをもち、現在の状態とマスの記号から次の動作(状態変化、ヘッドの移動、マスの書き換え)を決める (CPU)
テープの内容や、動作規則によって TM の振舞い(機能:何を計算するか)が決る
TM による計算可能性
計算可能なもの(とおぼしきもの..)には、それを実際に計算する TM が存在する
万能 TM
ある TM' (万能 TM) が存在し、任意の TM に対して、テープの工夫だけで、それと同じ機能を持つ
(証明の概要) 元の TM の機能を TM' のテープ上に実現 (プログラム) / 計算対象(データ)もテープ上にある
ノイマン型と TM
TM の事をノイマンが知っていて、コンピュータの設計に利用した
TM の限界 : フォン・ノイマンボトルネック 
ヘッドが一つ (逐次処理をしている) [cf. 人間の脳は並列処理]