私のプログラミング言語では Quine はどのように見えるでしょうか?

Question

私はチューリング完全プログラミング言語を作成しました (すでに証明されています)。 クワイン そのためですよね？

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

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

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

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

Answer 1

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

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

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

現実的にはいくつかの困難が生じる可能性があります。文字列の特徴は、文字列が含まれているということではなく、文字列が非常に大きな数値と同等であるということです。ここで必要なのは、無制限の精度の数値、またはある種の固定サイズの数値の配列、またはその他の大規模なデータ構造にアクセスできることです。数値の配列は、文字列でできることを行います。しかし、あなたの言語がチューリング完全であれば、メモリの大部分に簡単にアクセスする方法があるはずです。

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

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

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

Answer 2

あなたの言語がチューリング完全であり、クインが 1 つある場合、おそらく無限に多くのクワインが存在します。それらの一部だけを構築する方法を次に示します。

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

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

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

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

Answer 3

どうやら、あなたのプログラミング言語のプログラムは文字列です。 QUINEの出力がプログラムされます。

はしたがって、QUINEの出力は、文字列です。あなたが任意の文字列操作がない場合には、1を書くことは不可能だ。

あなたはどちらか（代わりに、シンプルな虎門で読み取り可能なテキストエンコーディングの）数字でプログラムをエンコードまたは文字列操作を実装する必要があります。