Квайны

Эта статья находится в разработке!

Определение:

Квайном (куайном, quine) называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).

Происхождение названия

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

Теорема (парадокс Квайна):

"Становится ложным, когда добавляется к собственной цитате" становится ложным, когда добавляется к собственной цитате.

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

Теорема (о существовании квайнов):

На любом языке программирования можно написать квайн

Доказательство:

[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]

Ссылки

• Quines (self-replicating programs)