Turing Machine Programming

手続的プログラミング言語の元祖,Turing Machine (TM) プログラミング へようこそ! 最も簡単な万能機械を作るという A. Turingの発想からしても, これ以上簡単な万能プログラミング言語はないだろう.遊び心でTMプログラミ ング初歩を楽しんでいただきたい.

テープ上の区間を別の区間にコピーする「生の」TMプログラムを正確に書 くことができるなら,その人はスーパープログラマーの素質があると思う.そ れをさておいても,TMプログラミングの実践がTMの理論をしっかり理解するた めの手段として有効であることは確かである.いそがば回れである.一見無駄 なエネルギーを割くようでも基礎体力作りとして取り組むことを勧める.

以下にあるように条件文 とか While 文を導入準備してからならば,スーパープログラマーの素質がなくて も「コピープログラム」を作れる.つまりは「コンパイラ方式」である.TMプ ログラミングの実践としてはプログラミング環境を便利にしてしてしまうのは 本末転倒かもしれない.しかし達成感も大切であろう.スーパープログラマー の素質のない作者でもこの「コンパイラ法」でコピーTMを作ることができた. おかげで,それなりの達成感とTM計算の貴重な実感も得られたように思う.

コマンド



Turing Machine コマンド例:


履歴を出力

使い方: 上の入力欄にコマンドを入力してからボタンを押します, あるいは,選択欄から論理式を選択し入力欄にコピーして(マウスボタンを離すと自動コピー)からボタンを押します.


● テープ状況はProlog項 L+R で表す.ここで L,R はリストである.たとえば, テープ状況 [a,b]+[c,d,e] は,ヘッドは現在 c の位置であること(cを見ている), ヘッドの左には記号列a,bがその右には c,d,e が書かれており,それ以外はすべて 空白(space)記号が書かれている,というテープ内容とヘッドの位置を表わしている. Prologの単独のリスト R は ヘッドの左がすべて空白の状況 []+R のことと規約する.

● turing(X,Y,Z)はPrologで書かれたインタプリタ述語である.たとえば, turing(right,[a,b],T)は, テープ状況 []+[a,b] のもとで,コマンド right を実行した結果のテープ状況 T を計算する.この例の場合,T=[a]+[b] と出力 される.一般に turing(C,L,T) は,初期テープ状況Lのもとでコマンド C を実行した 結果のテープ状況が T であるという関係を表す.C,L を与えると T が出力され る.次にいくつかの実行例をあげる.この言語の操作論的意味は明快であると期待する.

● turing(X,Y,Z,U) は turing(X,Y,Z) とほぼ同じであるが,第4引数の U には,レジ スターの内容が表示される.デバッグ用である.

● 計算の履歴を表示させるには"history:"をかぶせる.

● 現在試験的に用意しているユーザ定義コマンドは下の def 述語を参照のこと.


right move to the right cell
left move to the left cell
nop no operation
mark mark the currrent position
unmark unmark the current position
get(X) read the current symbol into register X
put(X) write register X to the tape
set(X,Y) X:= Y (assignment)
insert(A) insert A before the current position
$(X) the content of register X
[C1,C2,...,Cn] sequential composition
if(A,C,D) conditional sentence
if(A,C) if(A,C,nop)
unless(A,C) if(A,nop,C)
while(A,C) if(A,[C,while(A,C)])
until(A,C) unless(A,[C,until(A,C)])
(macros) see macro_def below

● 現在次のユーザ定義コマンドを例として用意している. 最初の例は,一進法による数の足しお算プログラミングである. その後ろの節 def(q0,q(a,b,r,q1)) は,本来の TM の5-組の (q0, a, b, r, q1) を表している.つまり提案の言語が任意のTMを模倣できることはストレートにわかる. 逆に,このコンパイラ言語がTMネイティブに翻訳されることも コマンドの定義をひとつひとつ確かめることにより確認できる.
def(add,[mark,right,find(@),put(1),find(@),put(space),left,put(@),home,unmark]).
def(q0, q(a,b,r,q1)).  
def(q1,halt).