парадокс расселла в применении к программам

[avva]

Назовем программу проницательной, если в процессе своей работы она печатает в точности свой исходный код. При этом она необязательно останавливается когда-либо, и может печатать еще много всего. Очевидно, набор всех непроницательных программ - вполне определенный объект, в его существовании нет никакого парадокса. Может ли существовать программа, которая - не останавливаясь - печатает исходные коды всех непроницательных программ, и больше ничего?

Она не может напечатать свой код, потому что тогда она одновременно приноцательная по определению, и непроницательная, потому что она печатает только непроницательные программы.

Она не может не напечатать свой код, потому что если она его вообще никогда не напечатает, то она непроницательная по определению, а значит, когда-то должна дойти до своего кода и напечатать.

Поэтому такой программы не существует.

Кажется, это доказательство немного проще, чем стандартное доказательство проблемы остановки. Меж тем оно тоже доказывает невозможность алгоритмического решения определенной задачи. Правда, понятие "решения задачи" в этом случае не столь удобное, как в проблеме остановки.

(по мотивам главы о самореференции в Metamagical Themas Хофштадтера)

(интересно сравнить с парадоксом Расселла в теории множеств, а также известной его формулировкой о брадобрее, который решил брить всех в городе, кто не бреет самого себя, и выходит парадокс, если задуматься, бреет ли он себя сам. В парадоксе Расселла сам рассматриваемый объект "множество всех множеств, которые не являются собственными элементами" существовать не может - его существование и приводит к парадоксу. В вопросе о программах выше в существовании множества всех программ, которые не печатают свой код, нет никакого парадокса и оно вполне себе существует. Но оказывается, что распечатать его невозможно, т.е. когда мы хотим им "воспользоваться", нам не дают. Так же и с брадобреем: множество всех жителей, которые не бреют самих себя, вполне себе существует. Но если мы попробуем к нему подойти и "воспользоваться", т.е. брадобрей хочет брить именно его - это не получается)

Comments

[(Anonymous)]

Возьмём для простоты программный интерпретатор сat. Очевидно, что любая программа ненулевой длины будет печатать в точности свой код.
Единственная же программа нулевой длины будет печатать код всех непроницательных программ, т.е. ничего.
Сказать же, напечатала ли она свой собственный код или нет, с определенностью нельзя, а потому считать ее непроницательной неверно.

[avva.livejournal.com]

Ваш пример просто показывает, что я недостаточно тщательно определил свой формализм, и поэтому он может провисать на "крайних случаях" - напр. не разграничивает непечатание ничего и печатание пустой программы. Но я просто сознательно не входил в эти подробности; данную проблему легко исправить, более точно определив, что значит "распечатать все непроницательные программы, и более ничего". Например, введем отдельный разделительный символ X, который не используется в текстах программ, хотя они могут его выводить, и скажем, что "напечатать все непроницательные программы" значит выдавать на выход символы

X
код программы
X
код программы
...

и так далее до бесконечности (в случае тривиальных моделей, когда непроницательных программ конечное число, можно уговориться еще один Χ в конце поставить). Это сразу снимает выдвинутое вами возражение.

[amarao-san.livejournal.com]

"Поэтому такой программы не существует." - не убедительно.

С тем же успехом можно сказать, что брадобрея не существует.

[rednyrg721.livejournal.com]

А по Вашему, брадобрей, "который решил брить всех в городе, кто не бреет самого себя", существует?

[amarao-san.livejournal.com]

Брадобрей, очевидно _существует_. Получится у него это, или нет, другой вопрос. Но нет ни одной философской причины, почему конкретному брадобрею не может прийти в голову такая идея. Это реальный мир. Тут, если поделить на ноль, ничего страшного не происходит.

[rednyrg721.livejournal.com]

Но ведь если не получится, он уже не будет брадобреем, "который бреет всех в городе, кто не бреет самого себя", а значит такого брадобрея не существует. Не отделяйте брадобрея от его свойства, которое в кавычках.

[amarao-san.livejournal.com]

В исходной задаче было "брадобрей решил...". Такой брадобрей существует. Если бы мы говорили о брадобрее, который бы побрил всех, кто не бреется сам, то мы бы должны были говорить не о том, что брадобрей не существует, а о том, что брадобрей что-то не так сделал.

[dima-l.livejournal.com]

Этому брадобрею, если он человек разумный, стоило бы решить еще один вопрос (более конкретный): собирается ли он брить самого себя.
Как только он этот вопрос решит, он станет человеком, который принял два взаимоисключающих решения.
Такие случаи бывают (я лично много раз бывал в похожем положении).
То есть такой человек наверняка существует.
А еще у такого человека всегда существует опасность нарушить одно из своих решений (или оба).

[dopkins.livejournal.com]

Если я не ошибаюсь, история про брадобрея - способ рассказать этот парадокс нематематикам, которые не очень любят словосочетания "множество всех множеств". Исходно брадобрея не было: "Пусть K — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли K само себя в качестве элемента? Если да, то, по определению K, оно не должно быть элементом K — противоречие. Если нет — то, по определению K, оно должно быть элементом K — вновь противоречие."

Аналогично с программой: если она непроницательная, она не должна печатать себя, но тогда она должна печатать себя, потому что предназначена для печатания всех непроницательных. Такая программа не может существовать.

[amarao-san.livejournal.com]

Как мне кажется, в тот момент, когда происходит переход от множеств к объектам реального мира, происходит какой-то феерчиеский мухлёж.

Вот, тот же брадобрей. Вместо "брадобрей НЕ СМОЖЕТ" нам говорят "брадобрей НЕ СУЩЕСТВУЕТ". Но это же глупость! Значит, подобная тонкость должна быть и в теории множеств, только её упускают...

[dopkins.livejournal.com]

Действительно, здесь много зависит от формулировок. Прочитайте, пожалуйста, Википедию (http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%A0%D0%B0%D1%81%D1%81%D0%B5%D0%BB%D0%B0) - там в парадоксе брадобрея нет слов "сможет" и "существует".

Но мухлежа нет, математика такого не любит.

[emirr.livejournal.com]

Дело в том, что любая физическая (реальная) система существует во времени. И свойства элементов системы (например "бреет самого себя") могут со временем изменяться.

Хм

[alaev.livejournal.com]

- Кажется, это доказательство немного проще, чем стандартное доказательство проблемы остановки. Меж тем оно тоже доказывает невозможность алгоритмического решения определенной задачи.

Доказательство доказывает, что эту задачу в принципе нельзя решить. То есть даже если мы будем рассматривать не обычные вычислительные устройства, а допускающие какие-нибудь неалгоритмичные действия, всё равно такой программы существовать не будет.

То есть чисто логический парадокс, алгоритмы тут ни при чём. Проблема остановки тесно связана с понятием алгоритма.

Re: Хм

[(Anonymous)]

это не чисто логический парадокс, в том смысле, что множество непроницательных программ вполне себе существует (в отличие от множества всех множеств, не содержащих и т.д.) а нерекурсивно оно ровно потому же, почему нерекурсивно и множество останавливающихся программ.

все без исключения необычные вычислительные устройства рассматривать неинтересно. потому что вычислительное устройство, в котором ответ на вопрос «проницательна ли данная программа» дается встроенной командой, ничем не лучше, чем вычислительное устройство, в котором ответ на вопрос «останавливается ли данная программа» дается встроенной командой. если же считать, что такими мощными командами пользоваться нельзя, сразу возникает вопрос — а какими можно?

Re: Хм

[alaev.livejournal.com]

Я думаю, аналогия здесь такая.

- множество непроницательных программ вполне себе существует

точно так же, как класс всех множеств. А программа, которая печатает тексты всех непроницательных программ, не существует по тем же причинам, по каким класс всех множеств сам не является множеством.

- если же считать, что такими мощными командами пользоваться нельзя, сразу возникает вопрос — а какими можно?

Тут вообще неважно, какими командами мы пользуемся. Вместо вычислительного устройства можно рассмотреть произвольную функцию, отображающую некоторое множество слов (множество "программ") в множество бесконечных строк символов. Скажем, что "программа" проницательна, если её текст входит в строку, в которую она отображается. Далее можно повторить все рассуждения из исходного поста, ничего не изменится.

Понятие алгоритма тут никак не используется.

Re: Хм

[shmel39.livejournal.com]

А программа, которая печатает тексты всех непроницательных программ, не существует по тем же причинам, по каким класс всех множеств сам не является множеством.

Спасибо! Эта мысль у меня крутилась где-то на границе сознания вчера весь вечер, но я так и не смог её внятно сформулировать :-)

Re: Хм

[(Anonymous)]

да, это я ошибся немного, вы правы

Впрочем, я был не совсем прав

[alaev.livejournal.com]

Хотя сам по себе парадокс чисто логический, их него вытекает, что множество проницательных программ невычислимо (нерекурсивно), и даже не вычислимо перечислимо. Это тоже интересно.

Пожалуй, недостаток этого рассуждения в том, что проблема остановки даёт пример перечислимого множества, которое не является вычислимым. Здесь же рассматривается более сложное множество. Но зато доказательство более простое, да.

Точнее, совсем не прав

[alaev.livejournal.com]

Анатолий, надеюсь, я Вас не раздражаю обилием комментов? :) Предыдущее я писал в воскресенье вечером, и не обдумал всё до конца.

Множество всех проницательных программ вычислимо перечислимо: мы можем запустить все программы одновременно, и если какая-то их них выдаст свой код, напечатать её. Так мы перечислим все проницательные программы.

То есть это тоже пример вычислимо перечислимого и не вычислимого множества.

Re: Точнее, совсем не прав

[avva.livejournal.com]

Ничего страшного.

Множество всех НЕ-проницательных программ неперечислимо, и аргумент в записи, собственно, это доказывает.

Множество всех проницательных программ перечислимо (напр. используя ваш аргумент, который можно сделать строгим), и из предыдущего абзаца сразу следует, что не вычислимо.

Так что в итоге, вы правы, мы получаем пример невычислимого, перечислимого множества, как и в проблеме остановки. Но я вижу это как в первую очередь док-во неперечислимости непроницательных программ - суть док-ва именно в этом.

[mi-b.livejournal.com]

из того, что программа печатает "исходные коды всех проницательных программ и больше ничего" не следует, что программа не печатает ни одного кода проницательной программы - ведь может быть код проницательной программы, который непрерывная подстрока кода непроницательной или конкатенат кода нескольких непроницательных. так что искомая программа вполне может быть проницательной

[avva.livejournal.com]

см. ответ анониму выше, он подходит и для этого возражения тоже.

[mi-b.livejournal.com]

значит, ваш результат доказан для программ на языке, который запрещает некоторые выводимые символы в коде ;)

[(Anonymous)]

что в реальности помогают решать такие задачи ?

[mi-b.livejournal.com]

наверное, другие задачи ;)

забавная аналогия

[a-shen.livejournal.com]

можно ещё отметить, что перечислимое множество (recursively enumerable, computable enumerable etc.) можно задавать двумя способами - как область определения и как область значений. Стандартный пример неперечислимого множества говорит о программах, не входящих в свою область определения, Ваше рассуждение - о программах, не входящих в свою область значений

[shmel39.livejournal.com]

У меня давно появилась привычка - очень тщательно присматриваться к тем местах в доказательствах, где употребляется "очевидно", "легко заметить" и т.д. :=)) Особенно мне не понравилось "набор всех непроницательных программ". Не всякое множество рекурсивно перечислимо, а тут набор...

*Тут я два раза пытался написать про то, останется ли утверждение верным при замене "набор" -> "множество", но оба раза мне самому не нравилось и я стёр. Не знаю как это осознать. Неочевидно мне существует ли такое множество всех непроницательных программ.*

[avva.livejournal.com]

Я просто хотел избежать слова "множество" в этом аргументе для неспециалистов. Конечно, множество есть - и оно не рекурсивно перечислимо; собственно, аргумент именно это и доказывает, если строго подойти.

С существованием множества нет никаких проблем, так же, как с существованием множества всех неостанавливающихся программ, например. И свойство "строка x кодирует программу, к-я останавливается", и свойство "строка x кодирует программу, к-я во время своей работы ни разу не печатает x" легко можно формализовать в виде соответствующих формул. Если строго к этому подходить, надо выбрать формализм (напр. машины Тьюринга), определить, что такое "печатать в процессе работы" (т.к. машина Тьюринга может стирать уже написанное на ленте, так что может лучше и не ее выбрать в качестве формализма), и так далее. Но все это здесь действительно тривиально.

[bugabuga.livejournal.com]

Это из серии "Не существует программа, которая правильно отвечает на все бинарные вопросы словами true или false" с очевидным проверочным вопросом "Ты сейчас напечатаешь false?"? :)

[avva.livejournal.com]

Не совсем.

[a-bronx.livejournal.com]

взять множество всех программ
пока множество не пусто {
    взять любую программу из множества
    если программа непроницательная и не совпадает с данной программой {
       распечатать 
    }
    удалить программу из множества
}
распечатать себя

Так как множество всех программ бесконечно, то все условия выполнены:
1) программа в точности делает то, что нужно - распечатывает тексты всех непроницательных программ,
2) при этом сама программа явно проницательна, так как готова распечатать себя как только кончатся все непроницательные,
3) но она этого никогда не сделает, а значит она одновременно непроницательна (поэтому в неё и добавлен код для распечатки самой себя, непроницательной :)

[avva.livejournal.com]

Все же эта программа однозначно непроницательна :)

[a-bronx.livejournal.com]

Ну вот как только закончит с другими непроницательными, так сразу обязательно распечатает себя! Честно-честно! Просто эта программа ещё и альтруистична, поэтому пропускает всех вперёд! :)

[a-bronx.livejournal.com]

"Я бы давно уже побрился, да вот от клиентов отбоя нету!" (с) брадобрей Рассела :)

[avva.livejournal.com]

:)

[gaz-v-pol.livejournal.com]

Вы исходите из предположения, что про каждую программу можно с уверенностью сказать, является ли она проницательной. Это не кажется мне очевидным. Можно себе представить программу, которая пытается из аксиом арифметики вывести противоречие, и если находит, то включается какой-то блок, который доводит программу до печати своего текста. Будет ли такая программа проницательной?

[avva.livejournal.com]

С моей точки зрения - несомненно, не будет. Просто мы никогда не сможем доказать (конечными методами), что она непроницательна.

[cousin-it.livejournal.com]

Ага. Я как сейчас помню ощущение собственной тупости, когда до меня много лет назад впервые дошло, что парадокс Рассела, проблема остановки и теорема Геделя о неполноте - это одно и то же.

[ro-che.livejournal.com]

Не понял, почему парадокс Рассела и теорема Геделя о неполноте -- одно и то же?

[pingva.livejournal.com]

недавно друзья, с которыми ты нас познакомил, рассказали прекрасную около-геделевскую историю:

некая особа предъявляла безо всякого повода справку о том, что она не сумасшедшая.