Куайн (квайн, англ. quine) — компьютерная программа, которая выдаёт на выходе точную копию своего исходного текста. При этом программы, использующие внешние данные (чтение текста программы из файла, ввод его с клавиатуры и так далее), куайнами не считаются. Кроме того, не считается куайном «программа», не содержащая вообще никакого кода (вырожденный случай).
В книге «Этюды для программистов» Чарльза Уэзерелла сформулировано более строгое условие: программа не должна пользоваться приёмами, позволяющими получить доступ к своему исходному коду, хранящемуся в памяти загрузчика или интерпретатора. Поэтому куайны 10 LIST на бейсике и SOURCE TYPE на языке Форт — не совсем честные.
10 LIST
SOURCE TYPE
Термин получил название от имени американского логика и философа Уилларда Ван Ормана Куайна (1908—2000), который занимался углублённым изучением косвенной самореференции (англ. indirect self-reference).
Куайны возможны в любом тьюринг-полном языке программирования — как следствие теоремы Клини о рекурсии[англ.]. Идея куайнов была впервые описана Полом Братли (англ. Bratley, Paul) и Жаном Милло (англ. Millo, Jean) в «Computer Recreations; Self-Reproducing Automata», Software — Practice & Experience, выпуск 2 (1972), с. 397—400. Братли заинтересовался саморепродуцированием программ после знакомства с первой такой программой, написанной на языке программирования Atlas Autocode в Эдинбурге в 1960-х годах преподавателем и исследователем Хэмишем Дюаром (англ. Hamish Dewar).
Вот исходный текст этой программы:
%BEGIN !THIS IS A SELF-REPRODUCING PROGRAM %ROUTINESPEC R R PRINT SYMBOL(39) R PRINT SYMBOL(39) NEWLINE %CAPTION %END~ %CAPTION %ENDOFPROGRAM~ %ROUTINE R %PRINTTEXT ' %BEGIN !THIS IS A SELF-REPRODUCING PROGRAM %ROUTINESPEC R R PRINT SYMBOL(39) R PRINT SYMBOL(39) NEWLINE %CAPTION %END~ %CAPTION %ENDOFPROGRAM~ %ROUTINE R %PRINTTEXT ' %END %ENDOFPROGRAM
Куайном n-го порядка для n > 1 {\displaystyle n>1} называется программа, которая выводит на экран такой код A 1 {\displaystyle A_{1}} , что ∀ k : 1 < k < n {\displaystyle \forall k:1<k<n} запуск кода A k − 1 {\displaystyle A_{k-1}} выводит на экран код A k {\displaystyle A_{k}} . При этом код A n − 1 {\displaystyle A_{n-1}} выводит на экран код изначальной программы.
Цепным куайном для списка языков программирования A 1 , . . . , A n {\displaystyle A_{1},...,A_{n}} называется такой код на языке A 1 {\displaystyle A_{1}} , что при поочерёдном запуске всех кодов ∀ k < n {\displaystyle \forall k<n} код на языке A k {\displaystyle A_{k}} выводит произвольный код на языке A k + 1 {\displaystyle A_{k+1}} . При этом сгенерированный в результате n − 1 {\displaystyle n-1} шагов код на языке A n {\displaystyle A_{n}} выводит на экран изначальный код на языке A 1 {\displaystyle A_{1}} .
Японский программист Юсукэ Эндо в 2013 году создал цепной куайн для n = 50 {\displaystyle n=50} с началом на языке программирования Ruby (впрочем, согласно определению, благодаря цикличности алгоритма при наличии кодов на всех языках начинать исполнение цикла можно с любого из них). Языки программирования в куайне расположены в алфавитном порядке. К 2018 году он довёл число языков в этом куайне до 128[1].
Юсукэ Эндо также создал псевдокуайн на Ruby, выводящий свой текст с помощью псевдоанимации (прорисовки новых комбинаций символов на консоли с заданным интервалом).
Также своеобразной математической вариацией куайна можно считать самореферентную формулу Таппера — неравенство, точки истинности которого в определённой области плоскости рисуют эту же формулу.