Введение
Самовоспроизводящаяся программа
Квин – это компьютерная программа, которая не принимает никаких входных данных и выдает в качестве единственного результата копию своего собственного исходного кода. В теории вычислимости и литературе по информатике для обозначения таких программ используются термины "самовоспроизводящиеся программы", "самореплицирующиеся программы" и "самокопирующиеся программы". Квин представляет собой фиксированную точку среды выполнения, если рассматривать эту среду как функцию, преобразующую программы в их результаты. Квины возможны в любом языке программирования, являющемся полным по Тьюрингу, как прямое следствие теоремы о рекурсии Клини. Для развлечения программисты иногда стремятся создать максимально короткий квин на конкретном языке программирования.
История
Идея самовоспроизводящихся автоматов возникла на заре вычислительной техники, если не раньше. Джон фон Нейман разработал теорию о них в 1940-х годах. Позже, в 1972 году, Пол Братли и Жан Милло обсудили их в статье "Компьютерные забавы: самовоспроизводящиеся автоматы". Братли впервые заинтересовался самовоспроизводящимися программами, увидев первую известную такую программу, написанную на языке Atlas Autocode в Эдинбурге в 1960-х годах Хамишем Деваром, преподавателем и исследователем Эдинбургского университета. Требование предоставления исходного кода GNU Affero General Public License основано на идее квина.
Пустые куины
В некоторых языках, особенно в скриптовых, но также и в C, пустой исходный файл представляет собой фиксированную точку языка, то есть является корректной программой, не выдающей никакого вывода. Такая пустая программа, предложенная как "самая маленькая в мире самовоспроизводящаяся программа", однажды выиграла приз за "наиболее вольное обращение с правилами" на Международном конкурсе обфусцированного кода на C. Программа фактически не компилировалась, а использовала команду cp для копирования файла в другой файл, который затем можно было запустить для вывода пустой строки.
Программы Ouroboros
Концепция куина может быть расширена до нескольких уровней рекурсии, порождая "программы ouroboros" или куин-реле. Это не следует путать с мультиквинами.
Полиглота
Подобно, но в отличие от мультикуина, полиглотная программа — это компьютерная программа или скрипт, написанный на нескольких языках программирования или в нескольких форматах файлов, используя их синтаксис в комбинации. Полиглотная программа не обязана обладать свойством самовоспроизведения, хотя она может быть квином при одном или нескольких способах её выполнения. В отличие от квинов и мультиквинов, существование полиглотных программ не гарантируется для произвольных наборов языков теоремой рекурсии Клини, поскольку они основаны на взаимодействии синтаксисов, а не на доказуемом свойстве, что один язык всегда можно встроить в другой.
Автоматическое генерирование
Используя методы реляционного программирования, можно автоматически генерировать квины, преобразуя интерпретатор языка (или, что эквивалентно, компилятор и среду выполнения) в реляционную программу и затем находя её фиксированную точку.