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 programs (длиной не более нашей программы, которая производит диагональную процедуру)? мы останавливаемся, когда всех их переберём.

я хочу докопаться до истины, я только не понимаю, что можно делать с сетами, а что нельзя. мне кажется, что нельзя делать так, как хайтин, потому что если так делать, то можно доказать любую фигню, что я и пытаюсь показать.

[faceted-jacinth.livejournal.com]

(длиной не более нашей программы, которая производит диагональную процедуру)
---
Оппа.
Ты про это ничего не говорил. И это совсем не похоже на Чайтиновское доказательство.

Но так у тебя тоже ничего не получится. Если мы конечное количество программ перебираем, то всё же просто совсем. У нас есть наша перебирающая программа, которая в явном виде генерирует перебираемые программы, так? Мы прям написать её можем: вот у нас есть процедура, генерирующая программы (гарантированно останавливающиеся, как ты хочешь), вот процедура, запускающая n-тую, получающая n-тый бит и инвертирующая его.
Если генерирующая процедура НЕ генерирует в том числе и саму перебирающую программу, то никакого противоречия нет. Она в множество не входит по построению множества, всё хорошо.
Если генерирует, то что должна сделать проверяющая процедура? Если она тупо запустит программу, то тут же и зависнет. Ни о какой "гарантированной остановке" таким образом речи быть не может, получаем противоречие с предположением о том, что генерирующая процедура генерирует только останавливающиеся программы.

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

[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) останавливается, что как бы противоречит нашему предположению.