チューリング・マシン(TM) の凄い所

TM は有限機械
状態が有限/テープ記号も有限/動作(ヘッドの移動)も有限
無限なのはテープの長さだけ
TM は万能
「原理的に」計算可能な物は、TM で計算できる
もちろん、コーディングは使う