第2次世界大戦前、チューリングのアイデアによって数学上の
さまざまな問題を解くチューリングマシンが考え出され、
同時にチューリングマシンの限界も提示されました。
それは、数学的問題の中にはアルゴリズムに変換できない問題
は、チューリングマシンによっても解くことができない問題が
存在していることを示したそうです。
チューリングマシンをコンピュータに置き換えると、私はこれを
「解決策を、人間が論理的に置き換えることができるものは、
全てコンピュータで処理することができる」と解釈していましたが、
数学上の問題で論理的に置き換えることができない問題とは
具体的にどんな問題でしょうか?
数学にはあまり詳しくないのでよろしくお願いします。
No.1ベストアンサー
- 回答日時:
ありがとうございます。
残念ながら回答いただいた内容はよく理解できないのですが、
具体例があるということがわかっただけでも納得しています。
No.3
- 回答日時:
すみません, 話をややこしくします.
「計算」を理論的に考えるうえでいろいろなモデルがあります. 有名なのは Turing機械ですが, 他にもラムダ計算だとか項書き換え系だとか D∞ とかがあります. これらはいずれも「計算可能性」について等価 (だったと思う: つまり, いずれか 1つのモデルで記述できれば他のどのモデルでも記述できる) で, 普通に「計算できる」ものは全てこれらのモデルで記述することができます. ということで, 視点を変えて「Turing機械 (など) で記述できるときに『計算できる』と呼ぼう」という考え方が提唱されました. 「Church の提唱」というやつです. これについては広く「うん, そうだね」と認知されていますが実際にそうかどうかは不明. 単に Turing機械よりも広いモデルが見付かっていないだけかも.
ということで, 一応現在では「Turing機械でアルゴリズムが記述できる」=「計算可能」とみなされています. #1, #2 の停止性判定問題 (Halting Problem) は「Turing機械では判定できない」ことが知られており, 「計算不能」とか「決定不能」とかいうラベルを貼ることになります. が, 上に書いたようなことがあるので「あらゆる意味で計算できない」かどうかはわかっていません.
No.2
- 回答日時:
数学のところのほうが詳しい人がいそうですが・・・
チューリングマシンの停止問題そのものは
おおざっぱにやるなら
そんなに厄介な証明じゃないです.
チューリングマシン A が停止するかしないかを
判断できるチューリングマシン Stop があったとします.
StopにAを適用した状態をStop(A)と書き,
停止と判定されたときを True,
停止しないと判定されたときを Falseとします.
このとき
if Stop(X) = True {無限ループ} else {何もしない}
というチューリングマシン X を考えます.
#自分自身の停止性に言及してるところがポイント
これは,X自身が停まるか否かを Stop に判定させて
・Xが停止するときに,Xは無限ループ
・Xが停止しないときに,Xは停止する
という動きをします.
これは矛盾ですよね.
この書き方だと,ちょっと厄介なので,
これの普及版みたいのがあります.
#厳密に言えばちょっと離れてるんだけども,
#本質的なところは「自己言及」という点で同じですので
#ご容赦を
「この紙に書いてあることは嘘です」・・・(A)
と書いてある紙を考えます.
(A)が本当ならば,嘘ではないので,(A)は嘘です
(A)が嘘ならば,書いてあることは本当なので,(A)は本当です
こんなふうに「自己言及」と「真偽」を絡めると
途端に厄介になるというのが本質で,
数学の再構築とか
これは結局ゲーデルの不完全性定理とかにまで発展して,
一大理論を構築することになりました
#・・・いまでもそこから始まった話は進行中なんですよ.
>数学上の問題で論理的に置き換えることができない問題とは
これはですね,いろいろな考え方がありますが,
「一般連続体仮説」と呼ばれる問題なんかが
よくこの手の「不完全性」では引き合いにだされます.
問題そのものの説明とそれがどういう意味で
「論理の範囲外」なのかというのは,かなり数学的なので
省かせてもらいます.
ありがとうございます。
ニュアンスはだいぶわかりました。
質問の発端は、
・チューリングマシン(コンピュータ)で解けない数学の問題がある。
・論理的に表現できる解決策は、すべてコンピュータで解くことができる。
上記2つから、論理的に解決できない数学の問題っていったい何?
もしかして、証明がまだ達成されていなかったころの「四色問題」や「フェルマーの最終定理」のこと?
というのが始まりです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
CRC8を教えてください
-
排他的論理和 BCC(水平パリテ...
-
ホームページビルダーで料金の...
-
計算量の少ないn乗根の求め方
-
変化させるセルが変化しない
-
0xf0=256?
-
C言語についてです。 再帰を使...
-
エクセル VBAで 再計算を...
-
移動平均を計算するプログラム
-
C言語について 下の画像は do-w...
-
OpenGLでの軸回転について
-
C言語初心者。静磁場の計算。台...
-
傾いた四角形内の範囲の条件式
-
CRCについて教えてください
-
C言語で N行*M列 の逆行列を求...
-
VB6.0でのバイナリデータの扱い...
-
VBAでの勤務時間計算
-
Androidでのメトロノーム開発
-
Xwindowのプログラミング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
排他的論理和 BCC(水平パリテ...
-
VBAの再計算が反映されない件に...
-
バッチファイルでウインドウを...
-
変化させるセルが変化しない
-
EXCELなどで「返す」という表現
-
傾いた四角形内の範囲の条件式
-
エクセルで特定のセルのみを任...
-
CとFORTRANの計算速度はどちら...
-
Visual C++でdebugとreleaseで...
-
モジュラス103の計算とは何でし...
-
なぜオーバーフローになるので...
-
VB6で正確なミリ秒を計測したい...
-
VBでReplace
-
引き放し法による除算アルゴリ...
-
matlabで計算終了
-
CRC8を教えてください
-
VBAで関数をつくる
-
Excel VBAの残業時間の合計計算...
-
等高線を計算したい
おすすめ情報