ito/TuringMachine - PukiWiki

Turing Machine のページ

Turing Machine の簡易シミュレータ

対応している環境

  • Windows XP + Mingw
  • Windows XP + Cygwin
  • Linux

ただし、ソースファイルの依存関係 (どのファイルがどのファイルをインクルードしているか等) を自動的に解決するために用意された、make depend を実行する場合は、 sed が必要。(CygwinとほとんどのLinuxには標準装備?)

ダウンロードと使い方

ダウンロードはこちら fileTuring.zip &ref(Turing.tar.gz)

環境等にあわせて、zip または、tar.gz の好きな方をダウンロードします。

ダウンロードしたzip/tar.gzファイルを展開して、コンパイルします。

ビルドの方法

  • Mingw の場合 make BUILD_ENV=Mingw
  • Cygwin の場合 make BUILD_ENV=Cygwin
  • Linux の場合 make または、 make BUILD_ENV=Linux

デバッグ情報を含めず、バイナリのサイズを小さくするには、 TARGET_VERSION=Release を指定する。 例:

  • make BUILD_ENV=Mingw TARGET_VERSION=Release
  • make BUILD_ENV=Cygwin TARGET_VERSION=Release
  • make TARGET_VERSION=Release

使い方

Turing Machine の定義を書いたファイルを用意する。 ファイルのサンプルはこちら filein1.txt

  • 各行の内容は、次のようにする。
  • 1行目は、アルファベットの集合(テープに使う文字のセット)。 各文字を | で区切る。先頭の二つは、必ず #,B
  • 2行目は、状態集合(の表示に使う文字列のセット) 各要素を | で区切る。
  • 3行目は、初期状態,終了状態 (カンマ区切り)
  • 4行目から、繊維規則。 読み込み時の状態,読み込んだ文字,遷移後の状態,書き込む文字,ヘッドの移動方向 (カンマ区切り)
  • たとえば、 q0,B,q1,1,middleは、状態 q0のときにBを読み込むと 状態をq1に変え、テープに1を書き込み、ヘッドの位置は移動しない。
  • 移動方向は、left,right,middle または、l,r,m 大文字でも大丈夫かもしれない。 これ以外の文字列を指定すると、middle として扱うはずである。
  • すべての規則を列挙したら、次に.(ピリオド)だけの行をおく。
  • その次に、テープの初期値を | で区切って指定する。
  • その次の行に、ヘッドの初期位置を整数で指定する。 テープの左端が0.
  • 最後にステップ数を指定する。 ステップがこの数を超えるか、終了状態になるまで繰り返す。

実行

環境にあった実行ファイルに、入力ファイルと出力ファイルの名前を引数に渡す

  • bin/turing_cygwin_release.exe in1.txt out1.txt

出力ファイルを省略すると、標準出力に(色つきで)表示する。 入力ファイルも省略すると、最初に入力ファイルの名前を聞かれる。

標準出力への表示は、色つき(エスケープシーケンス使用)なので、 この結果をファイルにリダイレクトすると、大抵表示が乱れる。 ファイルへの書き込みは、リダイレクトを使うより、 ファイル名を引数に指定するほうがよい。

おまけ: Windowsで、Visual Studio 6.0 および Visual Studio .NET でも動くかもしれない。

\#comment

g(2), g(3) の計算

Links

論理と計算

ito


添付ファイル: fileTuring.tar.gz 412件 [詳細] fileTuring.zip 543件 [詳細] filein1.txt 667件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSSPDF
Last-modified: 2008-10-31 (金) 14:33:58 (3251d)