言語は完全にチューリングできますが、他の方法では不完全ですか？

StackOverflow https://stackoverflow.com/questions/813657

質問

たとえば、オペレーティングシステムを記述する際に、完全な言語を使用することでは達成できない特定のものがありますか？

役に立ちましたか？

解決

いいえ。または、少なくとも Church Turing Thesis 。

ただし、チューリングは完全ですが、特定のプログラムを書くのは非常に苦痛な言語があります。つまり、FORTRANでの文字列処理、COBOLでの数値プログラミング、sedでの整数演算、実質的にx86アセンブラーでのすべて。

そして、もちろん brainfuck があります。

他のヒント

はい、ハードウェアを直接操作できない言語を使用できます。たとえば、Bourneシェルを使用してオペレーティングシステムを記述することは困難です。しかし、これらの制限はあなたが思うよりも少ないです。オペレーティングシステムは、標準ML、Scheme、さらには Haskell ！

で記述されています。

チューリング完全は、完全性の最も一般的な正式な定義です。特定のアプリケーションに必要な言語機能がありますが、これらは正式な定義に適合しません。

たとえば、グラフィックス機能、バックグラウンドプロセスを生成する機能、状態を維持する機能、およびネットワークに接続する機能はすべて便利な機能ですが、言語のチューリング完全性とは関係ありません。したがって、Google App Engine上のPythonまたはサンドボックスで実行されるJavaアプレットは、チューリング完全です。

多くの場合、これらのタイプの機能はコア言語ではなくライブラリによって提供されることに気付くでしょう。

語用論について言えば、確かに...ファイルを読み書きできないプログラミング言語を想像できます（たとえば、整数の関数を計算できるがそれだけです）... 言語がトースターを操作できないからといって、チューリング完全ではないというわけではありませんが、できないことはあるということです。 。

コンテキストに応じて、「言語で何かを達成する」人によって違うことを意味します。チューリングはそれらの人々の一人であり、彼は「完全」によって彼が意味するものを非常に正確に定義しました。

言語（または理論的なマシン）がチューリング完全である場合、それが実行できないチューリング計算はありません。これは、言語が全能であることを意味するのではなく、金額が得意であることを意味します。多くの「もの」がありますチューリング計算ではないため、チューリング完全なコンピューターでは実行できない場合があります。

＆quot;オペレーティングシステムであること＆quot;チューリング計算ではありません。オペレーティングシステムになるには、単なる計算以上のことを行う必要があります。また、ハードウェアを操作する必要があります。

チューリングの完全な言語と、入力や時間の適切な概念など、必要なすべてのハードウェア操作を実行するための一連の操作とともに、OSを作成できます。または、OSを記述することは可能です。個人的にできるかどうかは、言語がいかに簡単に動作するか、そして結果のプログラムが実際に動作させたいデバイスのメモリに適合して実行されるかなど、チューリング定義が無視する物理的制限に依存します。現実的な時間で実行します。

ただし、実用的な制限は無視します。はい、ハードウェアを駆動するのに十分な操作が言語にある場合、チューリング完全言語でOSを記述できます。言語をライブラリと区別する実用的なCSアプローチを採用したい場合は、「ライブラリ呼び出し」。彼のコンピューティングモデルには「呼び出し」の概念がないため、Turingはそのような区別をしませんでした。とにかく。また、ブートストラップの問題も解決する必要があります。ハードウェアは、記述している言語を直接実行する必要があります。または、ハードウェアが実行する言語へのコンパイラーが必要です。ハードウェアが実行されます。繰り返しになりますが、Turingは計算モデルが抽象ハードウェアを使用するため、これをすべて無視しますが、OSの記述はすべてハードウェアに関するものです。

英語（CompSciSpeakではなく）では、言語は「特定の機能を欠いている」と言うのが一般的であり、したがって、おそらく「完全ではない」と言えます。それらを持っている別の言語と比較して。 Cでクロージャを実装することが可能であると反論するかもしれません。たとえば、LispインタプリタであるCプログラムを記述し、その中にLispプログラムを文字列として埋め込むことができます。 Voila、Cでのクロージャ。ただし、これは、「Cにクロージャがあればいいのに」と言う場合、ほとんどの人が求めていることではありません。すべての言語にクロージャーが必要だと思うなら、Cは不完全です。すべての言語に構造化プログラミングが必要だと思われる場合、ARMアセンブラーは不完全です。オブジェクトにメソッドを動的に追加できると思われる場合、「AddMethod」でC ++クラスを記述することは完全に可能ですが、C ++は不完全です。および＆quot; CallMethodByName＆quot;メソッドを作成し、そこから独自のメソッド呼び出し規約を作成します。等々。

Turingは言語がこれらの便利さを必要としないと考えています。それらは実行できる計算に影響を与えず、特定のプログラムを書くことがどれだけ簡単かを左右します。チューリング完全性の概念は、プログラムがどのように見えるか、またはそれらがどのように構成されているか、何を出力するかについては何も言うことはありません。したがって、これらの言語は完全なチューリングですが、プログラマーの観点からは、これらの言語では達成できない特定のことがあります。

Languageは、サブルーチン、再帰、カスタムデータ型、ループ、クラスの定義、gotoなどのようなことを行うこともできないこともできます。このような言語機能のセットは、それを完了させるかどうかを決定します。たとえば、ループ、goto、およびサブルーチンがない場合、言語は不完全です。循環操作を実行することはできません。言語の完全性は非常に理論的かつ科学的なことです。たとえば、あなたの言語が関数を再帰的に呼び出すことを許可していないが、関数ポインタを許可している場合よりも証明されています-再帰をシミュレートすることができます、すなわちyコンビネーターで。

ファイルやハードウェアを扱うようなものは、多くの場合、言語の一部ではありません。プログラミングタスクを実行するには、言語以上のものが必要です。プログラムが動作する環境が必要です。x86では、言語として＆quot; int＆quot;の指示があります。パラメータは1つですが、「int 21h」を実行するときに特定の操作を実行するのはOS次第です。

Languageは、環境と通信して完全なものにするための何らかの方法を必要とするだけです-それで動作するのは環境次第です。 x86 asm＆quot; mov ax、bx＆quot;に書き込むことは有効です。ただし、この操作を実行するのはCPUの役割です。

他の方法で不完全であること-簡単に、完全性の独自のバージョンを定義してください。つまり、クラスベースのOOPなしで作業するのは嫌いなので、クラスベースのOOPをサポートする言語機能がない場合、言語はフェルドマン完全ではないことを定義しましょう。それでは、CとJavascriptはF完全ではありません。それらの言語で何でもでき、クラスベースのOOPをある程度シミュレートすることもできます。

OSについて-命令を実行するプロセッサと、言語をCPU命令に変換するコンパイラが必要です。コンパイラが何かをマシンコードに変換することを想像できます。同様に、以下は有効なJSコードです

for(var i=0;i<10;i++){
 mov("ax",i);
 int(0x21);
}

それをマシンコードにコンパイルするのはそれほど難しくないはずです。

現代の世界では、言語だけでなく、プラットフォーム、標準および非標準ライブラリ、文献、コミュニティ、サポートなども選択します。これらすべてのことは、特定のことを行う能力に影響を与えます。 「十分に完全」ではない可能性がありますあなたの仕事のために。しかし、C ++コードをJavaアプレットにコンパイルできない場合でも、C ++言語が不完全であることを意味しません。 c ++コードをJVMでロードできるものに変換するコンパイラーが存在しないだけです。

必要に応じて、＆quot; OpenFile、PingNetworkHost、DownloadMpeg4FileOverHttpsAndPlayBackwards＆quot;などの言語機能を使用して言語を設計できます。しかし、言語にそれらがない場合でも、他の言語機能と環境サポートを使用して実装できます。そのような機能がなくても、言語が不完全になることはありません。言語がCに似ているが、goto演算子、loop演算子（for、while、do while）および関数がない場合、循環プログラムを書くことはできず、環境とライブラリは役に立ちません。

答えは最も明確なはいです。チューリング完全性とは、チューリング完全言語を使用して計算可能な関数を計算できることを意味するだけです。一つには、計算の複雑さについて何も言わない。

通常、多項式時間アルゴリズムは他のチューリング完全言語の多項式時間アルゴリズムとして表現できると期待できますが、それだけです。特に、チューリングの完全性が唯一の焦点である場合、リアルタイム要件（ソフトまたはハード）はすべてウィンドウの外に出ます。

もう1つの重要なことは言語の表現力です。これは主に主観的な性質ですが、プログラムはJavaなどよりもマシンコードで書くのがはるかに難しいことを理解できます。

オペレーティングシステムに関しては、ハードウェアへのインターフェイスは必須ですが、そのようなユーティリティにはどの言語でも適合できます。

[編集] もう1つ付け加えると、プログラミング言語の実際の実装は、有限のコンピューティングマシンの性質上、チューリング完全ではありません。 Church-Turingの論文は、関連する独創的な発見（停止する問題など）とともに、コンピューティングの理解の基礎となりますが、実用的なコンピューティングの世界に出会うことはめったにありません。

不完全なユーザビリティ：）

話が言語についての場合、通常、言語はいくつかの非常に単純なマシンで実行されると想定されます。そのため、ファイルの読み取りやネットワークへのアクセスという概念は、通常、言語の能力に関しては考慮されていません。

計算可能性理論でよく使用されるさまざまなクラスの言語があります（それぞれほぼ無限の修正が加えられています）

  1. 有限オートマトン。これは最も単純なクラスのマシンであり、最小クラスの言語を認識することができます。これは、たまたま正規表現が認識できる exact 言語です。文字列が2つの「a」で始まり、dで終わるかどうか。文字列に括弧のバランスの取れたセットfxが含まれているかどうかを認識するために使用することはできません。
  2. オートマトンを押し下げます。これは本質的に、スタックを持つ有限オートマトンの拡張です。有限状態マシンとは異なり、特定の文字列にバランスの取れた括弧のセットが含まれているかどうかを判断するために使用できます。オートマトンをプッシュダウンできる言語は、コンテキストフリーの文法を使用して記述できるセットよりも正確にセットであり、ソースコードの解析によく使用されます。
  3. チューリングマシン。これらはここでは最も強力なクラスのマシンですが、すべての質問に答えるために使用できるという意味ではありません。彼らは質問に答えることができません。この文字列は永遠に実行されるチューリングマシンを説明していますか？実際、チューリングマシンは、チューリングマシンの自明でない特性については何も語ることができません（ライス定理）。

したがって、はい、チューリングマシンには制限があり、チューリングマシンではできないことを実行できるマシンのクラスがありますが、それらは理論的には存在し、実際には新しいものです（すべての確率で）。

チューリング（または正規表現、プッシュダウンオートマトン）以外の完全性の定義は、言語に関連するとは思いません。ただし、この完全性は、数値または記号の計算機能に関してのみです。

あなたが言及していることは、言語よりもランタイムと環境の機能であるように思えます。重要な違いがあり、完全性の正式な概念は通常、言語自体にのみ適用されます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top