Квайны

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Квайном (англ. quine)[1] называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом)[2].

Доказательство существования

Теорема (о существовании квайнов):
На любом языке программирования можно написать квайн
Доказательство:
[math]\triangleright[/math]
Рассмотрим функцию [math]h(t)[/math], которая по данной программе [math]t[/math] печатает её исходный код. Очевидно, она вычислима. По теореме о неподвижной точке существует такая программа [math]n[/math], что [math]h(n)[/math] и [math]n[/math] ведут себя одинаково, то есть печатают свой код. Таким образом, [math]n[/math] печатает код [math]n[/math], т.е. является квайном.
[math]\triangleleft[/math]

Общий принцип написания квайнов

Квайн состоит из двух сегментов: кода и данных. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в них), а затем, просто выводит данные. Чтобы написать простой квайн на C, мы положим в данные текстовое представление кода и при выводе данных будем экранировать знаки табуляции и переносов:

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>

int
main (void)
{
  unsigned int i;

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

Можно представить сегмент данных как некий шифр, который можно расшифровать двумя способами. В результате расшифровки первым способом получится строковое представление собственно сегмента данных, при расшифровке вторым способом получится строковое представление сегмента кода. Объединив результаты этих расшифровок, мы получим строку, в которой содержится весь исходный код программы. Таким образом, изменяя способ шифровки-расшифровки, можно получать сложные конструкции, например, цикл из 50 программ, каждая из которых выводит код на новом языке программирования, который является следующей программой в цикле

Связанные определения

Интроны

Определение:
Интроном (intron) называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся в процессе саморепликации квайна.

Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов. В вышеприведённый квайн можно легко добавить интрон, написав перед объявлением функции

const unsigned char intron[] = "--Hello! I am an intron!---";

и добавив в код (а значит, и модифицировав данные) строчки для вывода интрона. Интроны активно используются при создании мульти-квайнов.

Мульти-квайны

Определение:
Би-квайном (bi-quine) называется программа, которая делает одно из двух:
  • при обычном запуске она выводит свой исходный код
  • при запуске с особым аргументом она выводит исходный код своего "брата" на другом языке программирования.
Её брат делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным спец. аргументом.


Определение:
[math]R[/math]-квайном называется программа, способная вывести исходный код [math]R-1[/math] программ на других языках программирования в зависимости от переданного ей аргумента, а так же свой исходный код при вызове без аргументов.

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

Теорема (о существовании мульти-квайнов):
На любом языке программирования можно написать мульти-квайн
Доказательство:
[math]\triangleright[/math]

Докажем утверждение для би-квайна, для большего количества языков доказательство будет выглядеть аналогично.

Рассмотрим программу с двумя параметрами на языке [math]L_1[/math], которая выводит первый параметр при обычном запуске и второй - при запуске со спец. аргументом. По теореме о неподвижной точке мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке [math]L_2[/math]. И наконец, зафиксируем как аргумент первой исходник второй и наоборот.
[math]\triangleleft[/math]

Таким образом, следуя нашему доказательству, чтобы написать мульти-квайн мы будем использовать интроны. У нас есть [math]r[/math] программ, т.е. [math]r[/math] сегментов кода (на каждом языке); кроме того, каждая из [math]r[/math] программ имеет в дополнение к сегменту кода [math]r[/math] сегментов данных, каждая из которых представляет собой код на определённом языке (т.е. [math]r-1[/math] интрон + сегмент данных программы). Когда программу [math]i[/math] (имеющую сегмент кода под номером [math]i[/math] на языке [math]L_i[/math]) просят вывести исходный код программы [math]j[/math], она использует один из своих интронов, чтобы вывести сегмент кода программы [math]j[/math], а затем использует все интроны и свой сегмент данных для вывода сегмента данных программы [math]j[/math].

Источники информации

Примечания

  1. Название "квайн" было предложено Дугласом Хофштадтером, в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа Уилларда Ван Ормана Квайна, который углублённо изучал явление косвенного самоупоминания.
  2. Из теоремы Клини о рекурсии очевидно следует, что квайн можно написать на любом Тьюринг-полном языке.