Пользуясь тем, что на Хабре проходит очередной месячник квайнов (см., например, Теорема Клини о неподвижной точке: квайны или Мультиязыковые квайны), рискну рассказать и одну свою историю. В ней не будет таких сложностей и заумствований, как в упомянутых топиках, поэтому данный текст можно воспринимать как пятничное развлечение.
Дело происходило почти четверть века назад, в эпоху отсутствия всеобщей компьютеризации и интернета. Возник у меня как-то вопрос — а можно ли написать программу, выводящую свой собственный текст. Слова «квайн» в те времена никто из моих знакомых не знал, а посмотреть в википедии я не мог «за отсутствием таковой» (с).
Промучался я над этой задачкой неделю, но таки победил её. Программа получилась корявенькая, длинная, но требованию удовлетворяла. Ужасно гордый собой, я начал предлагать эту задачу всем своим друзьям. По ходу дела пришлось уточнять условия — нельзя читать из файла, программа должна быть не пустой. Обычно после этого товарищи надолго задумывались.
Однако, один из друзей мне моментально ответил, что это, дескать, элементарно, и тут же предоставил мне требуемую программу, удовлетворяющую поставленным условиям.
Оказалось, что я всё-таки упустил одно важное и, казалось-бы, очевидное условие. Однако без его явного упоминания задачка действительно становится тривиальной. Тем не менее даже в современной статье о квайнах в википедии это условие почему-то отсутствует. Хотите знать, что это за условие?
Программа была примерно такая:
program quine;
var i:byte;
begin
randomize;
for i:=1 to 91 do write(chr(random(255)));
end.
Здесь язык — Паскаль, но, надеюсь, идея понятна: отсутствовало условие о том, что программа должна выводить собственный текст при каждом запуске.
Приведённая программа каждый раз выводит случайную последовательность из 91 символа. Вероятность того, что при этом получится текст исходной программы, крайне мала. Однако эта вероятность ненулевая!
Во многих статьях (особенно математических) множество компьютерных программ и алгоритмов заведомо сужается рассмотрением только детерминированных (или вычислимых) функций. Но множество мыслимых программ значительно шире.
Конечно, приведённая здесь программа отсылает нас к теореме «о бесконечных обезьянах», которая утверждает, что абстрактная обезьяна, ударяя случайным образом по клавишам печатной машинки в течение неограниченно долгого времени, рано или поздно напечатает любой наперёд заданный текст (в частности, «Гамлет» Шекспира).
Кроме различных сомнений философского характера в истинности этой теоремы, о большинстве которых можно прочитать из указанной статьи в википедии, есть и практические сложности с имплементацией данного квайна. Даже если мы позволим компьютеру работать неограниченное количество времени, возможно, что текст программы так и не будет ни разу напечатан. Дело в том, что операторы randomize и random обеспечивают выдачу псевдо-случайных чисел, а отнюдь не генерируют настоящую случайную последовательность. Поэтому может так статься, что именно нужная нам последовательность символов не появится никогда в силу этой псевдо-случайности.
Тем не менее оригинальность такого подхода к задаче заслуживает внимания!
PS. Прочитать об этом решении со слов упомянутого здесь друга, а также о других историях из его жизни можно тут: Куайн на Паскале
Автор: ystein
