Изменения

|definition='''Квайном''' (англ. '''куайном, quine''') <ref name=quineName/> называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).

==Происхождение названия==Название "квайн" было предложено [http://ru.wikipedia.org/wiki/ХофштадтерСтоит отметить,_Дуглас Дугласом Хофштадтером]что программы, в его известной книге "Гёдельиспользующие для чтения своего кода файловую систему, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа [http://ru.wikipediaквайнами не считаются.org/wiki/КуайнНапример,_Уиллард_Ван_Орман Уилларда Ван Ормана Квайна], который углублённо изучал явление [http://en.wikipedia.org/wiki/Indirect_self-reference косвенного самоупоминания]. в частности, это явление можно проиллюстрировать следующим парадоксальным утверждением, известном как парадокс Квайна: программа на BASIC вида {{Теорема|about<font size =парадокс Квайна|statement="Становится ложным, когда добавляется к собственной цитате2em" становится ложным, когда добавляется к собственной цитате.> }}==Доказательство существования=={{Теорема|about=о существовании квайнов 10 LIST|statement= На любом языке программирования можно написать квайн|proof= Рассмотрим функцию <tex>h(t)</texfont>, которая по данной программе <tex>t</tex> печатает её выводит на экран свой исходный код. Очевидно, она вычислима. По [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B8#.D0.A2.D0.B5.D0.BE.D1.80.D0.B5.D0.BC.D0.B0_.D0.BE_.D0.BD.D0.B5.D0.BF.D0.BE.D0.B4.D0.B2.D0.B8.D0.B6.D0.BD.D0.BE.D0.B9_.D1.82.D0.BE.D1.87.D0.BA.D0.B5 теореме о неподвижной точке] существует такая программа поскольку команда <tex>n\mathtt{LIST}</tex>, что <tex>hпросит среду исполнения вывести в консоль текущую программу (n)</tex> и <tex>n</tex> ведут себя одинаково, то есть печатают свой код. Таким образом, <tex>n</tex> печатает код <tex>n</tex>, т.е. является квайном.}} ==Общий принцип написания квайнов==Квайн состоит из двух сегментов: <b>кода</b> и <b>данных</b>. Данные представляют собой текстовую версию кода, иэта функция была необходима для программистов, так как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в нихпрограммы зачастую не мог поместиться на консоль 80x25 символов), а затем, просто выводит данные.Чтобы написать простой квайн на C, мы положим в данные текстовое представление кода и при выводе данных будем экранировать знаки табуляции и переносов: <nowiki>const char data [] ="#include <stdio.h>\n\nint\nmain (void)\n{\n unsigned int i;\n\n p""rintf (\"const char data [] =\");\n for ( i=0 ; data[i] ; i++ "")\n {\n if ( i%60 == 0 )\n\tprintf (\"\\n\\\"\");\n switc""h ( data[i] )\n\t{\n\tcase '\\\\':\n\tcase '\"':\n\t printf (\"\\\\%c\", d""ata[i]);\n\t break;\n\tcase '\\n':\n\t printf (\"\\\\n\");\n\t break;\n""\tcase '\\t':\n\t printf (\"\\\\t\");\n\t break;\n\tdefault:\n\t printf"" (\"%c\", data[i]);\n\t}\n if ( i%60 == 59 || !data[i+1] )\n\t""printf (\"\\\"\");\n }\n printf (\";\\n\\n\");\n for ( i=0 ; data[""i] ; i++ )\n putchar (data[i]);\n return 0;\n}\n";

#include <stdioКвайн состоит из двух сегментов: кода и данных. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код, содержащийся в них, а затем просто выводит данные.h>

printf ("const char data [] ="); for ( i=0 ; data[i] ; i++ ) { if ( i%60 Мультиквайны== 0 ) printf ("\n\""); switch ( data[i] ) { case '\\': case '"': printf ("\\%c", data[i]); break; case '\n': printf ("\\n"); break; case '\t': printf ("\\t"); break; default: printf ("%c", data[i]); } if ( i%60 == 59 || !data[i+1] ) printf ("\""); } printf (";\n\n"); for ( i=0 ; data[i] ; i++ ) putchar (data[i]); return 0;}</nowiki>==Связанные определения=====Интроны===

|definition='''Интроном''' (англ. ''intron'') <ref name=intronName/> называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся сохраняется в процессе саморепликации квайна.

|definition='''Би-квайномБиквайном''' (bi-quineангл. ''biquine'') называется программа, которая делает одно из двух:*при обычном запуске она выводит свой исходный код,

Её "брат " делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным спец. специальным аргументом.

|definition='''<tex>R</tex>-квайном''' (англ. <tex>R</tex>-''quine'') называется программа, способная вывести исходный код <tex>R-1</tex> программ на других языках программирования в зависимости от переданного ей аргумента, а так же также свой исходный код при вызове без аргументов.

Заметим, что требование, чтобы программы были на разных языках программирования , важно, т.к. иначе все программы смогут иметь один и тот же код. 

|about=о существовании мульти-квайновмультиквайнов|statement= На любом языке программирования можно написать мульти-квайнмультиквайн.|proof= Докажем утверждение для би-квайна, для биквайна. Для большего количества языков доказательство будет выглядеть аналогично.

Рассмотрим программу с двумя параметрами на языке <tex>L_1</tex>, которая выводит первый параметр при обычном запуске и второй {{- --}} при запуске со спец. аргументом. По [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B8#.D0.A2.D0.B5.D0.BE.D1.80.D0.B5.D0.BC.D0.B0_.D0.BE_.D0.BD.D0.B5.D0.BF.D0.BE.D0.B4.D0.B2.D0.B8.D0.B6.D0.BD.D0.BE.D0.B9_.D1.82.D0.BE.D1.87.D0.BA.D0.B5 [Теорема о рекурсии|теореме о неподвижной точкерекурсии]] мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке <tex>L_2</tex>. И , наконец, зафиксируем как аргумент параметр первой исходник программы исходный код второй и наоборот.

Таким образом, следуя нашему ===Принцип написания===Будем следовать доказательствуи напишем мультиквайн для двух языков. Далее покажем, чтобы написать мульти-квайн мы будем использовать интроныкак добавить новый язык. У нас есть * напишем для каждого языка "полуквайн":<table><tr><td><font size = "2em"> <tex>P_1(p,arg)</tex>: '''if''' (arg == "print second!") '''print'''(p) '''else''' '''print'''(getSrc()) </font></td><td><font size = "2em"> <tex>P_2(p,arg)</tex>: '''if''' (arg == "print first!") '''print'''(p) '''else''' '''print'''(getSrc()) </font></td></tr></table>* подставим код второй программы в первую:<font size = "2em"> <tex>rP_1(p,arg)</tex>: '''if''' (arg == "print second!") '''print'''(<tex>P_2</tex> программ(p, т.еarg). getSrc()) '''else''' '''print'''(getSrc()) </font>* применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим параметр на исходный код программы: <font size = "2em"> <tex>P_1(arg)</tex>: '''if''' (arg == "print second!") '''print'''(<tex>rP_2</tex> сегментов кода (на каждом языкеgetSrc(), arg).getSrc()) '''else''' '''print'''(getSrc()); кроме того</font>Вторая программа может быть получена запуском первой с нужным аргументом. Теперь добавим третий язык:* напишем для него "полуквайн", каждая из но уже с двумя параметрами и тремя возможными выводами:<font size = "2em"> <tex>rP_3(p1,p2,arg)</tex> программ имеет : '''if''' (arg == "print first!") '''print'''(p1) '''elseif''' (arg == "print second!") '''print'''(p2) '''else''' '''print'''(getSrc()) </font>* добавим параметр в дополнение к сегменту кода два уже существующих квайна: <table><tr><td><font size = "2em"> <tex>P_1(p,arg)</tex>: '''if''' (arg == "print second!") '''print'''(<tex>rP_2</tex> сегментов данных(p, каждая из которых представляет собой код на определённом языке getSrc(т.е), arg). getSrc()) '''elseif''' (arg == "print third!") '''print'''(p) '''else''' '''print'''(getSrc()) </font></td><td><font size = "2em"> <tex>P_2(p,arg)</tex>: '''if''' (arg == "print first!") '''print'''(<tex>r-1P_1</tex> интрон + сегмент данных программы(p, getSrc(), arg). Когда программу getSrc()) '''elseif''' (arg == "print third!") '''print'''(p) '''else''' '''print'''(getSrc()) </font></td></tr></table> * подставим код первых двух в третью:<font size = "2em"> <tex>iP_3(p1,p2,arg)</tex> : '''if''' (arg == "print first!") '''print'''(имеющую сегмент кода под номером <tex>iP_1</tex> на языке (p1, arg).getSrc()) '''elseif''' (arg == "print second!") '''print'''(<tex>L_iP_2</tex>(p2, arg).getSrc()) '''else''' '''print'''(getSrc() просят вывести ) </font> * применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим оба параметра на исходный код программы :<font size = "2em"> <tex>P_3(arg)</tex>: '''if''' (arg == "print first!") '''print'''(<tex>jP_1</tex>(getSrc(), она использует один из своих интронов, чтобы вывести сегмент кода программы arg).getSrc()) '''elseif''' (arg == "print second!") '''print'''(<tex>jP_2</tex>(getSrc(), а затем использует все интроны arg).getSrc()) '''else''' '''print'''(getSrc()) </font>Две оставшиеся программы будут выглядеть аналогично и свой сегмент данных для вывода сегмента данных программы смогут быть получены путём запуска третьей с каждым из возможных аргументов. == Примечания ==<texreferences>j<ref name=quineName>Название "квайн" было предложено [http:/tex/ru.wikipedia.org/wiki/Хофштадтер,_Дуглас Дугласом Хофштадтером], в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа [http://ru.wikipedia.org/wiki/Куайн,_Уиллард_Ван_Орман Уилларда Ван Ормана Квайна], который углублённо изучал явление [http://en.wikipedia.org/wiki/Indirect_self-reference косвенного самоупоминания].</ref><ref name=intronName>Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов.</ref></references> == Ссылки Источники информации ==* [http://www.madore.org/~david/computers/quine.html Madore.org &mdash; Quines (self-replicating programs)]* [http://habrahabr.ru/post/186782/ Хабрахабр &mdash; Эстафета из 50 квайнов]* [http://habrahabr.ru/post/188378/ Хабрахабр &mdash; Мультиязыковые квайны]* [http://habrahabr.ru/post/128191/ Хабрахабр &mdash; Как писать квайны]* [http://en.wikipedia.org/wiki/Quine_(computing)#Multiquines Wikipedia &mdash; Multi-quines] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]]