Cantor's diagonal procedure

[109]

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

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

Comments

[109.livejournal.com]

Ты про это ничего не говорил.

ну как же не говорил, всё время же: http://109.livejournal.com/413545.html?thread=1566825#t1566825

Но так у тебя тоже ничего не получится.

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

противоречие заключается в том, что процедура в сете одновременно есть (по определению сета) и нет (поскольку она выводит новый number, которого нет в сете). всё точно так же, как с computable numbers у хайтина. программа наша никогда не зацикливается, поскольку её input - это не тексты других программ, а конечные числа, вычисленные ими. точно так же, как у процедуры диагонализации, применяемой хайтиным.

про генерирование программ не понял, я про генерирование программ ничего никогда не говорил.

[faceted-jacinth.livejournal.com]

А, я тогда не понял.

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

Если ты про перебор конечного числа программ говоришь, то это уже совсем не непонятная теория множеств, это ты берёшь и пишешь программу на C#, которая как-то генерит программы (гарантированно останавливающиеся!), запускает их и записывает результаты. Если она в том числе и себя сгенерила и тупо запустила, значит, ты ошибся, потому что она зависнет и вовсе не будет гарантированно останавливающейся. Ты ошибся, когда процедуру генерации гарантированно останавливающихся программ писал, а не с теорией что-то не то.

Кстати, у меня вдруг сомнения появились, ты самое правильное доказательство невычислимости halting problem видел-то? Без диагонализации и прочего? Могу написать, если не видел.

[109.livejournal.com]

никто не генерит программы, откуда ты это взял, вообще? Cantor's diagonal procedure напускается на output. то есть output этих halting/not halting programs - это input для Cantor's diagonal procedure.

первый же результат запроса http://google.com/search?q=cantor%27s+diagonal+procedure+wiki гласит, что "in reality Cantor's diagonal procedure proves nothing", так что я явно onto something here.

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

[faceted-jacinth.livejournal.com]

никто не генерит программы, откуда ты это взял, вообще? Cantor's diagonal procedure напускается на output. то есть output этих halting/not halting programs - это input для Cantor's diagonal procedure.
---
Ты чо? Какой аутпут? Откуда он у нас возьмётся?

Чайтин, на секундочку, как раз undecidability of the halting problem вот так смешно доказывает, если ты не заметил.

И делает это буквально так: наша гипотетическая программа сама генерирует и получает результаты всех программ в лексикографическом порядке, если бы она действительно могла это сделать, то мы бы получили противоречие -- она бы сгенерила вычислимое число, которого нет в списке вычислимых чисел. Процедура генерации программ есть явно, вот она. Значит, невозможно построить процедуру проверки, которая а) вернёт результат работы независающей программы, б) вернёт единицу или ещё что-нибудь для зависающей (не зависнув сама!).

Вот, никакого input никакие мистические высшие силы чайтиновской программе не дают. Это сердце его доказательства.


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

Нет, ты неправильно всё понял, перечитай теперь статью ещё раз =).


Так это, на всякий случай, ты таки знаком с простым и понятным доказательством undecidability of the halting problem, без диагонального аргумента? В википедии не оно, почему-то.

PS: Я бы крайне не рекомендовал искать в интернетах фразы вроде "Эйнштейн был неправ!" и делать выводы.

[faceted-jacinth.livejournal.com]

Кстати, случай с фиксированным конечным множеством программ вообще говоря не столько про хальтинг проблем, сколько про некорректность фразы "первое число, которое нельзя описать менее чем двадцатью словами" (если воспринимать её как описание некоего числа).

Ты именно это пытаешься сделать, написать программу, которая перебирает какую-то часть программ фиксированной длины и что-то делает с их выводом; отлично, что она должна делать со своим собственным выводом, если она входит в этот список? И откуда она его должна взять: тупо запустить если, она зависает, а так можно постулировать произвольный, конечно.

[faceted-jacinth.livejournal.com]

Я всё-таки напишу правильное доказательство, потому что оно показывает, что на самом деле происходит в доказательстве Чайтина.

Итак, берём машину Тьюринга. Конкретный механизм, это важно, и я хочу подчеркнуть, что мы не говорим о "программах вообще", мы говорим предельно конкретно. Фиксируем способ записи программы нулями и единицами -- ну, там, фиксируем способ записи чисел префиксным кодом, записываем количество состояний, записываем длину алфавита, для каждого состояния записываем все переходы и так далее.

Предположим, что у нас есть машина тьюринга А, которая получает на ленте закодированную машину тьюринга, закодированное начальное состояние ленты и оставляет 1, если та МТ останавливается для тех данных, или 0, если нет. Но сама обязательно останавливается рано или поздно. Я буду писать A(M, L) = 1, если машина M останавливается на данных L.

Делаем машину А1(M) = A(M, M). То есть берём с ленты код машины, клонируем его и запускаем машину А. Ещё раз подчеркну, мы вполне конкретно это делаем, если у нас есть C# класс, реализующий машину тьюринга, мы вызываем у него конкретные методы "добавить состояние", "добавить переход" и так далее, дописывая небольшой кусочек кода, копирующий данные.

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

Запускаем А2(А2). Раз мы предположили, что А обязательно останавливается, то и А2(А2) остановится. Это значит, что А1(А2) выдала 0 (единственный способ для А2 не зависнуть). Это значит, что А(А2, А2) выдала 0. Это значит, что А2(А2) не останавливается. Получили противоречие, следовательно, такой машины А не может существовать и проблема останова undecidable.

Теперь, что делает Чайтин. Он точно так же предполагает, что у нас есть машина А, проверяющая останов данной ей машины на данной ей ленте. Но модифицирует её он по-другому. Он предполагает, что у нас есть два фиксированных состояния, первое и второе например, соответствующие выводу очередной цифры.

Он строит машину А1(M, n), которая патчит данную ей машину так, что та останавливается ровно после n проходов через первое или второе состояние, затем запускает А(M*, "") (на патченной машине, с пустой лентой), которая говорит, дойдёт ли M до n-той цифры, если да, то узнаёт n-тую цифру и выводит её, иначе выводит 0. Надеюсь, ты понимаешь, что это можно сделать, и не очень сложно (особенно если performance is not a worry).

Он строит машину А2(), генерирующую все возможные машины M_i в лексикографическом порядке, вызывающую А1(M_i, i) и выводящую отрицание очередного полученного значения (то есть проходящую через 0 если вернули 1 и наоборот).

Он запускает А2(). Дальше он, в статье, говорит много общих слов, которые действительно не очень убедительны. На самом же деле всё просто: по построению А2 в какой-то момент вызовет А1(А2, n), ну, с каким-то конечным n, номером самой А2. Полученный результат A1 инвертирует и возвращает как n-тый бит, это то же самое n. Теперь, по построению мы видим, что А2 не зависнет. Следовательно, А1(А2, n) выдаст именно тот бит, который выдаёт А2 на n-той позиции. Но А2 полученный бит инвертирует и выдаёт! Она должна выдать на n-том месте не тот бит, который она выдаёт на n-том месте, по построению! Получили противоречие. Значит, машина А пиздит -- либо зависая, либо выдавая неправильный результат (потому что "правильного" результата существовать не может).

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

[faceted-jacinth.livejournal.com]

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

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