Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 40 comments