2

この質問に触発された

無限のメモリと無制限のCPUパワーを備えた魔法のチューリングマシンがあるとします。

これがどのように可能であるかについて想像力を働かせてください。たとえば、ある種の超空間連続体を使用して、必要なだけ自動的に並列化し、時間計算量や数に関係なく、計算可能な質問に対する答えを計算できるようにします。 1秒で実際の「論理ステップ」の。

ただし、計算可能な質問には1秒でしか答えられません...したがって、私は「不可能な」マシンを想定していません（少なくとも私はそうは思いません）...たとえば、このマシンはまだ答えることができません停止問題を解決します。

そのようなマシンのプログラミング言語はどのようになりますか？私が知っているすべてのプログラミング言語は、現在「アルゴリズムの複雑さ」にいくらかの譲歩をしなければなりません...しかし、その制約を取り除いて、私たちが気にするのはプログラミング言語の「表現力」だけだと思います。つまり、「計算可能な質問」を簡潔に表現する能力...

とにかく、うまくいけば興味深い議論のために、コミュニティウィキとしてそれを開いてください...

4

11 に答える 11

4 
SendMessage travelingSalesman "Just buy a ticket to the same city twice already. You'll spend much more money trying to solve this than you'll save by visiting Austin twice."
SendMessage travelingSalesman "Wait, they built what kind of computer? Nevermind."
于 2009-05-28T11:38:58.567 に答える
4

これは実際には論理的ではありません。物事にO（1）時間がかかる場合、量子コンピューターであっても、n回行うとO（n）時間がかかります。「すべて」にO（1）時間がかかることは不可能です。

例：あなたがリンクした質問に対する受け入れられた回答で言及されているグローバーのアルゴリズムは、n個のアイテムのデータベースで要素を見つけるのにO（n ^ 1/2）時間を要します。そしてそれはO（1）ではありません。

于 2009-05-28T11:39:34.073 に答える
3

メモリの量、メモリの速度、またはプロセッサの速度は、アルゴリズムの時間と空間の複雑さを定義するものではありません。基本的な数学はそれを行います。すべてがO（1）で計算できるかどうかをプログラミング言語がどのように見えるかを尋ねるのは、円周率が3で、すべての平方根の結果が整数である場合に電卓がどのように見えるかを尋ねるようなものです。それは本当に不可能であり、そうでなければ、あまり役に立たないでしょう。

さて、無限のプロセスパワーと無限のメモリで何をするかを自問することは、有用な演習になる可能性があります。アルゴリズムの複雑さに対処する必要がありますが、おそらくどういうわけか別の方法で作業するでしょう。そのために私は百年の言語をお勧めします。

于 2009-05-28T11:51:04.907 に答える
2

それはおそらくhaskellっぽい言語かもしれません。正直なところ、コーディングするのは夢です。型、クラス、関数の「法則」をプログラムしてから、それらを解き放ちます。それは信じられないほど楽しく、強力であり、非常に簡潔でエレガントなコードを書くことができます。それは芸術のようなものです。

于 2009-05-28T11:36:40.040 に答える
2

停止問題が計算可能でなくても、「Mより小さいサイズのすべての可能な入力でNステップ以内にこの停止を行うか」ということに注意してください。

そのため、プログラミング言語は純粋に仕様になります。関数の事前条件と事後条件を正確に指定するだけで、コンパイラーは仕様を実装する可能な限り最速のコードを実装できます。

また、これは非常に迅速に特異点を引き起こします。AIの構築は、ほぼ無限の計算を実行できればはるかに簡単になります。AIを効率的に計算できるようになると、「10億年かけてプログラムを考えたら、プログラムをどのように改善できるでしょうか。 「...

于 2009-05-29T21:29:22.680 に答える
1

たぶん、それは「実際の」コードというよりも擬似コードのように見えるでしょう。結局のところ、どちらの方法でも十分に高速になるため、実装の詳細について心配する必要はありません。

于 2009-05-28T11:33:45.613 に答える
1

あなたはO（1）を過小評価しています。これは、問題を計算する時間がこのCに制限されるような定数C>0が存在することを意味します。

無視するのは、Cの実際の値は大きくなる可能性があり、アルゴリズムごとに異なる可能性がある（そしてほとんどの場合は異なる）ということです。両方ともO（1）を使用する2つのアルゴリズム（またはコンピューター-関係ありません）がある場合がありますが、一方のCはもう一方のCの10億倍大きい場合があります。後者の場合、時間の点ではるかに遅く、おそらく非常に遅くなります。

于 2009-05-28T11:36:56.997 に答える
1

スケーラビリティはもはや問題ではありません。AIは私たちよりもはるかに賢いでしょう。私たちはもはやプログラムする必要はなく、代わりにAIは私たちが自分たちでそれらを実現する前に私たちの意図を理解するでしょう。

于 2009-05-28T11:39:23.450 に答える
1

SQLはそのような言語です-あなたはデータの一部を要求し、それを取得します。dbの実装の詳細について心配する必要がない場合は、プログラミングするのも楽しいかもしれません。

于 2009-05-28T11:49:16.143 に答える
0

すべてが1秒で完了する場合、ほとんどの言語は最終的に次のようになります。私はそれをDWIM理論と呼びます（私が意味する理論を実行してください）。

Just do what I said (without any bugs this time)

なぜなら、1秒ですべてを計算できるマシンを開発した場合、おそらくその段階でマインドコントロールが可能になり、少なくとも人工知能が必要になるからです。

于 2010-08-24T22:18:01.247 に答える
-1

新しい言語が登場するかどうかはわかりませんが（私は物理学者であり、コンピューター科学者ではありません）、それでもPythonでプログラムを作成します。

于 2010-12-16T06:57:34.933 に答える