Квайны — различия между версиями
(→Мульти-квайны) |
м (rollbackEdits.php mass rollback) |
||
(не показано 16 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition='''Квайном''' (англ. ''quine'')<ref name=quineName/> называется программа, которая выводит свой исходный код. При этом | + | |definition='''Квайном''' (англ. ''quine'')<ref name=quineName/> называется программа, которая выводит свой исходный код. При этом программа не должна использовать внешние данные (например, читать файл со своим исходным кодом). |
}} | }} | ||
Стоит отметить, что программы, использующие для чтения своего кода файловую систему, квайнами не считаются. Например, программа на BASIC вида | Стоит отметить, что программы, использующие для чтения своего кода файловую систему, квайнами не считаются. Например, программа на BASIC вида | ||
− | + | <font size = "2em"> | |
10 LIST | 10 LIST | ||
− | </font | + | </font> |
− | выводит на экран свой исходный код, поскольку команда <tex>\mathtt{LIST}</tex> просит среду исполнения вывести в консоль текущую программу (эта функция была необходима для программистов, | + | выводит на экран свой исходный код, поскольку команда <tex>\mathtt{LIST}</tex> просит среду исполнения вывести в консоль текущую программу (эта функция была необходима для программистов, так как код программы зачастую не мог поместиться на консоль 80x25 символов). |
− | Квайн состоит из двух сегментов: | + | Квайн состоит из двух сегментов: кода и данных. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код, содержащийся в них, а затем просто выводит данные. |
− | Формально общий принцип написания квайнов содержится в доказательстве [[Теорема о рекурсии|теоремы о рекурсии]]. Далее будет рассмотрено понятие | + | Формально общий принцип написания квайнов содержится в доказательстве [[Теорема о рекурсии|теоремы о рекурсии]]. Далее будет рассмотрено понятие мультиквайна. |
− | == | + | ==Мультиквайны== |
+ | ===Связанные определения=== | ||
+ | {{Определение | ||
+ | |definition='''Интроном''' (англ. ''intron'')<ref name=intronName/> называется часть сегмента данных, которая не используется для вывода кода, но сохраняется в процессе саморепликации квайна. | ||
+ | }} | ||
{{Определение | {{Определение | ||
− | |definition=''' | + | |definition='''Биквайном''' (англ. ''biquine'') называется программа, которая делает одно из двух: |
*при обычном запуске она выводит свой исходный код, | *при обычном запуске она выводит свой исходный код, | ||
*при запуске с особым аргументом она выводит исходный код своего "брата" на другом языке программирования. | *при запуске с особым аргументом она выводит исходный код своего "брата" на другом языке программирования. | ||
− | Её брат делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным специальным аргументом. | + | Её "брат" делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным специальным аргументом. |
}} | }} | ||
{{Определение | {{Определение | ||
− | |definition='''<tex>R</tex>-квайном''' (англ. <tex>R</tex>-''quine'') называется программа, способная вывести исходный код <tex>R-1</tex> программ на других языках программирования в зависимости от переданного ей аргумента, а | + | |definition='''<tex>R</tex>-квайном''' (англ. <tex>R</tex>-''quine'') называется программа, способная вывести исходный код <tex>R-1</tex> программ на других языках программирования в зависимости от переданного ей аргумента, а также свой исходный код при вызове без аргументов. |
}} | }} | ||
− | Заметим, что требование, чтобы программы были на разных языках программирования важно, | + | Заметим, что требование, чтобы программы были на разных языках программирования, важно, иначе все программы смогут иметь один и тот же код. |
{{ | {{ | ||
Теорема | Теорема | ||
− | |about=о существовании | + | |about=о существовании мультиквайнов |
− | |statement= На любом языке программирования можно написать | + | |statement= На любом языке программирования можно написать мультиквайн. |
− | |proof= Докажем утверждение для | + | |proof= Докажем утверждение для биквайна. Для большего количества языков доказательство будет выглядеть аналогично. |
− | |||
− | |||
− | |||
− | + | Рассмотрим программу с двумя параметрами на языке <tex>L_1</tex>, которая выводит первый параметр при обычном запуске и второй {{---}} при запуске со спец. аргументом. По [[Теорема о рекурсии|теореме о рекурсии]] мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке <tex>L_2</tex>. И, наконец, зафиксируем как параметр первой программы исходный код второй и наоборот. | |
− | {{ | ||
− | | | ||
}} | }} | ||
===Принцип написания=== | ===Принцип написания=== | ||
− | Будем следовать доказательству и напишем | + | Будем следовать доказательству и напишем мультиквайн для двух языков. Далее покажем, как добавить новый язык. |
− | * напишем для каждого языка " | + | * напишем для каждого языка "полуквайн": |
<table> | <table> | ||
<tr> | <tr> | ||
− | <td | + | <td><font size = "2em"> |
<tex>P_1(p,arg)</tex>: | <tex>P_1(p,arg)</tex>: | ||
'''if''' (arg == "print second!") | '''if''' (arg == "print second!") | ||
Строка 48: | Строка 47: | ||
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font></td> |
− | <td | + | <td><font size = "2em"> |
<tex>P_2(p,arg)</tex>: | <tex>P_2(p,arg)</tex>: | ||
'''if''' (arg == "print first!") | '''if''' (arg == "print first!") | ||
Строка 55: | Строка 54: | ||
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font></td> |
</tr> | </tr> | ||
</table> | </table> | ||
* подставим код второй программы в первую: | * подставим код второй программы в первую: | ||
− | + | <font size = "2em"> | |
<tex>P_1(p,arg)</tex>: | <tex>P_1(p,arg)</tex>: | ||
'''if''' (arg == "print second!") | '''if''' (arg == "print second!") | ||
− | '''print'''(<tex>P_2</tex>(p,arg).getSrc()) | + | '''print'''(<tex>P_2</tex>(p, arg).getSrc()) |
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font> |
* применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим параметр на исходный код программы: | * применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим параметр на исходный код программы: | ||
− | + | <font size = "2em"> | |
− | |||
− | |||
<tex>P_1(arg)</tex>: | <tex>P_1(arg)</tex>: | ||
'''if''' (arg == "print second!") | '''if''' (arg == "print second!") | ||
− | '''print'''(<tex>P_2</tex>(getSrc(),arg).getSrc()) | + | '''print'''(<tex>P_2</tex>(getSrc(), arg).getSrc()) |
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font> |
− | + | Вторая программа может быть получена запуском первой с нужным аргументом. | |
− | + | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Теперь добавим третий язык: | Теперь добавим третий язык: | ||
− | * напишем для него " | + | * напишем для него "полуквайн", но уже с двумя параметрами и тремя возможными выводами: |
− | + | <font size = "2em"> | |
<tex>P_3(p1,p2,arg)</tex>: | <tex>P_3(p1,p2,arg)</tex>: | ||
'''if''' (arg == "print first!") | '''if''' (arg == "print first!") | ||
Строка 95: | Строка 85: | ||
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font> |
* добавим параметр в два уже существующих квайна: | * добавим параметр в два уже существующих квайна: | ||
<table> | <table> | ||
<tr> | <tr> | ||
− | <td | + | <td><font size = "2em"> |
<tex>P_1(p,arg)</tex>: | <tex>P_1(p,arg)</tex>: | ||
'''if''' (arg == "print second!") | '''if''' (arg == "print second!") | ||
− | '''print'''(<tex>P_2</tex>(p,getSrc(),arg).getSrc()) | + | '''print'''(<tex>P_2</tex>(p, getSrc(), arg).getSrc()) |
'''elseif''' (arg == "print third!") | '''elseif''' (arg == "print third!") | ||
'''print'''(p) | '''print'''(p) | ||
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font></td> |
− | <td | + | <td><font size = "2em"> |
<tex>P_2(p,arg)</tex>: | <tex>P_2(p,arg)</tex>: | ||
'''if''' (arg == "print first!") | '''if''' (arg == "print first!") | ||
− | '''print'''(<tex>P_1</tex>(p,getSrc(),arg).getSrc()) | + | '''print'''(<tex>P_1</tex>(p, getSrc(), arg).getSrc()) |
'''elseif''' (arg == "print third!") | '''elseif''' (arg == "print third!") | ||
'''print'''(p) | '''print'''(p) | ||
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font></td> |
</tr> | </tr> | ||
</table> | </table> | ||
* подставим код первых двух в третью: | * подставим код первых двух в третью: | ||
− | + | <font size = "2em"> | |
<tex>P_3(p1,p2,arg)</tex>: | <tex>P_3(p1,p2,arg)</tex>: | ||
'''if''' (arg == "print first!") | '''if''' (arg == "print first!") | ||
− | '''print'''(<tex>P_1</tex>(p1,arg).getSrc()) | + | '''print'''(<tex>P_1</tex>(p1, arg).getSrc()) |
'''elseif''' (arg == "print second!") | '''elseif''' (arg == "print second!") | ||
− | '''print'''(<tex>P_2</tex>(p2,arg).getSrc()) | + | '''print'''(<tex>P_2</tex>(p2, arg).getSrc()) |
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font> |
− | * применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим оба параметра на исходный код программы | + | * применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим оба параметра на исходный код программы: |
− | + | <font size = "2em"> | |
<tex>P_3(arg)</tex>: | <tex>P_3(arg)</tex>: | ||
'''if''' (arg == "print first!") | '''if''' (arg == "print first!") | ||
− | '''print'''(<tex>P_1</tex>(getSrc(),arg).getSrc()) | + | '''print'''(<tex>P_1</tex>(getSrc(), arg).getSrc()) |
'''elseif''' (arg == "print second!") | '''elseif''' (arg == "print second!") | ||
− | '''print'''(<tex>P_2</tex>(getSrc(),arg).getSrc()) | + | '''print'''(<tex>P_2</tex>(getSrc(), arg).getSrc()) |
'''else''' | '''else''' | ||
'''print'''(getSrc()) | '''print'''(getSrc()) | ||
− | </font | + | </font> |
− | Две оставшиеся программы будут выглядеть аналогично | + | Две оставшиеся программы будут выглядеть аналогично и смогут быть получены путём запуска третьей с каждым из возможных аргументов. |
== Примечания == | == Примечания == |
Текущая версия на 19:38, 4 сентября 2022
Определение: |
Квайном (англ. quine)[1] называется программа, которая выводит свой исходный код. При этом программа не должна использовать внешние данные (например, читать файл со своим исходным кодом). |
Стоит отметить, что программы, использующие для чтения своего кода файловую систему, квайнами не считаются. Например, программа на BASIC вида
10 LIST
выводит на экран свой исходный код, поскольку команда
просит среду исполнения вывести в консоль текущую программу (эта функция была необходима для программистов, так как код программы зачастую не мог поместиться на консоль 80x25 символов).Квайн состоит из двух сегментов: кода и данных. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код, содержащийся в них, а затем просто выводит данные.
Формально общий принцип написания квайнов содержится в доказательстве теоремы о рекурсии. Далее будет рассмотрено понятие мультиквайна.
Мультиквайны
Связанные определения
Определение: |
Интроном (англ. intron)[2] называется часть сегмента данных, которая не используется для вывода кода, но сохраняется в процессе саморепликации квайна. |
Определение: |
Биквайном (англ. biquine) называется программа, которая делает одно из двух:
|
Определение: |
-квайном (англ. -quine) называется программа, способная вывести исходный код программ на других языках программирования в зависимости от переданного ей аргумента, а также свой исходный код при вызове без аргументов. |
Заметим, что требование, чтобы программы были на разных языках программирования, важно, иначе все программы смогут иметь один и тот же код.
Теорема (о существовании мультиквайнов): |
На любом языке программирования можно написать мультиквайн. |
Доказательство: |
Докажем утверждение для биквайна. Для большего количества языков доказательство будет выглядеть аналогично. Рассмотрим программу с двумя параметрами на языке , которая выводит первый параметр при обычном запуске и второй — при запуске со спец. аргументом. По теореме о рекурсии мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке . И, наконец, зафиксируем как параметр первой программы исходный код второй и наоборот. |
Принцип написания
Будем следовать доказательству и напишем мультиквайн для двух языков. Далее покажем, как добавить новый язык.
- напишем для каждого языка "полуквайн":
:
if (arg == "print second!")
print(p)
else
print(getSrc())
|
:
if (arg == "print first!")
print(p)
else
print(getSrc())
|
- подставим код второй программы в первую:
: if (arg == "print second!") print( (p, arg).getSrc()) else print(getSrc())
- применим теорему о рекурсии и заменим параметр на исходный код программы:
: if (arg == "print second!") print( (getSrc(), arg).getSrc()) else print(getSrc())
Вторая программа может быть получена запуском первой с нужным аргументом.
Теперь добавим третий язык:
- напишем для него "полуквайн", но уже с двумя параметрами и тремя возможными выводами:
:
if (arg == "print first!")
print(p1)
elseif (arg == "print second!")
print(p2)
else
print(getSrc())
- добавим параметр в два уже существующих квайна:
: if (arg == "print second!") print( (p, getSrc(), arg).getSrc()) elseif (arg == "print third!") print(p) else print(getSrc()) |
: if (arg == "print first!") print( (p, getSrc(), arg).getSrc()) elseif (arg == "print third!") print(p) else print(getSrc()) |
- подставим код первых двух в третью:
: if (arg == "print first!") print( (p1, arg).getSrc()) elseif (arg == "print second!") print( (p2, arg).getSrc()) else print(getSrc())
- применим теорему о рекурсии и заменим оба параметра на исходный код программы:
: if (arg == "print first!") print( (getSrc(), arg).getSrc()) elseif (arg == "print second!") print( (getSrc(), arg).getSrc()) else print(getSrc())
Две оставшиеся программы будут выглядеть аналогично и смогут быть получены путём запуска третьей с каждым из возможных аргументов.
Примечания
- ↑ Название "квайн" было предложено Дугласом Хофштадтером, в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа Уилларда Ван Ормана Квайна, который углублённо изучал явление косвенного самоупоминания.
- ↑ Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов.