33

私の言語がチューリング完全である場合、それ自体を出力するプログラムを作成することが100%可能かどうかを知りたかっただけです(もちろん、ファイル読み取り機能は使用しません)

したがって、出力、変数、条件、および goto (はい、goto) など、完全なチューリングを行うために本当に必要なものが言語にある場合 (Brainf*ck コードをそれに変換することで証明します)、試してみることができますか?その中にクワインを書いていますか?

チューリングマシンがあらゆる計算タスクを実行できるというチューリングの法則にクワインが直接適合するかどうかわからないため、これも尋ねています。私は知りたいだけなので、それが不可能かもしれないことを知らずに何年もやろうとはしません.

4

4 に答える 4

32

チューリング完全であり、任意の文字列を出力できるプログラミング言語 (プログラムとしての文字列の計算可能な関数 — これは、存在するすべてのプログラミング言語で満たされる技術的条件です) はクワイン プログラムを持ちます (そして、実際、無限に多くのクワイン プログラムと多くの同様の好奇心) が不動点定理によって次のように示されます。

こちらをご覧ください

于 2010-04-02T17:15:39.857 に答える
5

私は数ヶ月前にこの問題に遭遇しました。

クワインを書くことは必ずしも言語がチューリング完全であることを証明するわけではありませんが、それは強力な提案です;)チューリング完全性に関する限り、あなたが(あなたが言ったように)あなたの言語から別のチューリング完全への有効な翻訳を提供できれば言語の場合、あなたの言語はチューリング完全です。

そうは言っても、文字列を出力できるチューリング完全である言語はすべて、クワインを生成できるはずです。また、ウィキペディアから:

クインは、実行環境を関数と見なした場合の実行環境の固定点です。クワインは、クリーネの再帰定理の直接の結果として、計算可能な文字列を出力する機能を持つすべてのプログラミング言語で可能です。娯楽のために、プログラマーは、与えられたプログラミング言語で可能な限り短いクワインを開発しようとすることがあります。

于 2010-04-02T17:22:12.367 に答える
4

表現内のすべてのシンボルを出力できないプログラミング言語を使用することは可能です。たとえば、I/O はアラビア語の言語キーワードを持つ 7 ビット ASCII 文字に制限される場合があります。それは私が考えることができる唯一の例外です。

于 2010-04-02T19:17:03.550 に答える