サブルーチン機能を持つチューリング機械シミュレータの設計

概要

論文の詳細を見る
チューリング機械はその構造の単純さにも関わらず、最も汎用的な能力を持つ数学的な計算機モデルである。一般に、計算可能性を定義する道具としてチューリング機械が用いられているが、有効な手順という直観的な概念やアルゴリズムの後半部を幻覚の論じる為の形式的モデルとしても重要な存在である.従来よりチューリング機械の動作についての理解を助けるために、電子計算機上でシミュレーションを行なう試みがあった.更に,unix上のグラフィカルインターフェイスとして広く普及,発達してきたX-windowを用いて視覚化することで効率的な学習を可能としたシミュレータも作成されている.しかし、実際にシミュレーションを行なおうとすると、簡単な関数ですら状態遷移図が複雑となり,視覚的にシミュレート出来る範囲を越えてしまうという問題があった.現在,この視覚的なシミュレータに対して,モジュール設定の為の拡張を施すことにより,規模の大きな状態遷移図を扱え,同時にサブルーチン呼び出しも利用できるシュミレータの設計,改良を行なっているので紹介する.
社団法人電子情報通信学会の論文
1995-03-27