【Linux で科学しよう！】 【Linux MLD】 【メディアラボ】
gTuring

gTuring

gTuring はチューリング・マシンのシミュレータです。 コンピュータ科学を学ぶものなら誰でも名前は知っていると思いますが、 実際にプログラミングしたことがある人は少ないでしょう。 gTuring で計算機の黎明期に想いを馳せてみてはいかがでしょうか？

(右図をクリックすると大きく表示します。)

作者: Arturo Espinosa Aldama さん他
ホームページ: http://www.nuclecu.unam.mx/~arturo/gTuring/
バージョン: 1.3 ? (2001/02/06)
ライセンス: GPL
付属ドキュメントを読む

上記の Aldama さんのホームページは ほとんど更新されていません 消滅したようです。 最近は Germán Poo-Caamaño さんが GNOME 2 用にメンテナンスしています (ここ に少し情報がありますがよく分かりません。 freshmeat の Project ページ はまだ残ってます)。

gTuring は GNOME 1.x のときはなぜか「ゲーム」に分類されていて gnome-games に含まれていました。 でも LinuxMLD 5 の gnome-games-1.2.0-9.i386.rpm では gTuring はビルドされないようになっていました (ゲームと思って動かした人には「なんだ、こりゃぁ」となるでしょうから Red Hat が外したのでしょう)。
ここで御紹介するパッケージは gnome-games Ver.1.3.90 から gTuring を取り出したものです。 LinuxMLD 6 の gnome-games-1.4.0.1 には gTuring を含めています。

使い方

インストールすると LinuxMLD 7 では「ゲーム」→「他のゲーム」にメニュー「Gチューリング」が追加されます。 MLD 5, 6 では「プログラム」→「ゲーム」になります。
ターミナル・エミュレータからは 

$ gturing

で起動します。

サンプルがいくつか付いていますから、そのプログラムを動かしてみましょう。
「ファイル」メニューから「開く...」を選択するとファイルダイアログが 開きます。 上に並んでいるボタン右端の「Examples」をクリックするとサンプルのある ディレクトリに移動します。 一番上の 3ones2zeroes.tur をやってみましょうか。

ファイルを選択して「了解」すると

と説明 (プログラムのコメント) が出て来ます。 ふむふむ、「1」が連続して３つ出て来たら「0」に置き換える……と。
次に「設定」メニューから「テープ...」を選択して、例えば次のように 入力します。

01011001110011101010

そして「実行」ボタンをクリックします。すると、ゴソゴソ動いて、なるほど、

01011000000000001010

になりました。

「表示」メニューから「状態」を表示させておいて、「ステップ」で実行すると 動きがよく分かります。

入力データの下で左右に移動する「^」はテープヘッドです。 すなわち、チューリングマシンとは、データをテープ (つまり１次元の文字の列) で 与えると、ヘッドの位置の文字を読み取ってその文字によって内部状態を変える 有限オートマトンです。

ある状態で入力に対してチューリングマシンがすることは、 出力 (テープ上の文字の書き換え)、ヘッドの移動 (右または左)、 次の状態への遷移です。 この５つを組にして書き並べたものがチューリングマシンのプログラムです。

上のプログラム 

 0  0  0  r  0 
 0  1  1  r  1 
 1  0  0  r  0 
 1  1  1  r  2 
 2  0  0  r  0 
 2  1  0  l  2 
 2  _  _  r  0

は次のように表に書き直すと分かりやすくなると思います。状態と 入力に対して、出力、移動、次の状態を並べて書いています。

  入力
 状態  0 1 _
0  0R0   1R1       
1 0R0 1R2  
2 0R0 0L2  _R0 

入力および出力の文字は gTuring では印刷可能な任意の文字が使えます。 ただし空白は、プログラム上はアンダースコア「_」で表します。 ヘッドの移動は小文字で l (左) または r (右) ですが、 上の表では (イチ と エル が紛らわしいので) 大文字で書いています。 gTuring の初期状態は、ヘッドは入力の左端にあり、状態は 0 です。 状態および入力に対して動作が規定されていない状態になったら、停止します。

gTuring のプログラムはテキストファイルですから通常の テキストエディタで簡単に作ることができます。フォーマットについては 「ヘルプ」メニューから表示できるドキュメント (Ver.1.2 だけど フォーマットの変更はないようです) に書かれています。

こんな「マシン」で何が出来るのか、「計算」なんてできるの？ と思う人もいるでしょう。ちゃんとできます。なにしろチューリングマシンは 1936 年に Alan Turing が「計算できる」という意味を示すために 提示した仮想機械です (後の 1945 年に von Neumann が EDVAC で具体化しました)。 言い換えると、チューリングマシンで出来ることが「計算」なのです。
付属サンプルを試してみてください。

add.tur
なんと１進法の加算です。 0 で区切って２つの１進法を与えます。 例えば「01101110」(つまり 2 と 3) を与えると 「0111110」が答えです。
addbin.tur
上のサンプルでは「こんなの計算と言えるのか」という気も しますが、こちらは２進数の加算です。 ２つの２進数を空白で区切って与えます。 例えば「10 11」(つまり 2 と 3) を与えると 「101」が答えになります。
bin2dec.tur
２進から十進への変換をします。実際には十進数に２進数を加算します。

もうすこし「賢く」加算をするプログラム BinaryAdd.tur を作ってみました。addbin.tur とは違って桁ごとに計算します。
もうひとつ、 SortABC.tur は、「A」「B」「C」の ３種類から成る文字の列をソートします。

インストール

LinuxMLD 6 では標準でインストールされています。

MLD 5, 7 では gturing-1.3.90-1.i386.rpm (75,908 bytes) をインストールします。
rpm コマンドでインストールするにはスーパーユーザになって 

# rpm -i gturing-1.3.90-1.i386.rpm

とします。
MLD 5, 6 では Gnome の GUI でインストールすることもできます。

その他

Ver.1.3 から状態遷移表の編集ができるようになったのですが、 「Editing is still alpha. Come back later or hack.」と警告が表示されるように まだ十分なものではないようです。なにしろ追加はできるけど削除ができません。 １、２ヶ所の修正なら使えますが、別のテキストエディタで修正して 読み込み直した方が早いでしょう。

その場合、 Gnome のメニューから起動するとファイルダイアログのディレクトリが 毎回ホームディレクトリから始まってしまうので、 ターミナルからコマンドで起動する方がいいです。 (Ver.1.2 ではサンプルファイルのあるディレクトリから ダイアログが始まっていたのに比べれば、少しはましになりました。)

新しい GNOME 2 バージョン でも編集機能はまだ完成していません。
なお、GNOME 2 バージョンの .tur プログラムに日本語コメントを付ける場合の文字コードは UTF-8 にしてください。

ここで御紹介しているパッケージでは調整していますが、 gTuring を収録しているディストリビューションによっては、 日本語環境で動作させるとテープ内容の文字列と、ヘッド位置を示す ^ がプロポーショナルフォントになって、位置がずれてしまうようです。 そういう場合は 

$ LANG=C gturing

のようにして (メニュー等英語になりますが) 起動するとよいでしょう。

参考

Web 上の参考になるページを御紹介します。

チューリングさんは、第２次世界大戦中にドイツの暗号 ENIGMA の解読を行なったことでも有名です (そのあいだ「行方不明」になっていたとか)。 genigma のページ を参照してください。
オートマトンの一種、セル・オートマトンについては Xlife のページを参照してください。

[2001/03/23 作成] [2005/10/01 更新]
【Linux で科学しよう！】 【Linux MLD】 【メディアラボ】
このページに関する御意見、御要望を science@mlb.co.jp までお寄せ下さい
Copyright © 2001-2005 Media Lab. All Rights Reserved.