![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНазовем программу проницательной, если в процессе своей работы она печатает в точности свой исходный код. При этом она необязательно останавливается когда-либо, и может печатать еще много всего. Очевидно, набор всех непроницательных программ - вполне определенный объект, в его существовании нет никакого парадокса. Может ли существовать программа, которая - не останавливаясь - печатает исходные коды всех непроницательных программ, и больше ничего?
Она не может напечатать свой код, потому что тогда она одновременно приноцательная по определению, и непроницательная, потому что она печатает только непроницательные программы.
Она не может не напечатать свой код, потому что если она его вообще никогда не напечатает, то она непроницательная по определению, а значит, когда-то должна дойти до своего кода и напечатать.
Поэтому такой программы не существует.
Кажется, это доказательство немного проще, чем стандартное доказательство проблемы остановки. Меж тем оно тоже доказывает невозможность алгоритмического решения определенной задачи. Правда, понятие "решения задачи" в этом случае не столь удобное, как в проблеме остановки.
(по мотивам главы о самореференции в Metamagical Themas Хофштадтера)
(интересно сравнить с парадоксом Расселла в теории множеств, а также известной его формулировкой о брадобрее, который решил брить всех в городе, кто не бреет самого себя, и выходит парадокс, если задуматься, бреет ли он себя сам. В парадоксе Расселла сам рассматриваемый объект "множество всех множеств, которые не являются собственными элементами" существовать не может - его существование и приводит к парадоксу. В вопросе о программах выше в существовании множества всех программ, которые не печатают свой код, нет никакого парадокса и оно вполне себе существует. Но оказывается, что распечатать его невозможно, т.е. когда мы хотим им "воспользоваться", нам не дают. Так же и с брадобреем: множество всех жителей, которые не бреют самих себя, вполне себе существует. Но если мы попробуем к нему подойти и "воспользоваться", т.е. брадобрей хочет брить именно его - это не получается)
Она не может напечатать свой код, потому что тогда она одновременно приноцательная по определению, и непроницательная, потому что она печатает только непроницательные программы.
Она не может не напечатать свой код, потому что если она его вообще никогда не напечатает, то она непроницательная по определению, а значит, когда-то должна дойти до своего кода и напечатать.
Поэтому такой программы не существует.
Кажется, это доказательство немного проще, чем стандартное доказательство проблемы остановки. Меж тем оно тоже доказывает невозможность алгоритмического решения определенной задачи. Правда, понятие "решения задачи" в этом случае не столь удобное, как в проблеме остановки.
(по мотивам главы о самореференции в Metamagical Themas Хофштадтера)
(интересно сравнить с парадоксом Расселла в теории множеств, а также известной его формулировкой о брадобрее, который решил брить всех в городе, кто не бреет самого себя, и выходит парадокс, если задуматься, бреет ли он себя сам. В парадоксе Расселла сам рассматриваемый объект "множество всех множеств, которые не являются собственными элементами" существовать не может - его существование и приводит к парадоксу. В вопросе о программах выше в существовании множества всех программ, которые не печатают свой код, нет никакого парадокса и оно вполне себе существует. Но оказывается, что распечатать его невозможно, т.е. когда мы хотим им "воспользоваться", нам не дают. Так же и с брадобреем: множество всех жителей, которые не бреют самих себя, вполне себе существует. Но если мы попробуем к нему подойти и "воспользоваться", т.е. брадобрей хочет брить именно его - это не получается)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-08-26 04:30 pm (UTC)