ある言語で X を実行できる場合、別の言語で Y を実行できると言う人をよく見かけます。これは、チューリング完全な議論です。したがって、あなたはしばしば（通常は卑劣なコメントで）「yもチューリング完全であるため、yでtを実行できることを確認してください。
私はずっと前に CS 理論を学びましたが、これが常に正しいとは思いません。なぜなら、Turing が並行処理のどこに適合するのかがわからないからです。たとえば、適切なハードウェアを使用して正確に同時に実行できるプログラミング言語がありますが、それが不可能なプログラミング言語もあります。
これはおそらく言語よりもハードウェア/ドライバーの問題であることは理解していますが、並行性がチューリング完全であることをどのように変更するのか、またはどのように変更するのか興味がありますか? あなたはチューリング完全を超えることができますか?
編集：私がこの質問をした最初の理由は、主に量子コンピューティングによるものでし た。受け入れられた答えはこれを言っていませんが、量子コンピューティングは（表向きは） turing のサブセットです。
これは多くの人にとって紛らわしいトピックです。あなたは一人じゃない。問題は、ここでの「可能性」の定義が 2 つあるということです。「可能」の定義の 1 つは、それをどのように使用しているかです。同時実行が可能か、その言語を使用して巨大なロボットを操作できるか、コンピューターにイチゴを食べさせることが可能かなどです。これは素人の定義です。 「可能」の。
チューリングの完全性は、上記の意味での可能性とは何の関係もありません。確かに、同時実行はどこでも可能というわけではありません。これは、(少なくとも一部の同時実行の定義では) 言語が 2 つ以上の異なるプロセッサで同時に実行できるコードを生成できる必要があるためです。したがって、単一のプロセッサで実行されるコードにしかコンパイルできない言語は、同時実行ができません。ただし、それでもチューリング完全である可能性があります。
チューリングの完全性は、十分なメモリと実行時間が与えられたマシンで計算できる数学関数の種類と関係があります。数学関数を評価する目的で、単一のプロセッサは、1 つのプロセッサのロジックを次々に実行することによって複数のプロセッサをエミュレートできるため、複数のプロセッサが実行できるすべてのことを行うことができます。任意のデバイスで計算できるすべての数学関数は、チューリング マシンを使用して計算可能であるという (証明されておらず、証明できないが、反証可能である) 声明は、いわゆるチャーチ チューリング テーゼです。
任意のチューリング マシンをエミュレートできることを証明できるプログラミング言語は、チューリング完全と呼ばれます。これをChurch-Turingの論文と組み合わせると、プログラミング言語は、十分な時間とメモリがあれば、どのデバイスでも評価できるあらゆるタイプの数学関数を評価できることを意味します。ほとんどの言語は、動的配列を割り当て、ループと if ステートメント、およびいくつかの基本的なデータ操作を使用する能力のみを必要とするため、チューリング完全です。
逆に言うと、チューリング マシンは現在知られている任意のプロセッサをエミュレートするように構築でき、プログラミング言語はプロセッサを使用して行うことを行うため、現在のプログラミング言語はチューリング マシンよりも表現力が高くありません。したがって、数学関数の計算は、すべての一般的なプログラミング言語で等しく可能です。ある関数で計算可能な関数は、別の関数でも計算できます。これはパフォーマンスについては何も言いません- 並行性は本質的にパフォーマンスの最適化です。
はいといいえ。魔法とは対照的に、チューリングマシンが実行できることを実行でき、依然として計算と呼ばれる既知の計算モデルはありません¹。したがって、その意味で、チューリングの完全性を超えるものはありません。
一方で、「間接的な層を加えれば解決できない問題はない」という言葉はよく耳にするかもしれません。そのため、チューリング マシンに直接マッピングされる計算モデルと、一定レベルの間接性を必要とする計算モデルを区別する必要があるかもしれません。「間接的なレベルを追加する」ということは、一般的に正確な数学的概念ではありませんが、多くの特定のケースでは、間接的なレベルを観察できます。多くの場合、計算のパラダイムがチューリング計算可能であることを証明する最も簡単な方法は、チューリング マシンでそのパラダイムのインタープリターを作成することです。これはまさに間接的なレベルです。
それでは、並行性をモデル化することの意味を見てみましょう。あなたは「物事を正確に同時に実行する」能力について言及しています。これは、 parallelismと呼ばれる特定の種類の同時実行であり、同時実行に関する限り、非常に制限されたモデルです。並行性の世界は、これよりもはるかにワイルドです。それにもかかわらず、並列処理は、チューリング マシンでモデル化されたときに、何らかの形式の間接化を必要とするものを既に許可しています。
次の問題を考えてみましょう: コンピュータ プログラム A と B (ユニバーサル チューリング マシンのテープに渡された) が与えられた場合、両方を実行し、どちらかのプログラムの結果を返します。A と B の両方が非終了でない限り、プログラムは終了する必要があります。純粋にシーケンシャルな世界では、A を実行して結果を返すことができます。または、B を実行して結果を返すこともできます。しかし、A を実行することから始めて、B が終了している間に非終了プログラムになった場合、その実行戦略では問題は解決しません。同様に、B を実行することから開始した場合、A が終了しても B が終了しない可能性があるため、実行戦略では問題が解決されません。
A と B のどちらが終了するかは決定できないため、どちらを最初に実行するかを決定することはできません。ただし、チューリング マシンを変更してプログラムを並列実行する非常に簡単な方法があります。A と B を別々のテープに置き、オートマトンを複製し、2 つのうちの 1 つが終了するまで各プログラムの 1 つのステップを実行します。このレベルの処理を追加することで、並列実行の問題を解決できます。
この問題を解決するには、モデルを少し変更するだけで済みます (デュアル テープ チューリング マシンをシングル テープ マシンでモデル化するのは簡単です)。それにもかかわらず、これは [ラムダ計算](http://en.wikipedia.org/wiki/ラムダ計算) の重要な例であり、別の重要な計算モデルであるため、言及します。2 つのラムダ項を、そのうちの 1 つが正規形に達する (終了する) まで並列に縮約 (評価) する操作は、プロトキンの並列またはと呼ばれます。並列 or を実装するラムダ項 (ラムダ計算プログラム) を記述できないことが知られています。したがって、ラムダ計算は「本質的にシーケンシャル」であると言われています。
ここでラムダ計算に言及する理由は、ほとんどのプログラミング言語がプログラミング マシンよりもラムダ計算に近いからです。そのため、プログラマーとして、チューリング マシンからの洞察よりもラムダ計算からの洞察の方が重要な場合がよくあります。並列またはの例は、言語² に並行性を追加することで、元の言語では利用できない可能性を開くことができることを示しています。
チューリング マシンと本質的に同じトリックを使用して、シーケンシャル言語に同時実行性を追加することができます。つまり、スレッド A の小さな断片を実行し、次にスレッド B の小さな断片を実行する、というようにします。実際、言語でそれを行わなくても、通常はオペレーティング システムのカーネルが代わりにそれを行うことができます。厳密に言えば、これはスレッドの同時実行を提供しますが、それでも単一のプロセッサを使用します。
理論モデルとして、この種のスレッド化された実行には、決定論的であるという制限があります。. 実際、チューリング マシンで直接モデル化できるシステムはすべて決定論的です。並行システムを扱う場合、非決定論的なプログラムを記述できることが重要になることがよくあります。多くの場合、計算の複数のスレッドがインターリーブされる正確な順序は関係ありません。したがって、2 つのプログラムは、本質的に同じ計算を行うが、順序がわずかに異なる場合、同等です。単一プログラムの実行ではなく、可能なインターリーブのセットを調べることで、逐次計算のモデルから並行計算のモデルを作成できますが、管理が難しいレベルの間接計算が追加されます。したがって、並行性のほとんどのモデルは、システムに非決定性を焼き付けます。そんなことしたら、もうチューリングマシンでは走れません。
¹
この点で、思考 (私たちの脳内で起こっていること) は、それがどのように行われるのか分からず、科学的に理解されていないという意味で、依然として魔法です. 再現方法を知っているものはすべて (生物学的な意味ではありません!)、チューリング計算可能です。
²
ここで、言語には自分で定義できないすべてが含まれていることに注意してください。この意味で、標準ライブラリは「言語」の一部です。