スポンサーサイト

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

ネタつつき194 - チューリングマシンの停止問題から見える仕様定義/分析/設計能力

 チューリングマシンの停止問題は、仕様定義能力、分析能力、設計能力、実装能力などの総合能力が試されます。これは大変面白い事なので、チューリングマシンの停止問題における、上流部分(仕様定義、分析、設計)を考えてみましょう。
 私は職業柄、こうしたことは得意で、チューリングマシンの停止問題を読んで1分未満で、実務的に解く方法がわかりました。こういった類の問題は、システム屋が毎日している事なので、一応の答えを出すことは簡単です。では、どうやって考えたのか、興味がある人が居るかもしれませんので書きます。
 チューリングマシンの停止問題で実務的に考えるべきことは、何が求められているのかです。チューリングマシンの停止問題で要求されているのは、停止の有無を判定するアルゴリズムです。では、アルゴリズムとは何か、それから考えねばなりません。
 アルゴリズムを簡潔に述べると、有限回数で答えを出す方法です。従って、求められている事は、任意の与えられたアルゴリズムの停止の有無を、有限回数で決定する方法です。これが決まれば8割ぐらい終わったといえます。要求がわかれば、答えを用意することは比較的簡単です。何故ならば、現実の問題は要求を捉えることそのものが難しいからです。
 次に考えるべきことは、チューリングマシンの仕様です。チューリングマシンは、有限制御部、入力テープ、テープヘッドから構成される計算モデルです。そして、形式的には、状態、テープ記号、空白記号、入力記号集合、動作関数、初期状態、受理状態の集合からなります。加えて、手続きは有限で、機械的に実行できるステップでなければならないという制約もあります。これらの条件を踏まえ、そこからオブジェクトを導き出しつつ、アルゴリズムを解くことになります。
 最後に考えねばならないのは、チューリングマシンを処理するチューリングマシンと、そのチューリングマシンに渡されるチューリングマシンのどちらが上位かという事です。求められているのは、チューリングマシンの停止有無を判定する、チューリングマシン用のアルゴリズムなので、チューリングマシンを処理するチューリングマシンの方が上位です。上位が決まれば、有限回数かつ機械的なステップで解く方法を導き出せます。
 ここまで分かれば後は簡単です。循環ループにならないようにアルゴリズムを設計するだけです。何故ならば、チューリングマシンを処理するチューリグンマシンの要求定義が、必ず最後は停止するとなっているからです。また、上位であるという事は、引数として渡されるチューリングマシンを制御できるという事を意味しますので、それが決まった時点で答えは明白だといえるでしょう。
 このチューリングマシンの停止問題は、数学的には背理法で矛盾していると導きだされるのですが、これに疑問を持てるか否かで、実務能力に差が出ると思います。この論法には明らかにミスがあります。それは、入力値を無視している点と、渡されるチューリグンマシンの動作と、処理する側のチューリングマシンの動作が同一視されている点です。また、どうやって値を返すのかが曖昧です。これだけ定義が厳密に定められていないのですから、たとえ数学的には通用しても、実務では通用しません。私は数学とはもっと厳密的なものだと思っていたのですが、意外と曖昧なようです。数学はプログラミングよりも宣言的なのです。ヒルベルトさんの気持ちがわかるような気がします。
 現実は宣言的に論理的矛盾している事柄によく遭遇します。しかし、論理的に矛盾していると思考停止してはなりません。人間は論理的に矛盾していることをよく要求します。従って、論理的に矛盾していることに対して、如何にして答えを提供するのかが我々の課題であり、それをできる能力が実務能力だといえます。実務家にとって論理的矛盾は出発点です。思考停止せず、より深く考え続けましょう。
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

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