Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 37
Не квайн. Из условия «программа делает А» явно следует, что «программа не делает не А». Если задано, что программа должна выводить свой текст, то никаких других текстов она выводить не должна.
> Конечно, приведённая здесь программа отсылает нас к теореме «о бесконечных обезьянах», которая утверждает, что абстрактная обезьяна, ударяя случайным образом по клавишам печатной машинки в течение неограниченно долгого времени, рано или поздно напечатает любой наперёд заданный текст (в частности, «Гамлет» Шекспира).
С появлением интернета стало ясно, что теорема не верна :)
С появлением интернета стало ясно, что теорема не верна :)
Если бы они набирали случайно, то может быть и напечатали бы. Но в реальности и у обезьян, и у интернета есть вполне определенный bias, который и не позволяет этого сделать.
P. S. Хотя Гамлет набранный в интернете все же есть ;)
P. S. Хотя Гамлет набранный в интернете все же есть ;)
— С появлением интернета стало ясно, что теорема не верна
Просто подождите еще.
Просто подождите еще.
— deleted -
Таким образом любая программа может быть «квайном». Нигде, например, не сказано, что нельзя использовать свой компилятор для программы.
Квайном не может быть программа, использующая хак среды исполнения, чтобы получить доступ к своим исходникам. (Определение Ч.Уэзерелла).
Т.е. бейсиковская классика 10 LIST не является квайном, потому что среда исполнения и конфеты за неё есть будет.
В остальном же, ограничений на среду нет.
Например, если мы напишем вот такой деревянный интерпретатор языка helloworld,
то квайнами будут пустой файл и файлы, заполненные строками helloworld.
Одна беда, helloworld не тьюринг-полон, но это несложно обойти, скрестив его с брейнфаком:
— если строка начинается на #, то печатаем #helloworld
— иначе, выполняем брейнфак-код этой строки
Т.е. бейсиковская классика 10 LIST не является квайном, потому что среда исполнения и конфеты за неё есть будет.
В остальном же, ограничений на среду нет.
Например, если мы напишем вот такой деревянный интерпретатор языка helloworld,
for s in source_code :
print "helloworld" # каждую строку интерпретируем как команду вывода "helloworld"
то квайнами будут пустой файл и файлы, заполненные строками helloworld.
Одна беда, helloworld не тьюринг-полон, но это несложно обойти, скрестив его с брейнфаком:
— если строка начинается на #, то печатаем #helloworld
— иначе, выполняем брейнфак-код этой строки
Вспоминается HQ9+
Для бесконечных обезьян нужно включить в программу код проверки, что выходная строка является валидной программой (запускаем компилятор) и её результат (запускаем интерпретатор) совпадает с ней самой.
Этот код может породить квайн, может сам явиться квайном, может зациклиться, порождая всякую ерунду, но не квайны, может породить одноразовый квайн (который случайно напечатает себя с первой попытки), может уйти в бесконечную рекурсию, порождая вариацию себя, которая… (см. с начала строки).
Но если мы заглянем за край проективной плоскости, то там, несомненно, увидим там результат — квайн.
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, это будет на самом деле хардкор!
program quine;
var i:byte;
begin
srand(1337);
for i:=1 to 93 do write(chr(random(255)));
end.
Если получится найти подходящий seed, это будет на самом деле хардкор!
Значения seed ограничены, а если нет, то вечность подбирать будем :)
Такого может и не существовать. Проблема в том что нужно найти такой seed, который будет выводить сам себя.
Можно значительно повысить шансы на успех, если ввести массив со всеми символами, присутствующими в программе. Их будет значительно меньше 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… (естественно, этот пример работать не будет из-за синтаксических ошибок, это просто демонстрация идеи).
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+ и других хаков.
Хотя понятно, что такой хак завязан на реализацию генератора псевдослучайных чисел, следовательно, ничем не лучше HQ9+ и других хаков.
Генераторы псевдослучайных чисел, поставляемые в комплекте компиляторов и стандартных библиотек, как правило генерируют относительно короткую (10^9 и менее чисел до повторения) и известную заранее последовательность. srand() всего лишь начинает генерацию с другого места этой же последовательности. Поэтому, если программа попытается стать квайном с помощью rand и srand, вероятность успеха будет строго равна нулю.
Более того, даже если пользоваться более мощными методами генерации случайных чисел, такими как Mersenne-Twister, все равно длина последовательности хоть и велика, но конечна. Инициализация с другим seed, аналогично, просто запускает ту же самую последовательность с другого места. До тех пор, пока генератор псевдослучайных чисел является конечным автоматом (а все программные ГПСЧ ими являются), длина производимой ими последовательности конечна и поэтому не включает в себя все возможные подпоследовательности. Поэтому исходный код такого «квайна» может содержаться, а может и не содержаться в выводе ГПСЧ.
Более того, даже если пользоваться более мощными методами генерации случайных чисел, такими как Mersenne-Twister, все равно длина последовательности хоть и велика, но конечна. Инициализация с другим seed, аналогично, просто запускает ту же самую последовательность с другого места. До тех пор, пока генератор псевдослучайных чисел является конечным автоматом (а все программные ГПСЧ ими являются), длина производимой ими последовательности конечна и поэтому не включает в себя все возможные подпоследовательности. Поэтому исходный код такого «квайна» может содержаться, а может и не содержаться в выводе ГПСЧ.
Да, автор не видит разницы между генератором случайных чисел и генератором псевдослучайных чисел. Для псевдослучайного генератора вероятность получить какую-либо последовательность может быть нулевой. Причем в примере она таковой и является.
Ничто не мешает нам слинковаться с правильным генератором ПСЧ, который выдаёт заданную последовательность.
Для написания подобного рода квайнов явно необходимо использовать файловую систему πfs, там то скорее всего есть любая последовательность
Нет, не выйдет.
Дело в том, что хелловорлд в πfs лежит так далеко, что не хватит диска для записи оффсета
а квайн порождающий сам себя лежит примерно в экспоненту раз дальше — на запись этого квайна не хватит всех атомов вселенной если бит информации записывать на каждом отдельном атоме.
Дело в том, что хелловорлд в πfs лежит так далеко, что не хватит диска для записи оффсета
а квайн порождающий сам себя лежит примерно в экспоненту раз дальше — на запись этого квайна не хватит всех атомов вселенной если бит информации записывать на каждом отдельном атоме.
Как-то вы очень уж смело утверждаете, что чего-то там не хватит. В конце концов, от языка зависит.
грубо говоря из утверждения
«для любой конечной последовательности [байт] ИКС существует число ОФС, такое что представление π начиная с оффсета ОФС совпадает с ИКС»
не следует, что
«для любого ЯП на котором возможно написать программу печатающую свой собственный код существует числа ОФС, ЛЕН такие, что в последовательности π начиная с ОФС лежит программа длиной ЛЕН, которая является заданным ЯП и печатает свой код»
Если вольно менять квантор всеобщности на квантор существования, то можно предложить следующий язык программирования квайнов
1) программой на языке ππ (читается: «пи-пи») является любое количество символов (в том числе и пустое)
2) операторы языка ππ: а — печать символа 'a', 'b' — печать символа 'b' и вообще любой встреченный символ в программе — это оператор печати этого символа (логично предположить, что операторов всего 256 штук, но существуют реализации языка с поддержкой UNICODE)
3) язык ππ не является алгоритмически полным, но зато на нем легко написать программу печатающую свой собственный текст. Вернее — любая программа на ππ именно и печатает свой собственный текст!
4) любая программа на ππ уже хранится в πfs
с пятницей вас! РАминь!
«для любой конечной последовательности [байт] ИКС существует число ОФС, такое что представление π начиная с оффсета ОФС совпадает с ИКС»
не следует, что
«для любого ЯП на котором возможно написать программу печатающую свой собственный код существует числа ОФС, ЛЕН такие, что в последовательности π начиная с ОФС лежит программа длиной ЛЕН, которая является заданным ЯП и печатает свой код»
Если вольно менять квантор всеобщности на квантор существования, то можно предложить следующий язык программирования квайнов
1) программой на языке ππ (читается: «пи-пи») является любое количество символов (в том числе и пустое)
2) операторы языка ππ: а — печать символа 'a', 'b' — печать символа 'b' и вообще любой встреченный символ в программе — это оператор печати этого символа (логично предположить, что операторов всего 256 штук, но существуют реализации языка с поддержкой UNICODE)
3) язык ππ не является алгоритмически полным, но зато на нем легко написать программу печатающую свой собственный текст. Вернее — любая программа на ππ именно и печатает свой собственный текст!
4) любая программа на ππ уже хранится в πfs
с пятницей вас! РАминь!
наврал слегонца.
в оспариваемом мной утверждении
следует читать "… существует числа ОФС, ЛЕН меньшие числа атомов во вселенной… "
в оспариваемом мной утверждении
следует читать "… существует числа ОФС, ЛЕН меньшие числа атомов во вселенной… "
Отсутствие следствия, на которое вы указали, само собой имеет место быть. Однако мой комментарий лишь выражал несогласие с вашим утверждением «хелловорлд в πfs лежит так далеко, что не хватит диска для записи оффсета». Если бы это утверждение (назовем его А) было истинным, то есть выводимым, то по правилу обобщения логики первого порядка, истинным было бы так же «для любого языка программирования А».
И то же про квайн. Я не увтреждаю, что он всегда близко в пи. Я спорю с вашем утверждением, что он всегда далеко в пи.
И то же про квайн. Я не увтреждаю, что он всегда близко в пи. Я спорю с вашем утверждением, что он всегда далеко в пи.
Квайном на π будет, например, смещение 1 (там лежит цифра 1). Но дальше вплоть до смещения 10000 подобных объектов не наблюдается.
Да вроде задача-то не такая сложная. Когда я учился в Университете (12 лет назад закончил), работал там же лаборантом. На перемене прибежал друг и сказал, что ему срочно нужна программа, выводящая сама себя на Турбо Паскале, я как раз сидел на работе в компьютерном классе — у меня то ли пар не было, то ли «солил». За короткую перемену я справился. Это, кстати, был первый и последний в моей жизни квайн.
Как на счет рендомайзера основанного на mouseMove и прочих действиях пользователя/ОС?
for(i=0;73>i++;)write(String.fromCharCode(parseInt(Math.random()*255)))
На JavaScript даже еще короче (и вероятность больше). Уверен, его можно еще сократить. Например, parseint заменить.
На JavaScript даже еще короче (и вероятность больше). Уверен, его можно еще сократить. Например, parseint заменить.
тогда вопрос встречный
квайн ли
квайн ли
print open(__file__).read()
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
А квайн ли это?