言語に制御構造と変数があるが、配列、リスト、メモリ アクセスと割り当てなどをサポートしていない場合、その言語はチューリング完全でありえますか?
作成できる変数の量に制限がない場合はarray_1、 、array_2、 ...などの変数を作成して配列をシミュレートarray_6000し、それらを手動でループして、何らかの方法で複雑なデータ構造と再帰を作成できますか?
編集：名前操作で変数にアクセスできない場合でも（array_10+i許可されていません）？
1033 次
2 に答える
17
そうです。私が今まで見た中で最も最小限のチューリング完全言語の 1 つであるLambda Calculusを見てください。基本的に、ラムダ (関数リテラル) しかありません。代入も宣言もデータ構造もありません。それはすべて非常にスリムになっています。
ただし、関数を連鎖させることで、リストのような線形データ構造をシミュレートできます。かなり冗長になりますが、確かに可能であり、一連の連続した名前の変数を持つよりもはるかに優れています。
一般的に言えば、言語がチューリング完全であるかどうかは、その言語が配列を持っているかどうかとは何の関係もありません。SML や Haskell などの関数型言語には、ラムダ計算と同様に配列がありませんが、これらは実際に便利な言語です! 言語が「チューリング完全」であると言うのは、その言語で表現できないチューリング計算可能関数が存在しないという別の言い方です。これは驚くほど緩い修飾であり、完全に非実用的な多くの言語 (ラムダ計算など) を許可します。
于 2009-09-07T16:00:21.483 に答える
5
「変数」の概念すら持たないチューリング完全言語はたくさんあります！メモリアクセスと割り当ては実装の詳細であるため、完全に無関係です。チューリングマシンとチューリング完全性は非常に理論的な概念であり、物事を証明するのに役立ちますが、実際のハードウェアの現実から完全に切り離されていることを理解する必要があります。
ポール・グレアムは、コンピューター言語の歴史について、長いが非常に興味深いエッセイを書き、コンピューター言語の2つの非常に異なる主な伝統について説明しています。
- Lisp、Schemeなど-理論的な考察から導き出された、非常にシンプルでありながら概念的に強力な言語ですが、実装が簡単で効率的なものを完全に無視しているため、長い間実用的ではありません
- アセンブラー、FORTRAN、C、およびほとんどすべての「主流」言語-ハードウェアが実行できることから多かれ少なかれ直接派生し、実装が簡単で、効率的ですが、表現力の点で（古い！）Lispファミリーよりも長い間劣っています。
あなたは2番目の伝統しか知らないように聞こえますが、チューリング完全性は最初の伝統と同じ原則に由来する概念であり、それらの原則を知らなければほとんど意味がありません。
于 2009-09-07T16:25:59.577 に答える