7

すべてのチューリング完全言語で、作業を作成することは可能ですか?

  • 最初に他の言語で書かれたインタープリターで実行され、次に独自のソースコードをコンパイルするコンパイラー自体? (ブートストラップ)

  • バイナリを出力する標準準拠の C++ コンパイラ。

  • 正規表現パーサーと評価者?

  • World of Warcraft のクローン？(たとえば、言語が必要な API バインディングを取得し、OpenGL と WoW ソース コードが利用可能であると仮定します)

（ここではすべて理論上のものです）

Brainf*ck を言語の例として考えてみましょう。

4

8 に答える 8

8

すべてのチューリング完全言語で、機能するものを作成することは可能ですか...

1 つのチューリング完全言語がそれを実行できる場合、すべての言語で実行できます。この意味で、それらはすべて等しく「強力」です。あなたが説明したものはすべて、少なくとも 1 つのチューリング完全言語で既に存在するため、これらのプログラムはいずれも他のチューリング完全言語で記述できます。

ただし、何かが可能だからといって、それが簡単である、または実現可能であるとは限りません。これは非常に重要な違いであり、さまざまなプログラミング言語が存在する理由の核心です。彼らは特定の種類のソフトウェアを作るのが得意というわけではありません。

于 2010-04-08T15:19:15.590 に答える
8

Turing-Complete は計算機能のみを表現し、 I/O機能については何もありません!

于 2010-04-08T18:38:28.377 に答える
5

いいえ、チューリング完全性はI/Oやハードウェアとは何の関係もありません。ただし、変数（または「メモリテープ」）を使用して、I / O、ハードウェアシステム、およびグラフィックシステムが存在するふりをすることができます。BFでは、最初の2つのセル（x、y）を「ふりをした」画面解像度に使用し、次に別のx x yセルを画面上のすべてのピクセルに使用し、次のセル（n）を「ふりをした」ファイルシステムサイズに使用できます。次に、ファイルシステムコンテンツの次のn個のセル...

于 2010-04-09T01:37:35.440 に答える
2

はい、もちろん、それらすべてです。結局のところ、これが「チューリング完全」の意味です。つまり、計算可能なすべてのことを計算できます。

于 2010-04-08T15:16:40.213 に答える
1

チューリング完全であるために本当に必要なのは、簡単な計算ができること、いくつかの変数があり、while ループを実行できることだけです。または任意の数の同等のもの。実際のプログラムを実行したい場合は、もう少し (特にシステムコール) が必要であり、効率についても心配する必要があります (turing マシンは非常に遅くなる可能性があります...) 理論的には、turing と同等のシステム間に違いはありませんが、実際にはがある。

誰かが BF で WoW クライアントをやったら、私はとても感銘を受けます!

于 2010-04-08T15:25:52.933 に答える
0

1 つの Turing-Complete 言語で実装できるアルゴリズムは、他の言語でも実装できます。あなたの質問は、問題の言語を介して利用できるようにする必要があるオペレーティング システム サービスと API に関係しています。

要するに、形式言語の観点から言えば、上記のすべてに対する答えはイエスです。

于 2010-04-08T15:18:14.710 に答える
0

理論上、はい。しかし、もっと興味深い質問は、特定の「難解な」プログラミング言語でそれが実際に可能かどうかです。

于 2010-04-08T15:19:16.070 に答える
-2

すべての Turing-Complete 言語は、同じ関数セットを計算できます。したがって、チューリング完全言語は、他のチューリング完全言語で計算されるため、あなたが書いたことをすべて行うことができます。

于 2010-04-08T15:19:47.530 に答える