August 9th, 2009

moose, transparent

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

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

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

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

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

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

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

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

детские ссылки

1. Отличное сообщество kid_home_lib про детские книги. Там много всего замечательного.

2. via него - подборка журналов "Мурзилка" с номерами за многие годы.

3. (добавляет utnapishti) - kidpix - сообщество детской иллюстрации, тоже очень хорошее.

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

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

Вот, я написал, и самому даже забавно, что мне это показалось странным. Чему удивляться-то, действительно? Забыл, что ли, все? И отряд имени Мересьева, и книгу "Дети-герои", и все уроки, и все учебники, и все-все-все? Но показалось же странным; забыл же, значит, хотя бы частично.