例題:チューリングマシンシミュレータ

チューリングマシンは現在のデジタルコンピュータの数学的モデルである.チューリングマシンは論理的に定義されているので,その動きを頭の中で追ったり,紙の上に書き出したりすることは可能であるが,通常「計算」に要するステップ数は多く,追跡はなかなか骨の折れる仕事である.プログラミング言語を使ってシミュレータを書くというのは,通常の発想であるが,そのデザインには時間がかかる.Lispはプロトタイピングに適しており,時間をかけずに論理を追跡するのに適している.
(1) チューリングマシンとは
(2) チューリングマシンシミュレータの設計
(3) ソースコード例
(4) 実行例