[HOME]

Turing Machine Simulator -ver1.0



はじめに

このプログラムは、机上で設計したチューリングマシンが自分が考えたように 正確に動作するか検査するものです。 ようするにチューリングマシンシュミレータです。


ダウンロード

version1.2 (9kb 05/30/03)
version1.1 (9kb 09/15/02)
version1.0 (9kb 09/03/02)


特徴

このシミュレータはRichard P. Feynmanの、Feynman Lectures on Computation上 で述べられているチューリングマシンを実装しています。
以下に簡単に特徴を上げます。

CUI

基本的には結果しか出力されませんので、シミュレータ動作時のヘッドやテープ の状態を調べるのが困難です。しかし、list2turというプログラムを使用すれば、 このチューリングシュミレータのチューリングマシンプログラムを"gTuring" のものに変換できますので、gTuringがインストールされていればGUIで動作を確認 することが可能です。list2turはこのパッケージに含まれています。

無制限のテープ

無限のテープではありません。無制限のテープです。これは、テープが必要ならば いくらでも新しいテープを使えるということを意味します。もちろん、実際は メモリー量の制限を受けます。しかし、現在のコンピュータが搭載している メモリー量ならば無制限と考えても問題はないと思います。


動作環境

GCCがある環境なら大抵は大丈夫だと思います。
私が確認した環境は以下の二つです。

  VineLinux2.5(x86)
  gcc 2.95.3

  WindowsXP
  Cygwin
  gcc 2.95.3-5
*日本語文字コードがEUC-JPなのでWinXP+Cygwin環境では上手く表示されません。


インストール

ダウンロードしたファイルを解凍します。
Unixなら
tar -zxvf turing.tar.gz
でOKでしょう。 解凍すると、turingというフォルダが出来ますので、そのフォルダの中でコンパイルします。
いちおうMakefileを書きましたので、makeがあるならば

make
su (必要ならば)
make install

で平気なはずです。
install先のデフォルトは/usr/local/binです。

makeが無くても

gcc -o turing main.c gettape.c list.c
gcc -o list2tur list2tur.c gettape.c list.c tur.c

でコンパイルできると思います。
要約すると

	tar -zxvf turing.tar.gz
	cd turing
	make
	su (必要ならば
	make install
です。


簡単な使い方

基本はコマンドライン上で

turing [オプション] リストファイル テープファイル

と入力することです。結果は標準出力--通常は画面--に出力されます。 通常、出力される結果は、チューリングマシンが停止した後のテープだけですが、 -pオプションを使うと、開始から停止までの全てのステップにおける チューリングマシンの状態(State)、テープ、ステップ数が出力されます。
リストファイルとはチューリングマシンプログラムのことです。ファインマンの本 ではチューリングの五つ組と呼ばれているものです。 リストファイルについては後で説明します。
テープファイルはチューリングマシンに読ませるテープです。-tオプションを 用いれば標準入力--通常はキーボード--からテープを読みこみます。 テープファイルの詳細は後の項目に書いてあります。


オプション

オプションは必ずコマンド名(turing)の次に入力して下さい。

e.g) ◯ turing -t parity.list
× turing parity.list -t

-h -? --help	ヘルプです。使い方、オプションを表示します。

-v --version	バージョンを表示します。

-b		ブランクをスペースではなくアンダーバーで出力します。

-n N		チューリングマシンのヘッドの開始位置をNに指定します。
		通常はゼロです。

-p		ステップ数、状態(State)、テープを全ステップにおいて出力します。
		e.g)
		bash$ turing -p parity.list parity.tape
		   0( 0): 1010E
		   1( 1): 0010E
		   2( 1): 0010E
		   3( 0): 0000E
		   4( 0): 0000E
		   5( H): 00000

-t		テープをファイルからでなく標準入力--普通はキーボード--から入力
		します。改行(\n)、またはEOFで入力終了です。
		入力されたテープは/tmp/turing.tmpに保存されます。


リストファイル

チューリングマシンプログラム、またはチューリングの五つ組と呼ばれるものです。 このシミュレータはミンスキー及びファインマンの本に書かれている チューリングマシンをシミュレートするものなので、それらの本に掲載されている プログラムなら大した変更無く実行できると思います。

e.g)

# 開きカッコ、閉カッコが正しく対応しているか調べる
#? 0
0 ( ( 0 R
0 ) X 1 R
0 E E 2 R
0 X X 0 R
1 ( X 0 L
1 ) ) 1 L
1 E 0 H L
1 X X 1 L
2 ( 0 H L
2 ) ) H L
2 E 1 H L
2 X X 2 L

説明
#から改行まではコメントです。
#? N(数字) で、最初の状態をNにセットします。なければ最初の状態はゼロです。
「0 ( ( 0 R」がチューリングの五つ組です。
左から、現在の状態、入力、出力、次の状態、移動方向、を表しています。
*RはRight(右)、LはLeft(左)、HはHalt(停止)

チューリングマシンの状態は次のように変化します。ヘッドがあるところの セル(テープの構成要素)に書いてある値を読みこみます。現在の状態、 読みこんだ値に応じて出力が決まるので、その値をセルに書き込みます。 そしたら、次の状態に変化して、ヘッドを移動させます。ここで、注意すべきことは、 移動する向きは変化後の状態によって決まるということです。ということは、 状態と移動方向は一対一対応となります(上の例を参照)。これが、 このチューリングマシンの特徴で、他のチューリングマシンとの最大の違い だと思います。また、このマシンの利点は状態遷移図が書きやすいということです。 以下に、上のと同じ動作をする、普通のチューリングマシンの五つ組を掲げます (左から、状態、入力、出力、移動方向、次の状態)。

e.g)

0 ( ( R 0
0 ) X L 1
0 E E L 2
0 X X R 0
1 ( X R 0
1 ) ) L 1
1 E 0 R H
1 X X L 1
2 ( 0 R H
2 ) ) R H
2 E 1 R H
2 X X L 2

状態

状態は負でない整数を用いて表します。 最大の数はINT_MAXです(大抵は+32767〜+2147483647)。つまり、状態Nの範囲は

0 ≦ N ≦ INT_MAX

です。
HALT(停止状態)は"H"、または"h"で表します。

入力、出力

入力と出力は印字できるASCIIキャラクタで表します(一文字)。具体的には

!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKELMNOPQRSTUVWXYZ
[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
の94文字です。アンダーバー(_)はブランク(スペース)として扱われます。

移動方向

右への移動は"r"、または"R"
左への移動は"l", または"L"で表します。

その他

五つ組のそれぞれの値は必ずスペースで区切ってください。


テープファイル

チューリングマシンに読みこませるテープを記述したファイルです。
使える文字は入力、出力と同じです。
ブランクはアンダーバーで表します。
空白文字は無視されます。
新しいテープのセルは全てブランクです(アンダーバー)。

-tオプションを使えばテープファイルは必要ありません。


list2tur

このプログラムは、チューリングの五つ組をgTuringで実行できる五つ組に変換する ツールです。これによって、動作中の状態を調べるのが楽になると思います。 まず、使い方とオプションを簡単に説明します。

  list2tur [options] リストファイル

-h -? --help		使い方とオプションを表示します。

-v --version		バージョンを表示します。

gTuringは必ず右端がスタート位置のため、そのままではうまくgTuringの五つ組に 変換できない場合があります。たとえば、上で掲げたリストファイルを変換したもの をgTuringで実行しても、違う結果がでます。完ぺきな変換をするためには

#? 3
3 E E 0 R #移動方向はどちらでもよい

をリストファイルに追加します。

list2turの結果は標準出力に出力されますので、シェルのリダイレクション機能 などを使って結果をファイルに保存して下さい。

e.g)>
  bash$ list2tur parity.list > parity.tur


バグ

しっかりしたテストをしてないので、かなりのバグがあると思います。

再配布規定

このプログラムに関してはフリーソフトウェアとします。 配布・改変は自由にどうぞ。


参考文献

Feynman, Richard ファインマン計算機科学
Feynman Lectures on Computationを日本語に翻訳したものです。
編者と訳者の名前は忘れてしまいました。ごめんなさい。

Minsky, Marvin Finite and Infinite Machine
書名は適当です。たぶん、合ってるとは思います。ネットで調べたかぎりでは この本は翻訳されてないようです。


更新履歴

09/15/02 Version1.1公開
09/07/02 Version1.1
09/02/02 Version1.0
06/xx/02 プロトタイプ完成