コンピュータが解けない問題はありますか？

質問

タイトルどおりの質問です。
近年、コンピュータの進化は凄いものがありますが、現時点で、コンピュータが解けない問題ってあるのでしょうか？
一応条件として、
（１）人間が作った問題で
（２）人間には解くことができて
（３）コンピュータには解けない
この条件の下でスーパーコンピュータを使ったとして、解けない問題ってあるのでしょうか？。

回答No.16

jedimaster

「問題」「解く」という言葉の定義によるのではないでしょうか。数学的な問題を解くという観点に絞れば人間に解けてコンピュータに解けない問題というのは無い気がします。しかし、問題が漠然としていて、解けたかどうかの定義が曖昧な場合、たとえば以下のような「問題」を「解く」のは今のところ人間にしかできないような気がします。
・にんじん、じゃがいも、たまねぎ、牛肉が冷蔵庫にあるが、旦那が好きなおかずをこれらを使って作るには何を作るのがよいだろう?
・自閉症の子供、症状を観察して有効な治療法はどのようなものか考える医療行為
・自動車の運転
・髪型イメージチェンジしたいという人を前に、どのようなスタイルが似合うか考える。
・オリンピックの床運動の採点

それから、下の方の回答にある
＞チェス・囲碁・将棋が、いつか、オセロゲームのごとく計算機に全解明されてしまうのが、こわいような期待したいような．．．
オセロゲームもまだ計算機に全解明はされていませんので誤解なきよう。
*6x6盤については解明済み、8x8盤については最終40手くらいしか完全読みできません。他のゲームも含め時間の問題(たぶん今世紀中)ですが。
詳細はご興味あればhttp://www.hasera.com/othello/saizen.html
の下の方の解説をご覧ください。

お礼

１年近くも前の質問にお答えいただきありがとうございます。

この質問は「現時点でコンピュータの解答能力を人間が上回ることがあるかな？」と言う単純な疑問から出発したのですが、言葉の定義などあまり厳密なことは考えていませんでした。

今までのみなさまの回答からすると、数学的に答えが決まる問題ではコンピュータには勝てないようですね。
オセロ８＊８盤についてのご指摘ありがとうございました。早速、見てみたいと思います。

回答No.15

graphaffine

質問の意味が掴みきれないのですが、次の問題は
趣旨に沿っていますか。条件（１）～（３）を充たすと思いますが。

「あなたは、パンとご飯とどちらが好きですか」

p.s.　
コンピュータの進化は凄まじいとおっしゃる点、ある意味ではそうですが数学の組合せ理論から見ればまだまだです。例えば、N-クイーン問題と言うものがありますが、現在はたった二十数数次元のものしか解けませんし、今後コンピュータが進歩しても限界がありますから、せいぜい三十次元が解けるようになればいい方だと思います。

お礼

ご回答ありがとうございます。
私の質問の意図は、ＮＯ．１４の方のお礼にあるとおりです。
コンピュータより人間の方が凄い！なんてことは、なかなか無いのでしょうね。
Ｎ－クィーン問題というのは、私は初めて聞きましたので良く解らないのですが、人間は解けるのでしょうか？

回答No.14

gator

組み合わせの問題などで、場合の数がとてつもなく大きくなってしまう
場合に、解けないというものがあるようです。将棋などもその例でしょう。
処理能力が上がっていけば可能なのかも知れませんが。

>人間には解くことができて
将棋で続ければ、人間は経験によって、「こういう流れの時は、これかこの手
が使える」というように、常に場合の数を減らして考えるのに比べて、コンピ
ュータの場合、常に可能な組み合わせの全てを考えるから、追いつかないのでは
ないでしょうか? そこら辺も含めてプログラム化する手法はまだ実現していない
のではないでしょうか?

以前私が質問した問題も例になると思いますので、参考URLに入れておきます。

あと、大学の数学の授業で、「16人のマージャンの総当たり戦の組み合わせは
コンピュータには書けない」と先生が言ってました。これに関しては、答えの時に
休んでしまって聞いていないので、わかりませんが。どなたかわかる方がいたら
よろしくお願い致します。

以上

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=259493

お礼

ご回答ありがとうございます。
私の質問の意図は、「人間は解けるのにコンピュータは解けない問題はあるのかな？」という単純な疑問です。
「１６人の・・・」の答えは人間でも「書け」ないですよね？？？。

回答No.13

bttf2003

＃１０です。「お礼」に
＞広義のコンピュータと狭義のコンピュータの意味が分かりませんでした。（一部、他の人のために引用の文章を補足しました）

と、ありますが続きの「人間が問題解法のプログラムを作ることが出きる問題でも、コンピュータ」と言う文章の「コンピュータ」が、まさに「狭義のコンピュータ」です。
広義のコンピュータは、それ以外の全てのコンピュータを意味しています。（「広義」の意味は、＃１０の回答では、わざと間違って使っています）
つまり、コンピュータと定義できる物理的存在は、全て「広義のコンピュータ」です。（こちらは、言語的に正しい）

言いたかったことは、ふつうに「コンピュータ」と呼んでいるもの以外にも、「コンピュータ」はありますよ！と言うことです。
＃８の方の回答の最後から２行目に書かれている「現在とは異なった原理のコンピュータ」が、広義のコンピュータの１例です。

上記のことを理解されたら、この質問は違った内容になっていたでしょう。（しかしながら殆んど、気にするほどの意味はありません）

お礼

再度のご回答ありがとうございます。
ＨＡＬ９０００などは「広義のコンピュータ」に属するのでしょうか？。人間がプログラムしなくても作動するコンピュータ（？）とは・・・凄い・と言うより怖いような・・・。

回答No.12

shota_TK

関心のある分野なので参加させて下さい。

「問題」の定義を、No.2さんへのお礼に書かれていますが、この時点で圧倒的にコンピュータが有利になりますよね。特に、「解法のプログラミングが可能」と明確に定義してしまっては、勝負にならないと思います。

例えばチェスですが、現在の最強プログラムの原理は、自分vs自分の戦いを無限に続け、「最強の定石」を保存し続ける、という手法ですよね。この場合、プロ（？）の試合の多くの手順が事前にインプットされますので、プロの選手ではコンピュータに勝てません。しかし、三流選手と対戦すると負けることがある、と聞いたことがあります。序盤に予想外の手（例えそれが悪手でも）を打たれると、コンピュータは案外にもろいんですね。

この場合のプログラミングは「解法」ではなく、「解を得る手順になりうるもの」であって、これで解が得られるかどうか、わからないです。だからこそ、人間が勝てる余地が残っているんだと思います。

あとは揚げ足をとるような感じになっちゃうと思いますが、例えば・・・
（1/3）×3＝？
なんて問題はどうでしょうか。コンピュータは有限の桁数しか覚えられませんから、厳密には1になりませんよね。

もちろん、「こういう場合には分数を使え」というプログラミングを入れればいいわけですけど、それは、答えが出るように人間が入れ知恵したことになりますので、「コンピュータが解いた」と言えるかどうか・・・？

結局のところ、人間が解を出すのと同様のアルゴリズムをコンピュータにやらせるわけですから、No.8さんのおっしゃるようなパラドックス系しかないような気がします。

参考URL：

http://www2.ipcku.kansai-u.ac.jp/~saiton/paper/computation.htm

お礼

ご回答ありがとうございます。
お礼を申し上げるのが送れて申し訳ありませんでした。
あまり難しいことを考えず、気軽に質問してしまったのですが、案外奥が深く驚いています。

回答No.11

sanori

ひとりごと的カキコでーす。

＃９さんに同感。
翻訳だけに限らず、日本語漢字変換（ＦＥＰ）なんかでも、完璧を極めようとすると、人工知能に行き着いてしまうんですよね。

＃４さんにも同感ですが、チェス・囲碁・将棋が、いつか、オセロゲームのごとく計算機に全解明されてしまうのが、こわいような期待したいような．．．

ところで、コンピュータが人間を「凌いだ」例は四色問題だと思いますが、四色問題の証明って、未だに計算機による証明しか発表されていないんですかね？

お礼

ご回答ありがとうございます。
私も同感です。
質問最初の意図は、数学的な問題を想定していたのですが、確かに言われてみればその通りだと思います。
人間の能力も、捨てた物ではないですね。
しかし、チェスはコンピュータに凌駕されました。将棋は囲碁は果たして？？？

回答No.10

bttf2003

「コンピュータ」と質問にありますが、コンピュータには大きく分けて「広義のコンピュータ」と「狭義のコンピュータ」の２種類あって、ここで言ってる「コンピュータ」は狭義のコンピュータのことと思います。
狭義のコンピュータを、デジタル式のコンピュータとすれば、
１）問題を作る問題（例：前提なしで、数学の問題を作る）
２）無限を扱ったある種の問題（例：無限に答えがある問題）
３）非論理的問題（例：三段論法が、通用しない問題）
などなど
思いついたままを書きましたが、まだまだありそうです。
現存するコンピュータは、本当の（広義の）コンピュータではありません。

お礼

ご回答ありがとうございます。
私は浅学にして、広義のコンピュータ・狭義の・・・の意味が分かりませんでした。
人間が問題解法のプログラムを作ることが出きる問題でも、コンピュータには解く事ができない問題は存在して、（１）能力的な理由で現在は解けない（将来、能力が上がれば解く事ができる）問題と、（２）コンピュータの構造的な欠点（？）から解く事ができない（おそらくは将来も）問題と２種類あると考えて良いのでしょうか？

回答No.9

noname#27172

私は翻訳だと思います。最近 色んな翻訳ソフトが出回っていますが、どんなに高度な翻訳ソフトでも 納得のいく翻訳はできません。
あと JPEGの画像に関しても 未成年に有害なものを
コンピューターに識別させるのは不可能だと思います。

お礼

ご回答ありがとうございます。
確かに翻訳はそうですね。
前の方の回答と合わせますと、言語関係は苦手のようですね。

回答No.8

aminouchi

ご質問が数学ジャンルですから、数学的なものでお答えしましょう。

端的に言うと、パラドックス系の問題はコンピュータには解くことが出来ないと思われます。例えば「コンビュータでは解けないような問題を作る」という問題を解くことは不可能だと思います。

これは、この問題を作ったと言うこと自体が答えとなっていますからsai1958さんのあげた３つの条件に当てはまっています。

将来において、現在とは異なった原理のコンピュータが作られるか、飛躍的なプログラミング技法が発案されれば解けるかもしれませんが、今の技術と原理では解けないでしょう。

お礼

ご回答ありがとうございます。
恐れ入りました。
答えを理解するのに、時間がかかってしまいました。(^^;
おっしゃるとおりですね。
短時間でこれほど端的なお答えを出すaminouchi様には感服しました。

ありがとうございます。

回答No.7

ranx

> 近年、コンピュータの進化は凄いものがありますが、
原理的にできるかできないかというレベルで言えば、半世紀間、コンピュータ自体に変化は
ありません。メモリーが大きくなっったのと速くなっただけです。
ただ、それを利用して、問題の解き方＝アルゴリズムが進歩したという分野はあるのだと
思います。

コンピュータに解けない問題というだけでしたら、例えば任意のプログラムにバグが
あるかないかを判定するプログラムが作れないというのは、コンピュータが作られる以前から
数学的に証明されていたことですけれど、これは人間にも解けませんね。原理的には、
人間に解けるということは、解く手順が存在するし、解く手順が存在するということは、
そのようなプログラムが作れるということにもなります。

ただ、現状では、解く手順が複雑過ぎて明確にできないという問題はあると思います。
簡単かつ明快な例で、センター試験の国語の問題なんてどうでしょう。あれは満点をとることが
可能だと私は思っていますけれど、現在のソフトウェアには難しいのではないかと思います。
ただ、将来非常にメモリーが大きくなって、超高速化すれば、問題を解くようなプログラムも
作れるかもしれません。（そんなものを作る暇人がいればの話ですが。）

お礼

ご回答ありがとうございます。
国語の試験とは、なるほど！。
確かに、プログラミング自体も難しそうですし、１００点も難しいような。