スポンサーサイト

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

ネタつつき193 - チューリングマシンの停止問題を実務的に解く

 現実で起こる問題は、チューリングマシンの停止問題のような、矛盾に満ちています。しかしながら、現実は矛盾しているといって終われるほど簡単なものではありません。情報システムを開発業務をしていると、矛盾がデフォルトの状態になります。人間ははえてして矛盾したことを望むものです。従って、理論的には矛盾していることが明白なことに対しても、実務ではそれなりの答えを出さねばなりません。今回はそれを踏まえて、チューリングマシンの停止問題を実務的に解くことを目指します。最初に断わっておきますが、この記事で言っている解法は、数学的ではありません。あくまでも、現実にある問題を解くための実務的な考え方を述べています。
 まずは、チューリングマシンの停止問題を知らない人のために、簡潔にこの問題を書きます。チューリングマシンの停止問題とは、チューリングマシンMと記号列wからなる対( M, w )を受け取り、停止するならばYesを、停止しないならばNoを返すチューリングマシンMwを定義する。このチューリングマシンMwに対して、いかなる入力値( M, w )に対しても答えを出せるアルゴリズムが、あるか否かを決定する問題です。
 チューリングマシンの停止問題は、計算論的には決定不能であるとされています。何故ならば、入力値として、Mwと反対に動くMを定義すれば、どちらの結果にしても矛盾が生じるからです。つまり、MwがYesを返す場合Mは停止せず、MwがNoを返す場合Mは停止しますです。なんと厄介なチューリングマシンなのでしょう!この結果は、理論的に矛盾しているので、Mwの存在自体があり得ないと結論付けできます。まぁ、妥当な理論だと思います。しかし実務ではそれで済ませられません。「解法がわからないからお前に依頼しているんだ。」と言われるだけです。従って、どうにかして矛盾を克服せねばなりません。これから、チューリングマシンの停止問題を、強引に解いていきます。
 まずは、矛盾の原因を探ります。矛盾の要因は明らかに、MがMwを参照している事です。しかし、アルゴリズムは、有限回数で解かねばなりませんので、どちらか先に答えを出さねばなりません。その考えを元に、私ならば次のアルゴリズムを設計します・・・

【停止判定アルゴリズム】
0、各オブジェクトを初期化する。
1、MがMwを参照しているか否かを判定する。参照しているならば手順2へ飛ぶ。
 参照していないならば手順4へ飛ぶ。
2、Mwに入力値wを入力する。それをMに渡す値Yとする。
3、手順5へ飛ぶ。
4、入力値をMに渡す値Yとする。
5、Yを適用しMが無限ループするならばNo、しないならばYesを返却値として設定。
6、Mを終了。
7、返却値を返す。

簡単なアルゴリズムなので、内容をすぐに理解できると思います。内容を簡潔に言うと、ただのnot論理演算子です。Mwは任意のMを入力値して指定できる時点で、Mw自身を参照している可能性を考えねばなりません。ならば、想定外を想定し、それを判定すればいいだけです。これで一応解決できます。数学的には反則なような気がしますが、綺麗な理論だけでは現実で通用しません。
 今回の記事いかがでしたか?あまりスマートではありませんが、矛盾を解くには、強引な解法が必要です。理論に傾倒せず、柔軟に物事を考えれば、どんな決定不可能な問題でも解けると思います。現実は理論的に矛盾している事の方が多いので、理論に拘らず臨機応変に行動しましょう。そうすれば、答えは必ずあるのです。
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

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