Cantor's diagonal procedure

[109]

почитал Хайтина про halting problem. по-моему, это всё попытка побрить того, кто не бреется сам. не понимаю, как таким образом можно что-то доказать.

ну хорошо, а давайте возьмём множество не всех программ, а только всех, которые гарантированно halt. и тем же диагональным макаром построим новый number, которого в списке до того не было. будет нашa программа halting? ясен пень, она же только перебирает output других гарантированно halting программ. а почему же её в списке не было? чё мы этим доказали? по-моему, только то, что так нельзя рассуждать.

Comments

[faceted-jacinth.livejournal.com]

Ой, во-первых опечатался: Делаем машину А2(М), которая вызывает А1(М) и, если та вернула 1 (то есть сказала, что M(M) останавливается), то уходит в бесконечный цикл.

Во-вторых, всё-таки два случая надо рассмотреть. Если А2(А2) останавливается, то всё так, как я описал. Если А2 не останавливается, то она не останавливается именно потому, что ушла в бесконечный цикл когда А1 вернула 1. Потому что А1 останавливается всегда. Тогда, раз А1(А2) вернула единицу, значит, А(А2, А2) сказала, что А2(А2) останавливается, что как бы противоречит нашему предположению.