スポンサーサイト

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

ネタつつき197 - 現実のアルゴリズム停止性

 チューリングマシンの停止問題は、理論的には面白いのですが、実務的にはすぐに溶ける問題ですし、直接の役に立たないので、実務的な停止問題について考察しました。結論から言いますと、停止問題は確率の問題だと思います。
 考察に当たり、最初に停止問題の定義を考えてみましょう。計算機が停止するとはどういう意味でしょうか?私が思うに、終了状態に状態遷移できないことだと思います。具体的には、アルゴリズムの次のステップに進めない、循環ループしている、永遠に入力待ちにしている・・・などの状態です。一緒に個々の状況を考えてみましょう。
 一番多いのが、循環ループなどの理由で、終了状態に状態遷移できない状態です。これは、ループを脱出する条件を満たさない事が原因です。状態遷移木を作って探索すると検出できるでしょう。
 厄介なのは、人間の手が介入したときです。例えば、ユーザーが忘れて、ダイアログのボタンを押すなどといった、求められた操作をしないとき、アルゴリズムは前に進みません。これは機械的には解決できない問題です。制限時間を過ぎたら自動的にOKとみなす、などといった対策は可能ですが、心理的にはあまり好ましい解決方法でありません。後で勝手に処理をしたと怒られるかもしれません。
 他にもさまざまな要因が考えられます。ネットワークでパケットが紛失した、CPUが熱暴走した、HDDが破損した、怒った妹にPCを壊された、猫にESCボタンを押された、クラッカーにやられた、必要なファイルを消された・・・などといったことが起こるかもしれません。これも、広い意味で停止問題だといえるでしょう。
 これらの事例を考えてわかることは、真偽の2値ではなく、0以上1.0以下の浮動小数で表したほうが現実に即しているということです。文章ではわかりにくいと思いますので、実際に計算してみましょう。
 アルゴリズムXがあるとします。このアルゴリズムXは4つのステップA~Dで成り立っています。A:開始状態( 1.0 )、B:入力値待ち( 0.8 )、C:変換処理( 0,9 )、D:終了状態( 1.0 )だと仮定します。Bは10回に2回ユーザーに無視され、Cは10回に1回変換ミスで処理がストップするとします。このアルゴリズムの停止性は、1-( 1.0 * 0,8 * 0.9 * 1.0 ) =  1 - 0.72 = 0.18です。従ってアルゴリズムXは18%の確率で停止します。書き直したほうがよいでしょう。
 現実的な停止問題を考えるうえで、もう一つ考えるべきことがあります。それは、「区間」です。10日停止しないのと、100年停止しないアルゴリズムには天と地の差があります。基準となる区間をはっきりしないと、停止度を計算できません。
 察しがいい人は気付いたと思いますが、この問題は耐故障性と関連が深いと思います。ただし、故障していなくてもアルゴリズムが停止しないこともあるので、今回述べた停止性の一部が故障性だと考えるとよいと思います。
現実は複雑なので、すべての事象を列挙できないので、正確に求めることは不可能に近いですが、概算でいいのでアルゴリズムの停止性について考えると、よいシステムを構築が出来上がる確率が増えます。がむしゃらにアジャイル開発するのではなく、たまには立ち止まって、理論をじっくりと考えることも必要だと私は思います。
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。