チューリングの有名な停止性問題ですが、
「全てのプログラムMと全てのデータIに対して、
(1)M(I)が有限時間で停止するなら、H(M, I)は有限時間でYESを出力して停止する。
(2)M(I)が無限ループに入って停止しないなら、H(M, I)は有限時間でNOを出力して停止する。
ようなプログラムHは存在しない。」
という趣旨だと思うのですが、
人間(優秀なプログラマー)がM(I)を解読すれば、そのプログラムが有限時間で終わるか無限ループになるかは判断できるように思うのですが、この停止性問題はこの人間の判断もできないと言っているのでしょうか?それとも人間には判断できるが、それをプログラムに書いて機械に判断させることはできないといっているだけなのでしょうか?
No.4ベストアンサー
- 回答日時:
チューリングの停止問題が主張するのはあくまで、
プログラムMとデータIの『どのような(M,I)の組み合わせが入力された場合でも』、それが停止するか否かを判定できるようなプログラムHは存在しない。
という事です。『』で括った所がポイントです。つまり、与えられたどんなプログラムについても判定出来るような万能の停止判定プログラムはない、と言ってるんですね。
「特定のM(I)について停止判定できるか」について、停止問題は何も語っていません。
例えば停止状態への遷移が一切ないプログラムは当然無限ループしますし、逆に逐次処理だけでループ構造の一切ないプログラムは停止するに決まっています。
もっと複雑なプログラムについても、プログラマーが上手く解読すれば、停止するかしないかを証明できるかもしれません。あるいは非常に複雑なプログラムであれば、どう頑張ってもできないということもあるかもしれません。また、部分的な停止問題を解くプログラム、例えばC言語ならfor(;;)やwhile(1)をヒントに無限ループを検出できるプログラムはありえます。しかし、このプログラムはforやwhileが使われていないプログラムには無力ですから、チューリングの停止判定プログラムHになる資格がないわけです。
そして、もう一つ大事なことは、そういう「プログラムが存在しない」ことを言っているだけ、ということです。
停止するかしないかを絶対に証明できないプログラムが存在する、と言ってるわけではありません。
あらゆるプログラムに対応して「そのプログラムは停止するかしないか」の証明は存在するのかもしれません。停止問題はそれを見つけ出すプログラムが存在しないと言っているだけです。証明の存在については何も言っていないのです。
これを踏まえて、質問に応えるとするなら、
>人間(優秀なプログラマー)がM(I)を解読すれば、そのプログラムが有限時間で終わるか無限ループになるかは判断できるように思うのですが、
特定のM(I)についてなら、人間またはプログラムが停止するかどうかを判定する事はできる可能性があります(できないかもしれません。M(I)次第です)。
>この停止性問題はこの人間の判断もできないと言っているのでしょうか?
特定のM(I)に特化した証明を人間またはプログラムが作る事は可能かもしれません(不可能かもしれません)。どんなM(I)についても適用して判定できる万能のプログラム(アルゴリズム)は存在しません。これがチューリングの主張です。
>それとも人間には判断できるが、それをプログラムに書いて機械に判断させることはできないといっているだけなのでしょうか?
これは人間とプログラムに本質的な違いがあるかどうか、という哲学的・神学的な問題ですね。
人間の脳なんかただのニューロンオートマトンだという立場に立てば、人間と機械のできる事に違いはありません。(大多数の科学者はこっちの立場でしょう)
人間は霊感・神託(オラクル)を受け取る不思議な力があって、それはチューリングマシンの能力を超える計算を実現しているのだと信ずる立場であれば、そのときはあらゆるプログラムの停止性を判定するアルゴリズムが存在するのかもしれませんね。(そのアルゴリズムの一部には神託が組み込まれているはずです)
No.5
- 回答日時:
もう少し狭い世界の話として、有名な P≠NP 問題というのがあります
http://ja.wikipedia.org/wiki/P%E2%89%A0NP%E4%BA% …
この範囲の世界の話として問題が有限時間で解けるかは重要な未解決問題ですが
現状、経験論として多分P≠NP らしい、といわれています
この範囲でも未解決の問題ですので、現状はなんともいえません
No.3
- 回答日時:
「チューリングマシンの論理体系の外部にそれとは別の新たな論理体系を作って、それでもって停止性問題を解く」っていわれても, その「別の新たな論理体系」とやらを実際に見せてもらわないことには話にならんわけですが....
1つ明らかなのは, チューリング機械の停止性判定をするためにはその「別の新たな論理体系」を完全にチューリング機械と無関係にすることは不可能ということ. つまり「別の新たな論理体系」とは言っても, それはチューリング機械を含む体系でなければならないわけです.
で, 実際「停止性判定問題が解ける」体系は容易に作れます. 単に「停止性判定問題を解くオラクル」を投入するだけです.
とはいえこの体系が判定問題に対して完全かというとそうはならず, この体系においても「解くことのできない問題」というのはやっぱり存在します.
この回答への補足
ちょっと言葉の意味が分かりません。
「オラクル」って何ですか?私はデータベースのオラクルしか知りません。
言われていることは、多分ゲーデルの不完全性定理のことを言ってられると思うのですが、
要するに、停止性問題を解決できるようにチューリングマシンの体系を拡張しても、それ以外でまた新たに解決できない問題が出てきてしまう。
そういうことですよね?
No.2
- 回答日時:
まず、チューリングの停止性問題というのは、「……のようなプログラムは、チューリングマシンで表現(実現)できない」という意味です。
さらに、「すべてのプログラムとデータの組み合わせに対して」という前提を理解することが必要です。
「すべての M(I)」という意味は、「見たこともない」組み合わせや、「具体的には考えられない」組み合わせも含みます。
つまり、その組み合わせを「有限時間で実際に判断してみる」ということはできないわけです。
「実際に判断してみる」ということはできなくても、「そのようなプログラムは存在しない」ということが証明できたというのが、重要なのです。
No.1
- 回答日時:
この命題は,
「人間が判断できるかどうか」
については何も言っていません.
ただ, 実際には「人間の判断」とやらをどう定義するかって問題があります. 「チューリング機械で書ける」ということをもって「人間が判断できる」と定義するなら, 停止性問題から「人間も判断できない (ことがある)」という結論になる.
この回答への補足
人間が判断するということは、多分、
チューリングマシンの論理体系の外部にそれとは別の新たな論理体系を作って、それでもって停止性問題を解くということになると思うのですが、
その場合は、解ける可能性はあるということなのでしょうか?(おっしゃるように、チューリングの停止性問題はそのことには何も言っていないと思いますが)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 車検・修理・メンテナンス 4GR-FSE 電動ファンが止まらない 3 2022/09/10 17:35
- ノートパソコン Windows 10 動作改善方法 6 2023/04/26 22:30
- エアコン・クーラー・冷暖房機 富士通のエアコンですが、作業員に見て貰っても、以後冷房運転が時々止まり困ってます。 6 2022/07/18 19:22
- 消費者問題・詐欺 お金を取り返すことは可能でしょうか? 4 2023/01/07 13:17
- 事件・犯罪 私有地の横断歩道では、道路交通法は適用されますか? ショッピングセンターの入口と駐車場の間に横断歩道 2 2023/03/17 21:44
- 訴訟・裁判 調停に関しての一般的な質問 6 2022/05/21 10:53
- メルカリ メルカリ本人確認について メルカリの本人確認 住所、氏名、電話番号、生年月日登録必要かと思います 友 2 2022/03/27 23:54
- 哲学 エポケーとは? 2 2023/01/13 20:27
- 洗濯・クリーニング・コインランドリー 【止まってばかりの洗濯機…これって洗えてますか?】 ※長文です。すみません とても困っておりますので 4 2022/03/30 11:50
- その他(クラウドサービス・オンラインストレージ) 海外アップローダーのクレジットカード請求を止めるには 2 2022/04/10 19:33
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
あるプログラムのコマンドライ...
-
Excelで4096点以上のFFTの方法
-
このプログラミング誰か教えて...
-
PICマイコンのコピー(クローン...
-
テキストボックスのエンターキ...
-
Excelに埋め込んだVBAのプログ...
-
プログラムを斜めに並べる
-
「Outlookが他のプログラムによ...
-
Notepad++の関数リスト表示でC...
-
円周率を求めるC言語のプログラム
-
等差数列の和を求めるプログラム
-
表計算プログラムの作り方
-
寿命
-
ラベルのアドレスを知る方法は...
-
Vba UserFormを前面に出す方法...
-
VBAにてメール作成した際、一部...
-
COBOLの連絡領域について
-
XnViewにwebpを「いつも開く」...
-
自動クエリとはどういうもので...
-
グラフをC#のASP.net MVCで表示...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Excelに埋め込んだVBAのプログ...
-
Notepad++の関数リスト表示でC...
-
あるプログラムのコマンドライ...
-
これってほんとにみますか?
-
Excelで4096点以上のFFTの方法
-
「Outlookが他のプログラムによ...
-
自動クエリとはどういうもので...
-
VBAでユーザーフォームが自動的...
-
VBAにてメール作成した際、一部...
-
PICマイコンのコピー(クローン...
-
テキストボックスのエンターキ...
-
読み込み中にアクセス違反が発...
-
特定のwebサイトのタイトルや記...
-
未使用の変数を一括検索する方法
-
モジュール、アプリケーション...
-
COBOLの連絡領域について
-
Google カレンダーの商用利用
-
エクセルとワードをデスクトッ...
-
ドロップダウンリストの文字を...
-
binファイルってiphone専用です...
おすすめ情報