Cantor's diagonal procedure

[109]

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

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

Comments

[109.livejournal.com]

Если мы среди них выберем только программы, выводящие конечные числа за конечное время, и применим диагональный аргумент к получившемуся множеству так же, как к оригинальному, то получим программу, выводящую _бесконечное_ число.

да почему же бесконечное? перебираем конечное число программ, выводящих конечные числа за конечное время. получим программу, тоже выводящую конечное число за конечное время.

[faceted-jacinth.livejournal.com]

Чайтин использует программы, выводящие бесконечные числа.

Неверзелесс, если ты попытаешься применить его аргумент к программам, выводящим конечные числа, то получишь программу, выводящую бесконечное число. И никакого противоречия, потому что у него противоречие возникает когда он как бы конструирует программу, которая с одной стороны должна принадлежать исследуемому множеству (потому что в него входят ВСЕ программы, удовлетворяющие признакам), а с другой -- не принадлежит по построению.

[109.livejournal.com]

хайтин использует всякие программы, halting и не halting.

очевидным образом, halting programs выводят конечные числа.