脳と量子コンピュータ

質問

NP問題を多項式時間で「直感的に」解けてしまう人がいたとします。
その場合、人間の脳は、量子コンピュータだと言えるでしょうか？

また、そういう実例というのは存在するでしょうか？
私は、インドに「素因数分解を瞬時にする双子」がいるとかいううわさを
耳にしたことがありますが、出典は分かりません。

※1　量子コンピュータの定義は適当にしてくださって結構です。
明らかに間違った定義は困ってしまいますけど＾＾；
※2　カテ違いのような気がしますが、
「NP問題」の説明にあまり自信がなかったので、
「数学」にしてみました。
※3　回答者同士の議論、まったくもってかまいません。
もちろん、中傷・誹謗などは禁止です。

回答No.3

ranx · ベストアンサー

どうも、また来ました。
ibm_111さんのような素直な方に対して、私の表現はひねくれ過ぎていたようです。
前回書いたのは、要するにこういうことです。

人が多項式時間でＮＰ問題を処理できていることが示せれば、人の脳がテューリングマシン
ではないことを示す根拠になるだろう。しかし、それを実証するためのテストは終了する
ことができない。（無限回とはそういうことです。）よって、この質問には答えることが
できない。

大きな数を直観的に素因数分解できる人は存在するかもしれない。しかし、恐らく限度が
あるし、その場合の脳の能力は有限状態オートマトンと同等程度でしかない。

というわけで、ibm_111さんが受け取られたのとは恐らく正反対のことが、私の真意です。

ただし、これは、時間の計測によって答を出そうとするならばという話です。実際のところ
どうなのか。人間の脳はテューリングマシンなのかということですが、理性的・論理的に
答を出す能力について言うならば、テューリングマシンと同等だろうと思います。
チャーチらが提唱したのは要するにそういうことだと理解しています。では、それが人間の
脳の能力のすべてなのかということになると、よく分かりません。個人的には、自分自身の
限界を認識してそれを乗り越え、自分自身を再構成する能力というのは、多分テューリング
マシンには無いだろうと思うのですが、証明できるものなのかどうかも分かりません。

回答No.2

ranx

前提が非現実的で答え難い。誰か替わりに答えてくれないかなあ、と思っていたのですが、
どうも人気ないですね。

例えば、無限に大きなメモリーを持っている機械が有ったとして、全ての自然数（！）に
対する素因数を予め記憶していたとします。この機械はあらゆる素因数分解の答を瞬時に
出すことができます。これはもちろんテューリングマシンではありません。では、例えば
一応有限のメモリー内に、１億桁以下の自然数の素因数をすべて記憶している機械だったら
どうでしょうか。この機械は、形式的には有限状態オートマトンに過ぎません。それでも、
自然数の値に関わり無く瞬時に素因数分解の答を出すように見えます。１億桁以内ならば。
仮に１億桁までテストして、それで終わりにしてしまったら、違いは分かりません。
メモリーが大きければ、それだけ大きな数でも非テューリングマシンのように動作します。
ということは、この機械が有限状態オートマトンではないということを確認するためには、
無限に大きな数までテストしなければ、確定的な判断はできないことになります。その
ようなテストが可能だという前提でお考えでしょうか。

現実世界の「素因数分解を直観的に行う人」について言えば、そういう人がいるのかどうか
知りませんが、比較的小さな素因数を含む場合はさほど困難ではありません。問題は、大きな
素数を掛け合わせた数について正しく答を出せるかどうかなのです。このやり方は、実は
上記のアナロジーで考えることができます。そのような数を、予め九九のように記憶して
おけばよいのです。３桁×３桁くらいならば、頑張れば何とかできそうな気がします。
４桁×４桁となると、もう超人的ですね。しかし、そこら辺が限度ではないでしょうか。
何十桁、何百桁という、大きな素因数のみの分解を直観的に行える人がいるとは信じられ
ません。

一応、以上のことを踏まえ、無限回のテストを行うことができたとしたならば、ご質問の
> そういう人が存在して、しかもNP問題は「真に困難である」のなら、
> 脳はチューリングマシンでない、と言い切ってしまってよいのでしょうか？
は、その人の脳に関しては（全ての脳ではなく）、テューリングマシンではないと言えると
思います。

補足

>どうも人気ないですね。

まったく。もうちょっと意見を戦わせてほしかったのですが。
哲学カテゴリーのほうがよかったかな・・・
現実性がなさすぎましたかね。
それはともかく、ご回答ありがとうございます。

>そのようなテストが可能だという前提でお考えでしょうか。

一応、可能という前提で、お願いします。
脳のメモリがそんなに大きいとは思えないので。

>その人の脳に関しては（全ての脳ではなく）、
>テューリングマシンではないと言えると思います。

慎重な言い方ですね。
実は私も「その人の」という言葉をつけるかどうか迷ったのですが、
脳の構造が人により、それほど違うとは思えないので
その言葉をつけなかった次第です。
厳密に言うと、
「ある特定の問題に対して、（訓練次第で？？）全ての人間の脳はチューリングマシンでなくなる可能性があるか？」
ということになるでしょうか。

しばらくこの問いは空けときますので、
なんかご意見がありましたら、コメントください。

回答No.1

ranx

「多項式時間＝短時間」ではありませんよね。
多項式時間であっても、要素数が多くなれば膨大な時間になるでしょうし、
逆に非多項式時間であっても要素数が少なければ瞬時ということもありえます。
ですから、瞬時に解いたのは、単に計算が速かっただけかもしれません。
そもそもテューリングマシン（と等価なシステム）において、ＮＰ問題が
多項式時間で解けないということ自体まだ証明されていなかったはずですから、
瞬時に解けたとしても、実は原理的に多項式時間で解けることになっていたと
いう可能性だって残されています。
いずれにせよ、量子コンピュータの概念とは関係のない話だと思います。
量子コンピュータといえども、テューリングマシンと等価なシステムである
ことに変わりはありません。

補足

補足です。
つまり・・・要素数を増やしていったときに、その人がどのぐらいの時間で
その問題を解けるのかをちゃんと観測するんです。

>多項式時間で解けないということ自体まだ証明されていなかったはずですから、

確かにそうでした。
一応、NP問題は「真に困難である」ということが証明されたという前提で
ご回答ください。

>量子コンピュータといえども、テューリングマシンと等価なシステムである
ことに変わりはありません。

この問題に即して言うと、
もしも、そういう人が存在して、しかもNP問題は「真に困難である」のなら、
脳はチューリングマシンでない、と言い切ってしまってよいのでしょうか？