チューリングマシンは無限の長さのテープがあることが必要だが、
現実の計算機は無限の長さのテープや無限の容量の記憶を持たないので、
チューリングマシンには可能であっても現実の計算機にはできないことは
いくらでもある。
所詮、記憶容量が有限のマシンは、数学的には有限オートマトン
（有限状態遷移マシン）に過ぎないのだ。単に状態の数が（とても）多いだけだ。