Cantor's diagonal procedure
Jun. 1st, 2008 12:02 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109почитал Хайтина про halting problem. по-моему, это всё попытка побрить того, кто не бреется сам. не понимаю, как таким образом можно что-то доказать.
ну хорошо, а давайте возьмём множество не всех программ, а только всех, которые гарантированно halt. и тем же диагональным макаром построим новый number, которого в списке до того не было. будет нашa программа halting? ясен пень, она же только перебирает output других гарантированно halting программ. а почему же её в списке не было? чё мы этим доказали? по-моему, только то, что так нельзя рассуждать.
ну хорошо, а давайте возьмём множество не всех программ, а только всех, которые гарантированно halt. и тем же диагональным макаром построим новый number, которого в списке до того не было. будет нашa программа halting? ясен пень, она же только перебирает output других гарантированно halting программ. а почему же её в списке не было? чё мы этим доказали? по-моему, только то, что так нельзя рассуждать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2008-06-07 07:51 am (UTC)Хайтин (на самом деле он пересказывает построение Тьюринга) не вводит дополнительного требования "незацикливаемости" и без этого требования у Тьюринга получается более общий и фундаментальный результат, чем в твоём рассуждении.
В твоём рассуждении тоже получается осмысленный результат, не бессмыслица (как, как мне кажется, ты полагаешь). Я могу попробовать это объяснить в отдельных репликах. А то я уже напечатал довольно подробный текст и потерял, теперь буду кусками.