スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#で入門 コンパイラ 、インタプリタ編 チューリング・マシン(3)

 今回は前回作成したチューリング・マシンのソフトを使って何かプログラミングしてみたいと思います。 
今回作成してみるプログラムは2進数に1を加えるというプログラムです。 
「最初にテープに位置0から11011と印字されていれば、プログラムの実行の結果11100となり停止」というようにします。計算結果のヘッドの位置は最小位の数字の右隣で止まるようにします。 
 
最初の状態番号は1でこの時、まず数字がない部分までヘッドを右に移動します。 
数字がない部分に行き当たれば状態番号2に遷移せてヘッドを左に移動します。 
この部分のコードが次です。 
(状態番号、ヘッド値、遷移状態番号、書き込み動作、移動) 
1,0,1,_,1 
1,1,1,_,1 
1,_,2,_,-1 
 
状態2(これは繰り上がり1の状態で桁上がりの処理をしなければならない場合です。)になったら、 
(1)読み込んだ数字が0なら1に書き換えて終了準備(単にヘッドを右端にもっていくだけ)の状態3に移行します。 
2,0,3,1,1 
(2)読み込んだ数字が1なら0に書き換えて、繰り上がり1の状態(すなわち状態2)で、左にヘッドを動かします。 
2,1,2,0,-1 
(3)読み込んだものがプランク_なら、1を書き込んで終了準備(単にヘッドを右端にもっていくだけ)の状態3に移行します。 
 
状態3(これは終了準備(単にヘッドを右端にもっていくだけ))になったら 
(1)読み込んだ数字が0か1なら、単にヘッドを右に移動します。 
3,0,3,_,1 
3,1,3,_,1 
(2)ブランク_なら、ヘッドを左に動かして、終了状態を4として4に移行します。 
3,_,4,_,-1 
 
以上でプログラムは出来上がりです。まとめて表記すると 
 
1,0,1,_,1 
1,1,1,_,1 
1,_,2,_,-1 
2,0,3,1,1 
2,_,3,1,1 
2,1,2,0,-1 
3,0,3,_,1 
3,1,3,_,1 
3,_,4,_,-1 
 
終了状態番号は4 
 
例えばテープ初期値を 
として、前回のソフトで実行すると 
実行前が 
 
1045-1.jpg
 
で 
実行後が 
 
1045-2.jpg
 
 
になります。 
 
なお、定期ブログ更新を3ヶ月ほどお休みする予定です。 
 
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

trackback


この記事にトラックバックする(FC2ブログユーザー)

まとめ【F#で入門 コンパイラ】

 今回は前回作成したチューリング・マシンのソフトを使って何かプログラミングしてみたいと思います

コメントの投稿

非公開コメント

承認待ちコメント

このコメントは管理者の承認待ちです

承認待ちコメント

このコメントは管理者の承認待ちです

承認待ちコメント

このコメントは管理者の承認待ちです

承認待ちコメント

このコメントは管理者の承認待ちです

承認待ちコメント

このコメントは管理者の承認待ちです

承認待ちコメント

このコメントは管理者の承認待ちです
プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。