language-agnostic - ある言語がチューリング完全であっても、他の点では不完全である可能性はありますか?

Question

たとえば、オペレーティング システムを作成するときに、チューリング完全な言語では実現できない特定のことがありますか?

Answer 1

いいえ、または少なくとも教会のチューリングテーゼの反証となるものを見つけた場合。

ただし、チューリング完全であるが、特定のプログラムを作成するのが完全に面倒な言語があります。たとえば、FORTRAN での文字列処理、COBOL での数値プログラミング、sed での整数演算、x86 アセンブラーでの実質的なすべてなどです。

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

Answer 2

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

Answer 3

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

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

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

Answer 4

語用論について話しているのであれば、確かに...ファイルを読み書きする能力のないプログラミング言語を想像することができます(例えば、整数の関数を計算できる言語ですが、それだけです)... 言語ができるという理由だけで「トースターを操作しない」ということは、それがチューリング完全ではないという意味ではありませんが、それができないことがあるということを意味するので、この区別がどれほど「重要」または有用かはわかりません。

Answer 5

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

言語 (または理論上の機械) がチューリング完全である場合、実行できないチューリング計算はありません。これは、言語が全能であることを意味するのではなく、和算が得意であることを意味します。チューリング計算ではない多くの「もの」があり、そのためチューリング完全なコンピューターでは実行できない可能性があります。

「オペレーティング システムになる」は、チューリング計算ではありません。オペレーティング システムになるには、計算だけでなく、さらに多くのことを行う必要があります。また、ハードウェアを操作する必要があります。

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

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

英語 (CompSciSpeak ではなく) では、言語には「特定の機能が欠けている」と言うのが一般的であり、そのため、それらを持つ別の言語と比較して「完全ではない」と言うのはほぼ間違いありません。C でクロージャを実装することは可能であると反論する人もいるかもしれません。たとえば、Lisp インタプリタである C プログラムを書き、その中に Lisp プログラムを文字列として埋め込むことができます。出来上がり、C のクロージャ。ただし、「C にクロージャがあればいいのに」と言う場合、これはほとんどの人が求めているものではありません。すべての言語にクロージャが必要だと考えるなら、C は不完全です。すべての言語に構造化プログラミングが必要だと考える場合、ARM アセンブラーは不完全です。メソッドをオブジェクトに動的に追加できるはずだと思うなら、C++ クラスを "

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

Answer 6

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

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

言語は、環境と通信して完全になる何らかの方法が必要なだけです。それを処理するのは環境次第です。x86 asm "mov ax,bx" に書き込むことは有効ですが、この操作を実行するのは 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でロードできるものに変換するコンパイラがないだけです。

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

Answer 7

答えは間違いなくイエスです。チューリング完全性は、チューリング完全言語を使用して計算可能な関数を計算できることを意味するだけです。1 つには、計算の複雑さについては何も述べていません。

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

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

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

[編集] 私が付け加えるかもしれないもう 1 つのことは、プログラミング言語の実際の実装は、私たちの有限計算機の性質上、チューリング完全ではないということです。チャーチチューリングのテーゼは、関連する重要な発見 (停止問題など) とともに、コンピューティングを理解するための基礎を築きますが、それらが実際のコンピューティングの世界に出会うことはめったにありません。

Answer 8

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

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

Answer 9

不完全なユーザビリティ:)

Answer 10

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

計算可能性理論でよく使用されるさまざまなクラスの言語があります (それぞれにほぼ無限の変更が加えられています)。

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

そうです、チューリング マシンには制限があり、チューリング マシンではできないことを実行できるクラスのマシンがありますが、それらは理論上のみ存在し、実際にはより新しいものです。