Search
Write a publication
Pull to refresh

Comments 37

Не квайн. Из условия «программа делает А» явно следует, что «программа не делает не А». Если задано, что программа должна выводить свой текст, то никаких других текстов она выводить не должна.
<зануда mode>
Не по логике — не следует. Условие должно быть таким «программа делает только А».
</зануда mode>
Опечатался. Должно быть «по логике — не следует».
> Конечно, приведённая здесь программа отсылает нас к теореме «о бесконечных обезьянах», которая утверждает, что абстрактная обезьяна, ударяя случайным образом по клавишам печатной машинки в течение неограниченно долгого времени, рано или поздно напечатает любой наперёд заданный текст (в частности, «Гамлет» Шекспира).

С появлением интернета стало ясно, что теорема не верна :)
Если бы они набирали случайно, то может быть и напечатали бы. Но в реальности и у обезьян, и у интернета есть вполне определенный bias, который и не позволяет этого сделать.
P. S. Хотя Гамлет набранный в интернете все же есть ;)
— С появлением интернета стало ясно, что теорема не верна
Просто подождите еще.
Таким образом любая программа может быть «квайном». Нигде, например, не сказано, что нельзя использовать свой компилятор для программы.
Квайном не может быть программа, использующая хак среды исполнения, чтобы получить доступ к своим исходникам. (Определение Ч.Уэзерелла).
Т.е. бейсиковская классика 10 LIST не является квайном, потому что среда исполнения и конфеты за неё есть будет.
В остальном же, ограничений на среду нет.

Например, если мы напишем вот такой деревянный интерпретатор языка helloworld,
for s in source_code :
  print "helloworld" # каждую строку интерпретируем как команду вывода "helloworld"

то квайнами будут пустой файл и файлы, заполненные строками helloworld.
Одна беда, helloworld не тьюринг-полон, но это несложно обойти, скрестив его с брейнфаком:
— если строка начинается на #, то печатаем #helloworld
— иначе, выполняем брейнфак-код этой строки

Я этот язык имел в виду, но квайны на нём нечестные, команда Q выводит содержимое памяти интерпретатора (как бейсик).
Вот если бы команда Q печатала одну лишь букву Q в окружении кучи плюсиков, то её вывод был бы квайном.
Для бесконечных обезьян нужно включить в программу код проверки, что выходная строка является валидной программой (запускаем компилятор) и её результат (запускаем интерпретатор) совпадает с ней самой.
retry = True
while retry :
  src = generate_random_text()
  ok, printed = compile_and_run(src)
  retry = not ok or printed != src
print src

Этот код может породить квайн, может сам явиться квайном, может зациклиться, порождая всякую ерунду, но не квайны, может породить одноразовый квайн (который случайно напечатает себя с первой попытки), может уйти в бесконечную рекурсию, порождая вариацию себя, которая… (см. с начала строки).
Но если мы заглянем за край проективной плоскости, то там, несомненно, увидим там результат — квайн.
Ответов на смысл жизни надеюсь эта программа не дает?
Хм, а как вам вот такой квайн:

program quine;
var i:byte;
begin
srand(1337);
for i:=1 to 93 do write(chr(random(255)));
end.

Если получится найти подходящий seed, это будет на самом деле хардкор!
Значения seed ограничены, а если нет, то вечность подбирать будем :)
Такого может и не существовать. Проблема в том что нужно найти такой seed, который будет выводить сам себя.
Можно наверное так генератор написать, умело подобрав коэффициенты, причем который бы еще и тесты NIST проходил или хотя бы удовлетворял каким-то критериям.
Можно значительно повысить шансы на успех, если ввести массив со всеми символами, присутствующими в программе. Их будет значительно меньше 256. А потом сделать как-нибудь так:

const a:array[1..7] of string=(#13#10,
'const a:array[1..7] of string=(#13#10,',
''',
',',
');',
'',
'begin for i:=1 to 32 do write(a[random(7)]); end.');

begin for i:=1 to 32 do write(a[random(7)]); end.

И вот здесь уже можно искать seed… (естественно, этот пример работать не будет из-за синтаксических ошибок, это просто демонстрация идеи).
Все равно слишком длинно получается. Реальнее записать программу в виде байт-кода (например, взять спектрумовский бейсик, там один байт на команду), и заставить ее генерировать такой же байт-код. Либо придумать язык, где нужные функции записываются одной буквой.

Хотя понятно, что такой хак завязан на реализацию генератора псевдослучайных чисел, следовательно, ничем не лучше HQ9+ и других хаков.
Генераторы псевдослучайных чисел, поставляемые в комплекте компиляторов и стандартных библиотек, как правило генерируют относительно короткую (10^9 и менее чисел до повторения) и известную заранее последовательность. srand() всего лишь начинает генерацию с другого места этой же последовательности. Поэтому, если программа попытается стать квайном с помощью rand и srand, вероятность успеха будет строго равна нулю.

Более того, даже если пользоваться более мощными методами генерации случайных чисел, такими как Mersenne-Twister, все равно длина последовательности хоть и велика, но конечна. Инициализация с другим seed, аналогично, просто запускает ту же самую последовательность с другого места. До тех пор, пока генератор псевдослучайных чисел является конечным автоматом (а все программные ГПСЧ ими являются), длина производимой ими последовательности конечна и поэтому не включает в себя все возможные подпоследовательности. Поэтому исходный код такого «квайна» может содержаться, а может и не содержаться в выводе ГПСЧ.
Да, автор не видит разницы между генератором случайных чисел и генератором псевдослучайных чисел. Для псевдослучайного генератора вероятность получить какую-либо последовательность может быть нулевой. Причем в примере она таковой и является.
Ничто не мешает нам слинковаться с правильным генератором ПСЧ, который выдаёт заданную последовательность.
Для написания подобного рода квайнов явно необходимо использовать файловую систему πfs, там то скорее всего есть любая последовательность
Нет, не выйдет.
Дело в том, что хелловорлд в πfs лежит так далеко, что не хватит диска для записи оффсета
а квайн порождающий сам себя лежит примерно в экспоненту раз дальше — на запись этого квайна не хватит всех атомов вселенной если бит информации записывать на каждом отдельном атоме.
Как-то вы очень уж смело утверждаете, что чего-то там не хватит. В конце концов, от языка зависит.
грубо говоря из утверждения

«для любой конечной последовательности [байт] ИКС существует число ОФС, такое что представление π начиная с оффсета ОФС совпадает с ИКС»

не следует, что

«для любого ЯП на котором возможно написать программу печатающую свой собственный код существует числа ОФС, ЛЕН такие, что в последовательности π начиная с ОФС лежит программа длиной ЛЕН, которая является заданным ЯП и печатает свой код»

Если вольно менять квантор всеобщности на квантор существования, то можно предложить следующий язык программирования квайнов

1) программой на языке ππ (читается: «пи-пи») является любое количество символов (в том числе и пустое)

2) операторы языка ππ: а — печать символа 'a', 'b' — печать символа 'b' и вообще любой встреченный символ в программе — это оператор печати этого символа (логично предположить, что операторов всего 256 штук, но существуют реализации языка с поддержкой UNICODE)

3) язык ππ не является алгоритмически полным, но зато на нем легко написать программу печатающую свой собственный текст. Вернее — любая программа на ππ именно и печатает свой собственный текст!

4) любая программа на ππ уже хранится в πfs

с пятницей вас! РАминь!

наврал слегонца.
в оспариваемом мной утверждении
следует читать "… существует числа ОФС, ЛЕН меньшие числа атомов во вселенной… "
Отсутствие следствия, на которое вы указали, само собой имеет место быть. Однако мой комментарий лишь выражал несогласие с вашим утверждением «хелловорлд в πfs лежит так далеко, что не хватит диска для записи оффсета». Если бы это утверждение (назовем его А) было истинным, то есть выводимым, то по правилу обобщения логики первого порядка, истинным было бы так же «для любого языка программирования А».
И то же про квайн. Я не увтреждаю, что он всегда близко в пи. Я спорю с вашем утверждением, что он всегда далеко в пи.
Квайном на π будет, например, смещение 1 (там лежит цифра 1). Но дальше вплоть до смещения 10000 подобных объектов не наблюдается.
Да вроде задача-то не такая сложная. Когда я учился в Университете (12 лет назад закончил), работал там же лаборантом. На перемене прибежал друг и сказал, что ему срочно нужна программа, выводящая сама себя на Турбо Паскале, я как раз сидел на работе в компьютерном классе — у меня то ли пар не было, то ли «солил». За короткую перемену я справился. Это, кстати, был первый и последний в моей жизни квайн.
почему последний? это как собрать кубик-рубик — типа я могу это сделать и все, больше он не интересен?
Да мне и в первый-то раз не интересно было. Сделал по просьбе друга.
Как на счет рендомайзера основанного на mouseMove и прочих действиях пользователя/ОС?
Необязательно рандомайзер — можно использовать просто программу для набора текста. То есть, например, notepad вполне себе является таким вот операторо-ориентированным квайном.
for(i=0;73>i++;)write(String.fromCharCode(parseInt(Math.random()*255)))

На JavaScript даже еще короче (и вероятность больше). Уверен, его можно еще сократить. Например, parseint заменить.
тогда вопрос встречный
квайн ли
print open(__file__).read()
Нет, в определении квайна написано, что программа не должна иметь внешнего ввода (в том числе, файлового)
А то так не интересно получается)
Sign up to leave a comment.

Articles