スポンサーサイト

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

計算機の基本原理を味わおう20 - 状態遷移と停止問題について考えよう

 この記事は、計算機の基本原理を味わおう19 - 計算機と計算論の続きです。前回は計算論について解説しました。今回も引き続き、計算論の概念を解説します。
 前回少し触れましたが、計算の状態遷移は、手順そのものが観察対象ではありません。対象となる状態の変化について観察します。そうすることにより、プログラムの整合性がわかります。具体例として、not命令で状態遷移を考えていきます。
 状態遷移は何を主とするかで異なりますが、今回はnot命令の入力値で考えてみましょう。任意の入力値は、初期状態を経て、その後反転し、終了します。纏めると次のようになります・・・・
状態0:初期状態。移動先は状態1か2.
状態1:入力値が0の状態。移動先は状態2か状態3.
状態2:入力値が1の状態。移動先は状態1か状態3.
状態3:最終状態(CPUの停止)

状態0 → 状態1 → 状態2 → 状態3
状態0 → 状態2 → 状態1 → 状態3
図にすると菱形になり、初期状態に入る状態がなく、終了状態から遷移する状態がない事がわかります。また、状態が4個しかなく、アセンブラで見るよりも簡潔であることがわかると思います。
 簡潔になる理由は、余計なプロセスを見ないで済むからです。具体的には、最小計算機特有の事情によるジャンプ文や、フラグ操作は本質的ではではありません。それらの余計な情報がなくなる分、状態遷移で考えると本質が見えやすくなります。難しいプログラムを状態遷移で考えると、理解する糸口になることも多いです。
 計算の状態を考える時、課題となるのは停止問題です。計算は有限回数で行うものですから、停止できない(終了できない)のは非常に問題です。なので、停止ができるか否かが課題となります。再びnot命令を使って考えてみましょう。
 停止の有無を判定するには、停止の定義を考えねばなりません。not命令と最小計算機の仕様を考えると、停止する条件は明白です。CPU停止用のcmoveがあり、そこへジャンプするcmoveがあれば停止します。それを踏まえて、実際に試してみましょう。

using System;
using System.Collections.Generic;
using MiniBitMachine;
using MiniBitMachine.V3;
using MiniBitMachine.V3.Utility;

class Sample
{
    static void NotHaltingTest( bool addLast )
    {
        Memory m = new Memory( );
        ExecuteEnvironment info = Cpu.GetEnvironment( );
        byte targetAddress = 3;
        byte ds = 0;
        byte cs = 1;
        Cpu cpu = new Cpu( ds, cs, m );
        Not not = new Not(
            targetAddress,
            cpu,
            addLast );
        not.SetBinary( );
        Console.WriteLine(
            "********** not命令の内容 **********" );
        Console.WriteLine( not );
        Console.WriteLine( "not命令は停止できる? : {0}",
            cpu.Executer.IsHalting( targetAddress, not.Cmovs ) );
        Console.WriteLine( );
    }

    static void Main()
    {
        NotHaltingTest( true );
        NotHaltingTest( false );
        Console.ReadLine( );
    }
}

using System;
using System.Linq;
using System.Collections.Generic;

namespace MiniBitMachine.V3
{
    //機械語命令を実行するオブジェクト。
    internal class Executer
    {
        //関係のないメンバーは省略
        
        //プログラムが停止するか判定する。
        public bool IsHalting( 
            byte targetAddress, 
            IEnumerable<CompareMove> cmovs )
        {
            var match =
                from i in cmovs
                from l in cmovs
                where l.Position == i.Source &&
                    i.Destination == 
                        this._exeInfo.ProgramCounterAddress &&
                    l.Destination == this._exeInfo.LastAddress
                   select i;
            if ( match.Count( ) == 0 ) return false;
            return true;
        }
    }
}

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace MiniBitMachine.V3
{
    //比較移動命令。
    public class CompareMove : IEquatable<CompareMove>
    {
        //関係のないメンバーは省略
        
        //位置。
        private int _position;
        public int Position
        {
            get { return _position; }
            internal set { _position = value; }
        }
    }
}

説明すれば簡単にプログラムが思い浮かぶと思いましたので掲載していませんが、ifオブジェクトに、停止命令追加の有無を、指定できるようにしています。このサンプルを実行すると、終了を表わすcmoveがない場合と、そこにジャンプする命令がない場合にfalseを返すことが確認できます。
 厳密に判定するならば、全てのステップを実行してみて、停止命令にたどり着かない場合にfalseを返すことになりますが、問題の本質はそこではありません。本質は、停止記号とそこに至るルートがあれば停止する事です。
 「なんだ簡単じゃないか」と思った人が居るかもしれませんが、この停止問題は意外と難しいです。例えば、ユーザーの入力に依存したプロセスがあったり、ネットワーク越しのプロセスがあったりすると、停止するかどうかは必ずしも明白ではありません。それに、どんなアルゴリズムでも停止の有無が判定できる万能アルゴリズムは存在しません。ちょっと疑問が残りますが、計算論ではそうなっています。
 これは、チューリングマシンの停止問題というものです。嘘吐きのパラドックスの応用で考えます。正反対の答えを返すチューリングマシンを、チューリングマシンで停止の有無で判定すると、真偽どちらに決定しても矛盾してしまいます。実務家の私としては、要するに仕様が足りないだけ(終了条件に関する情報が足りない)だと思うのですが、計算理論では一応決定不能(真偽を決定できない)となっています。覚えておくと、システム設計時に役立つと思います。続く...
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

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