24

私は、Ken Thompson の古典的な論文Reflections on Trusting Trustを読みました。この論文では、彼の主張の導入としてユーザーにQuineを書くよう促しています (強くお勧めします)。

quine は、入力を受け取らず、独自のソース コードのコピーを唯一の出力として生成するコンピューター プログラムです。

素朴なアプローチは、単に言いたいことです：

print "[insert this program's source here]"

しかし、これは不可能であることがすぐにわかります。Python を使用して自分で作成することになりましたが、「トリック」を説明するのにまだ問題があります。クワインが可能である理由の優れた説明を探しています。

4

2 に答える 2

14

通常のトリックはprintf、フォーマット文字列がプログラムの構造を表すように使用し、必要な再帰を取得するために文字列自体のプレースホルダーを使用することです。

http://www.nyx.net/~gthompso/quine.htmの標準 C の例は、これを非常によく示しています。

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}

編集：これを書いた後、私は少し検索を行いました：http://www.madore.org/~david/computers/quine.htmlは、クインとは何か、なぜ機能するのかについて、非常に優れた、より理論的な説明を提供します。

于 2012-01-15T20:56:43.643 に答える
3

これが私が書いたもので、 ;putcharの代わりに使用します。printfしたがって、すべての独自のエスケープコードを処理する必要があります。ただし、すべてのC実行文字セット間で100％移植可能です。

プログラムテキスト自体の継ぎ目を反映したテキスト表現の継ぎ目があり、最初の作業から最後の作業に変化することがわかります。クワインを書く秘訣は、この「こぶ」を乗り越えることです。ここでは、穴から抜け出す方法に切り替えます。オプションは、テキスト表現と言語の出力機能によって制約されます。

#include <stdio.h>

void with(char *s) {
    for (; *s; s++) switch (*s) {
    case '\n': putchar('\\'); putchar('n'); break;
    case '\\': putchar('\\'); putchar('\\'); break;
    case '\"': putchar('\\'); putchar('\"'); break;
    default: putchar(*s);
    }
}
void out(char *s) { for (; *s; s++) putchar(*s); }
int main() {
    char *a[] = {
"#include <stdio.h>\n\n",
"void with(char *s) {\n",
"    for (; *s; s++) switch (*s) {\n",
"   case '\\",
"n': putchar('\\\\'); putchar('n'); break;\n",
"   case '\\\\': putchar('\\\\'); putchar('\\\\'); break;\n",
"   case '\\\"': putchar('\\\\'); putchar('\\\"'); break;\n",
"   default: putchar(*s);\n",
"    }\n}\n",
"void out(char *s) { for (; *s; s++) putchar(*s); }\n",
"int main() {\n",
"    char *a[] = {\n",
NULL }, *b[] = {
"NULL }, **p;\n",
"    for (p = a; *p; p++) out(*p);\n",
"    for (p = a; *p; p++) {\n",
"   putchar('\\\"');\n",
"   with(*p);\n",
"   putchar('\\\"'); putchar(','); putchar('\\",
"n');\n",
"    }\n",
"    out(\"NULL }, *b[] = {\\",
"n\");\n",
"    for (p = b; *p; p++) {\n",
"   putchar('\\\"');\n",
"   with(*p);\n",
"   putchar('\\\"'); putchar(','); putchar('\\",
"n');\n",
"    }\n",
"    for (p = b; *p; p++) out(*p);\n",
"    return 0;\n",
"}\n",
NULL }, **p;
    for (p = a; *p; p++) out(*p);
    for (p = a; *p; p++) {
    putchar('\"');
    with(*p);
    putchar('\"'); putchar(','); putchar('\n');
    }
    out("NULL }, *b[] = {\n");
    for (p = b; *p; p++) {
    putchar('\"');
    with(*p);
    putchar('\"'); putchar(','); putchar('\n');
    }
    for (p = b; *p; p++) out(*p);
    return 0;
}

一般的なトリックは、テキストファイルを読み取り、数値の配列を出力するプログラムを作成して、クインをジャンプスタートすることです。次に、静的配列を使用するように変更し、新しい（静的配列）プログラムに対して最初のプログラムを実行して、プログラムを表す数値の配列を生成します。それを静的配列に挿入し、落ち着くまで再度実行すると、クワインが得られます。ただし、特定の文字セットに関連付けられています（== 100％移植可能ではありません）。上記のようなプログラム（従来のprintfハックではない）は、ASCIIまたはEBCDICでも同じように機能します（従来のprintfハックはハードコードされたASCIIが含まれているため、EBCDICでは失敗します）。

編集：

もう一度質問を注意深く（最後に）読んでみると、実際にはもっと哲学のないテクニックを探しているようです。無限後退から抜け出すための秘訣は、2つのferです。エンコードされたプログラムと拡張されたプログラムの両方を同じデータから取得する必要があります。同じデータを2つの方法で使用します。したがって、このデータは、プログラムの将来の兆候であるフレームを取り巻く部分のみを記述します。このフレーム内の画像は、オリジナルのストレートコピーです。

これは、あなたが自然に手で再帰的な描画を作成する方法です：テレビのテレビのテレビ。再帰が十分に確立されているため、ある時点で疲れて、画面上にグレアをスケッチするだけです。

編集：

クワインが可能である理由の優れた説明を探しています。

クワインの「可能性」は、19世紀と20世紀の数学的革命の深みにまで及びます。WVOクワインによる「クラシック」クワインは、一連の単語（IIRC）です。

自分自身に追加するとfalseになります

これは逆説であり、両側に刻まれたメダリオンが答えた「悲しいときは私を幸せにし、幸せなときは私を悲しくする」というダビデの要求に似ています。

同じ種類の結び目は、フレーゲ、ラッセル、ホワイトヘッド、シュカシエヴィチ、そしてもちろん、私たちの少年チューリング、チャーチ、チューなどの現代の数理論理学の先駆者によって調査されました。言葉遊びの領域からプログラムによるデモンストレーションにQuineを転置することを可能にするトリック（途中でパラドックス部分をねじることなく）は、算術演算自体を数値としてエンコードするゲーデルの方法でした。したがって、数式全体をにエンコードできます。単一の（巨大な）整数。特に、この表現のデコードを実行する数学関数は、同じ（数値）形式で表現できます。この数値（ゲーデルでエンコードされた関数）は、コードとデータの両方です。

このパワートリオ（コード、表現、データ）は、さまざまな表現に置き換えることができます。別の表現（またはバイト-> ASCII-> 16進数->整数などのチェーン）を選択することにより、コードの動作を変更し、データの外観を変更します。

于 2012-10-18T16:36:47.383 に答える