編寫奎因的「訣竅」是什麼？

我讀了Ken Thompson的經典論文Reflections on Trusting Trust，其中他提示用戶編寫Quine作爲他的論點的介紹（強烈推薦閱讀）。編寫奎因的「訣竅」是什麼？

奎因是一種計算機程序，它不接受任何輸入並生成其自己的源代碼的副本作爲唯一的輸出。

簡易方法很簡單，就是想說：

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

但一個快速認爲這是不可能的。我使用Python結束了writing one myself，但仍然無法解釋「訣竅」。 我正在尋找一個很好的解釋爲什麼奎因斯是可能的。

來源

2012-01-15 paislee

你讀到的頁面（肯·湯普森的圖靈獎演講中的那一頁）在我讀完之後就已經被刪除了：/感謝上帝，我做了一個備份...... – SasQ 2012-08-12 18:07:20

@ SasQ它仍然適用於我 – paislee 2012-08-13 19:01:35

是的，現在它也適用於我。那天我看到一個服務器消息，該對象沒有找到或類似的東西，所以我認爲他們刪除它。 – SasQ 2012-08-15 10:31:20

正常的技巧是使用printf使得格式字符串代表程序的結構，用字符串本身一個佔位符來獲得你所需要的遞歸：

標準的C例如，從http://www.nyx.net/~gthompso/quine.htm說明了這一點相當不錯：

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-15 20:56:43

下面是我寫的一個使用putchar而不是printf;因此它必須處理所有它自己的轉義碼。但它在所有C執行字符集中均爲％100。

你應該能夠看到，有一個縫在反映一個縫在程序文本本身，它從開始工作到結束工作改變了文本表示。 編寫Qu因的技巧是克服這個「駝峯」，在那裏你切換到挖掘你的方式出的洞！您的選項受到文本表示和語言輸出設施的限制。

#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; 
}

一個常見的技巧是跳躍通過編寫一個程序來讀取一個文本和輸出數字的數組開始的喹。然後修改它以使用靜態數組，然後針對新的（靜態數組）程序運行第一個程序，從而生成一個表示程序的數字數組。將它插入到靜態數組中，再次運行它直到它穩定下來，並且讓你成爲一個quine。但是，它綁定到一個特定的字符集（==不是100％便攜式）。像上面這樣的程序（而不是經典的printf黑客）將在ASCII或EBCDIC上工作（傳統的printf黑客在EBCDIC中失敗，因爲它包含硬編碼的ASCII）。

編輯：

重讀的問題，仔細（最終），看來你實際上是尋找更多的理念，少技術。讓你走出無限倒退的訣竅是雙發。您必須從相同的數據中獲得編碼的程序和擴展的程序：使用相同的數據2種方式。因此該數據僅描述了圍繞其未來表現的部分程序框架。該幀內的圖像是原始的直接副本。

這就是你自然會用手製作遞歸圖的方式：電視電視的電視。在某些時候你會感到疲倦，只是在屏幕上畫一些眩光，因爲遞歸已經足夠建立。

編輯：

我在尋找的，爲什麼基內斯是可能的一個很好的解釋。

奎因的「可能性」進入了19世紀和20世紀的數學革命的深處。「經典」奎因由WVO奎因，是詞的序列（IIRC）

時追加到自身

這是一個悖論，如同大衛的要求的東西，「讓我產生false 「當傷心的時候快樂，讓我開心的時候很難過」，雙方都寫着獎章回答：「這也會過去」。

同一種結由現代數學邏輯的先驅，如弗雷格，拉塞爾和懷特黑德，瓦魯薩維奇，當然，我們的男孩圖靈，教堂和Thue調查。這個訣竅使得我們可以將Qu因從文字遊戲轉化爲程序性演示（沿着路線解開悖論部分），這是Gödel將算術運算本身編碼爲數字的方法，因此整個數學表達式可以編碼成一個單一的（巨大的）整數。具體地說，執行該表示的解碼的數學函數可以以相同（數字）的形式表示。這個數字（一個哥德爾編碼函數）是的代碼和數據。

這個三重奏（代碼，表示，數據）可以轉換爲不同的表達方式。通過選擇不同的表示（或鏈如：bytes-> ASCII-> hexadecimal-> integer）會更改代碼的行爲，這會改變數據的外觀。

來源

2012-10-18 16:36:47

編寫奎因的「訣竅」是什麼？

回答

相關問題