5

チューリング完全なプログラミング言語(すでに証明済み)を作成したので、そのためのクワインを書くことができるはずですよね?

chrしかし、私が知っているすべてのクワインは、ソースコードを文字列に格納してから、とのようなものを使用してその中の特殊文字を置き換えordます。

私の言語には次のものしかありません

  • 基本的な算術
  • Int型とstring型
  • 変数
  • ==演算子
  • 条件付きgoto

実際の文字列操作が利用できないため、どのようにクインを書くことができるのかわかりません。定数文字列しか出力できません。それでも、100%チューリング完全です。

4

3 に答える 3

3

整数がある場合は、文字列をエンコードまたはデコードできます(A = 1、B = 2などの単純なスキームで十分です)。定数文字列を比較するか、intを比較できる必要があるだけです。したがって、根本的な問題はないようです。

あなたは数字を扱い、次のようなことを書きます

if (n == 1) print "A"
if (n == 2) print "B"
...

いくつかの実際的な問題がある可能性があります。文字列の場合は、文字が含まれているのではなく、非常に大きな数に相当します。ここで必要なのは、無制限の精度の数値、固定サイズの数値のある種の配列、またはその他の大きなデータ構造にアクセスできるようにすることです。数字の配列は、文字列ができることをあなたに代わって行います。ただし、言語がチューリング完全である場合は、メモリの大きなチャンクに簡単にアクセスする方法が必要です。

32ビットテープに制限されたチューリング完全言語(または32ビットの異なるメモリスペースごとに新しい名前を付ける必要がある場合)は残念ですが、そのような制限のあるクワインを書くことができるかどうかはわかりません。ちなみに、配列や同様の構造がない場合、言語がチューリング完全であることをどのように証明したかを知ることは興味深いでしょう。私が通常使用する一般的な方法は、私の言語を使用してチューリングマシンを実装することです。しかし、これを行うには、バンドをシミュレートするためのある種のアレイが必要です。

この種のエンコーディングは、基本的にゲーデルが不完全の定理で行ったことであり、論理式を整数としてエンコードする方法を見つけて、それを推論します。

構文の要素をさらに指定すると、それを実行することもできます(関数がなく、gotoのみの場合、それも問題になりますが、シミュレートすることもできます)。基本的な問題は、エンコードされたソースコードを「圧縮」する方法を見つけなければならないことです。長い文字列定数を使用できる場合は、おそらく役立つでしょう。

于 2010-04-11T19:00:47.990 に答える
3

あなたの言語がチューリング完全であり、1つのクワインがある場合、それらの数は無限にある可能性があります。それらの一部を作成する方法は次のとおりです。

  1. あなたの言語でBrainfuck(または他のいくつかの単純なチューリング完全言語)インタープリターを実装します。ソースX1<brainfuck source>Y1が実行時にBrainfuckプログラムを解釈するようにプログラムを作成します。
  2. 任意の言語でアルゴリズムstring f(string a, string b)を記述し、任意の言語を指定するab、Brainfuckプログラムを出力します。このプログラムは、実行時に文字列a、Brainfuckソースコード全体、次に文字列を出力しますb。これを行うために、既存のBrainfuckクワインを適応させることができます。
  3. 結果のBrainfuckプログラムを計算f(X1, Y1)し、1からプログラムに埋め込みます。

ステップ1は最も難しいですが、チューリング完全であることを証明する最も簡単な方法の1つは、チューリング完全であることがすでに証明されている別の言語のインタープリターを実装することであるため、すでに実行している可能性があります。

ステップ2はすでに可能であることが証明されており、プログラム言語に依存しません。

ステップ3は簡単な計算です。

于 2010-04-11T19:03:36.203 に答える
0

どうやら、あなたのプログラミング言語のプログラムは文字列です。クワインの出力はプログラムです。

したがって、クインの出力は文字列です。文字列操作がない場合、それを書くことは不可能です。

プログラムを(単純なヒューメン読み取り可能なテキストエンコーディングではなく)数値でエンコードするか、文字列操作を実装する必要があります。

于 2010-04-11T19:17:52.037 に答える