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-01 03:59 pm (UTC)А с твоим аргументом не так вот что: когда ты говоришь, дескать, давайте возьмём множество гарантированно останавливающихся программ, ты говоришь a set, not the set, ты берёшь одно из таких множеств. Ну, например множество программ, где эн-тая печатает эн единиц. Или эн-тое натуральное число, неважно. Ты применяешь к выбранному множеству процедуру диагонализации и получаешь какое-то другое множество, тоже обладающее этим свойством, все программы в нём гарантированно останавливаются. В нём, конечно, есть программы, не входившие в первое множество, никакого противоречия в этом не возможно усмотреть.
Если же ты имеешь в виду _the_ set останавливающихся программ (я не очень понимаю, какой тогда смысл добавлять слово "гарантированно"), то, извини, его ты взять не можешь, потому что его не существует. Что, собственно, и доказывается Чайтиным и Тьюрингом. Причём ты не только знаешь, что его не существует, его несуществование больно бьёт тебя по голове как только ты пытаешься построить хотя бы его кусочек. Почитай про Работящего Бобра, уже среди машин Тьюринга с бинарным алфавитом и пятью состояниями (десять чисел от 0 до 5, блин!) есть приблизительно сорок штук, про которых как бы непонятно, останавливаются ли они вообще.
(no subject)
Date: 2008-06-01 04:32 pm (UTC)(no subject)
Date: 2008-06-01 04:54 pm (UTC)Там же не останавливающиеся программы рассматриваются, там рассматриваются программы, выводящие знаки какого-то числа. Многие из них выводят бесконечные числа, например пи, и, соответственно, не останавливаются, но нас это не очень расстраивает, нас расстраивает то, что мы не можем для данной конкретной программы сказать, выведет ли она очередной символ. То есть разные виды неостанавливания -- одно дело, когда наша программа раз в сто тактов выводит цифру и делает это сколь угодно долго, другое -- когда она что-то делает сколь угодно долго ничего не выводя.
Если мы среди них выберем только программы, выводящие конечные числа за конечное время, и применим диагональный аргумент к получившемуся множеству так же, как к оригинальному, то получим программу, выводящую _бесконечное_ число. Она этому множеству и не должна принадлежать как бы, всё в порядке.
(no subject)
Date: 2008-06-01 08:12 pm (UTC)да почему же бесконечное? перебираем конечное число программ, выводящих конечные числа за конечное время. получим программу, тоже выводящую конечное число за конечное время.
(no subject)
Date: 2008-06-01 08:47 pm (UTC)Неверзелесс, если ты попытаешься применить его аргумент к программам, выводящим конечные числа, то получишь программу, выводящую бесконечное число. И никакого противоречия, потому что у него противоречие возникает когда он как бы конструирует программу, которая с одной стороны должна принадлежать исследуемому множеству (потому что в него входят ВСЕ программы, удовлетворяющие признакам), а с другой -- не принадлежит по построению.
(no subject)
Date: 2008-06-02 01:29 am (UTC)очевидным образом, halting programs выводят конечные числа.
(no subject)
Date: 2008-06-01 05:34 pm (UTC)Во-первых, под "печатает очередной символ" видимо понималось что-то вроде "проходит через специальное состояние Принт0 или Принт1", а не в содержимом ленты он искался. С ответом такая интерпретация совпадает, по крайней мере =).
Ну вот, возьмём множество программ {M_i}, для которых верно, что для любого n существует k(M_i, n), такое что в течение k ходов они пройдут через (состояние Принт1 или Принт2) хотя бы n раз или остановятся. Пусть такое множество существует, хотя мы и не знаем (и не имеем формального способа узнать), какие программы в него входят. И значения k(M_i, n) мы тоже не знаем, и вообще это вариант невычислимой Busy Beaver.
Далее, это множество счётно, не правда ли? Ну, между конечной и счётной мощностью ничего нет точно, а мощнее счётного оно вроде как быть не может, потому что является подмножеством счётного множества (всех конечных программ).
Раз оно счётно, значит, существует биекция между ним и множеством натуральных чисел, то есть его можно упорядочить и перебирать элементы по очереди (хоть мы и биекции этой тоже не знаем).
Значит, где-то "существует" алгоритм, который используя эту неизвестную нам биекцию берёт первую программу из множества и n = 1, получает ответ, ксорит с 1 и выдаёт наружу, затем берёт вторую программу, получает ответ для n = 2, инвертирует и выдаёт, и так далее. И приходим к противоречию.
Как его интерпретировать? Можно сказать, что этого множества всё-таки не существует, for all conceivable purposes. С другой стороны, можно запретить говорить о "где-то существующих алгоритмах", особенно использующих какие-то биекции, которые могут представлять собой невычислимые функции (и в данном случае представляют, собственно). Или заметить, что если наш алгоритм не вызывает биекцию явно, чтобы получить очередную программу, а содержит их все в себе как бы захардкоженные (хотя мы и не знаем, какие именно и в каком порядке), то он, очевидно, имеет бесконечную длину и поэтому по праву не принадлежит рассматриваемому множеству конечных программ.
(no subject)
Date: 2008-06-01 08:24 pm (UTC)про проблемы с биекцией не понял. хайтин же тоже берёт какое-то множество, и "используя неизвестную биекцию" применяет канторовскую диагонализацию.
(no subject)
Date: 2008-06-01 08:49 pm (UTC)Если мы ограничимся каким-то конечным N, то проблема останова превращается в P=NP, насколько я понимаю.
(no subject)
Date: 2008-06-02 01:31 am (UTC)проблемы останова у нас нет, у нас есть проблема, что программа одновременно в списке и не в списке.
(no subject)
Date: 2008-06-02 09:02 am (UTC)Сформулируй уже чётко и ясно, какие программы ты заносишь в список, как получаешь новую и почему она тоже должна быть в списке, хотя и не может по построению.
(no subject)
Date: 2008-06-04 08:11 am (UTC)(no subject)
Date: 2008-06-04 08:16 am (UTC)(no subject)
Date: 2008-06-04 11:04 pm (UTC)(no subject)
Date: 2008-06-05 07:27 am (UTC)Вообще это глупо как-то. Я понимаю, что от оригинального доказательства веет наёбкой и кажется, что можно его чуть изменить и получить что-нибудь прикольное. Ну, как с капиллярным эффектом, очень он подозрительный, кажется, что проделав в нужном месте дырочку можно получить вечный двигатель.
Но самое интересное, и с проблемой останова, и с капиллярным эффектом, заключается как раз в том, что они на самом деле работают, они являются проявлениями глубоких общих законов, поэтому когда честно выписываешь детали своего очередного Хитрого Плана, вместе с формулками если нужно, оказывается, что он не работает. После нескольких попыток даже начинаешь понимать, почему, начинаешь ощущать контуры этого невидимого закона, мешающего сделать фигню.
Ну а если ты не хочешь так делать и предпочитаешь разводить руками, дескать, тут что-то подозрительное, то я не вижу особого смысла.
(no subject)
Date: 2008-06-05 07:39 pm (UTC)почему бесконечно, если у нас конечное количество halting programs (длиной не более нашей программы, которая производит диагональную процедуру)? мы останавливаемся, когда всех их переберём.
я хочу докопаться до истины, я только не понимаю, что можно делать с сетами, а что нельзя. мне кажется, что нельзя делать так, как хайтин, потому что если так делать, то можно доказать любую фигню, что я и пытаюсь показать.
(no subject)
Date: 2008-06-05 08:11 pm (UTC)---
Оппа.
Ты про это ничего не говорил. И это совсем не похоже на Чайтиновское доказательство.
Но так у тебя тоже ничего не получится. Если мы конечное количество программ перебираем, то всё же просто совсем. У нас есть наша перебирающая программа, которая в явном виде генерирует перебираемые программы, так? Мы прям написать её можем: вот у нас есть процедура, генерирующая программы (гарантированно останавливающиеся, как ты хочешь), вот процедура, запускающая n-тую, получающая n-тый бит и инвертирующая его.
Если генерирующая процедура НЕ генерирует в том числе и саму перебирающую программу, то никакого противоречия нет. Она в множество не входит по построению множества, всё хорошо.
Если генерирует, то что должна сделать проверяющая процедура? Если она тупо запустит программу, то тут же и зависнет. Ни о какой "гарантированной остановке" таким образом речи быть не может, получаем противоречие с предположением о том, что генерирующая процедура генерирует только останавливающиеся программы.
Или мы можем добавить в проверяющую процедуру кусок, который, увидев что ему скормили нашу программу, выведет, например, 1. Это, кстати, точный аналог "добавления утверждения как аксиомы" в стандартном Гёделевском доказательстве. Отлично, сама программа теперь выведет 0 на этом месте. Так мы её написали. Какой в этом глубокий философский смысл -- не знаю.
(no subject)
Date: 2008-06-05 08:27 pm (UTC)ну как же не говорил, всё время же: http://109.livejournal.com/413545.html?thread=1566825#t1566825
Но так у тебя тоже ничего не получится.
в каком смысле ничего не получится? получается противоречие, из которого следует, что так делать нельзя.
противоречие заключается в том, что процедура в сете одновременно есть (по определению сета) и нет (поскольку она выводит новый number, которого нет в сете). всё точно так же, как с computable numbers у хайтина. программа наша никогда не зацикливается, поскольку её input - это не тексты других программ, а конечные числа, вычисленные ими. точно так же, как у процедуры диагонализации, применяемой хайтиным.
про генерирование программ не понял, я про генерирование программ ничего никогда не говорил.
(no subject)
Date: 2008-06-05 08:44 pm (UTC)поскольку её input - это не тексты других программ, а конечные числа, вычисленные ими.
---
Нет, у неё инпута вообще нет. Она сама как-то строит исследуемый сет. Процедура построения должна быть в ней, явно.
Если ты про перебор конечного числа программ говоришь, то это уже совсем не непонятная теория множеств, это ты берёшь и пишешь программу на C#, которая как-то генерит программы (гарантированно останавливающиеся!), запускает их и записывает результаты. Если она в том числе и себя сгенерила и тупо запустила, значит, ты ошибся, потому что она зависнет и вовсе не будет гарантированно останавливающейся. Ты ошибся, когда процедуру генерации гарантированно останавливающихся программ писал, а не с теорией что-то не то.
Кстати, у меня вдруг сомнения появились, ты самое правильное доказательство невычислимости halting problem видел-то? Без диагонализации и прочего? Могу написать, если не видел.
(no subject)
Date: 2008-06-06 12:00 am (UTC)первый же результат запроса 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 можно вычислить программой длиной в один байт. ты согласен с этим заявлением?
(no subject)
Date: 2008-06-06 07:27 am (UTC)---
Ты чо? Какой аутпут? Откуда он у нас возьмётся?
Чайтин, на секундочку, как раз undecidability of the halting problem вот так смешно доказывает, если ты не заметил.
И делает это буквально так: наша гипотетическая программа сама генерирует и получает результаты всех программ в лексикографическом порядке, если бы она действительно могла это сделать, то мы бы получили противоречие -- она бы сгенерила вычислимое число, которого нет в списке вычислимых чисел. Процедура генерации программ есть явно, вот она. Значит, невозможно построить процедуру проверки, которая а) вернёт результат работы независающей программы, б) вернёт единицу или ещё что-нибудь для зависающей (не зависнув сама!).
Вот, никакого input никакие мистические высшие силы чайтиновской программе не дают. Это сердце его доказательства.
Если ты считал, что мы рассматриваем программы, у которых есть какой-то инпут, то всё понятно, откуда у тебя недоверие с непониманием взялись. Хаха, ну да, тогда и любой computable number можно программой длиной в один байт вычислить, записав его на ленту в виде инпута и исполнив хальт.
Нет, ты неправильно всё понял, перечитай теперь статью ещё раз =).
Так это, на всякий случай, ты таки знаком с простым и понятным доказательством undecidability of the halting problem, без диагонального аргумента? В википедии не оно, почему-то.
PS: Я бы крайне не рекомендовал искать в интернетах фразы вроде "Эйнштейн был неправ!" и делать выводы.
(no subject)
Date: 2008-06-06 07:46 am (UTC)Ты именно это пытаешься сделать, написать программу, которая перебирает какую-то часть программ фиксированной длины и что-то делает с их выводом; отлично, что она должна делать со своим собственным выводом, если она входит в этот список? И откуда она его должна взять: тупо запустить если, она зависает, а так можно постулировать произвольный, конечно.
(no subject)
Date: 2008-06-06 10:17 am (UTC)Итак, берём машину Тьюринга. Конкретный механизм, это важно, и я хочу подчеркнуть, что мы не говорим о "программах вообще", мы говорим предельно конкретно. Фиксируем способ записи программы нулями и единицами -- ну, там, фиксируем способ записи чисел префиксным кодом, записываем количество состояний, записываем длину алфавита, для каждого состояния записываем все переходы и так далее.
Предположим, что у нас есть машина тьюринга А, которая получает на ленте закодированную машину тьюринга, закодированное начальное состояние ленты и оставляет 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 равного её собственному номеру).
(no subject)
Date: 2008-06-06 12:31 pm (UTC)Во-вторых, всё-таки два случая надо рассмотреть. Если А2(А2) останавливается, то всё так, как я описал. Если А2 не останавливается, то она не останавливается именно потому, что ушла в бесконечный цикл когда А1 вернула 1. Потому что А1 останавливается всегда. Тогда, раз А1(А2) вернула единицу, значит, А(А2, А2) сказала, что А2(А2) останавливается, что как бы противоречит нашему предположению.
(no subject)
Date: 2008-06-01 08:08 pm (UTC)да, но хайтин-то делает то же самое. он берёт множество _всех_ computable numbers, а потом строит number, отличный от всех numbers в этом множестве. и на основании этого этот number считается uncomputable. точно так же можно сказать, что исходного сета не существует.
(no subject)
Date: 2008-06-01 08:51 pm (UTC)(no subject)
Date: 2008-06-02 01:33 am (UTC)(no subject)
Date: 2008-06-03 08:09 am (UTC)(no subject)
Date: 2008-06-05 07:42 pm (UTC)(no subject)
Date: 2008-06-07 07:51 am (UTC)Хайтин (на самом деле он пересказывает построение Тьюринга) не вводит дополнительного требования "незацикливаемости" и без этого требования у Тьюринга получается более общий и фундаментальный результат, чем в твоём рассуждении.
В твоём рассуждении тоже получается осмысленный результат, не бессмыслица (как, как мне кажется, ты полагаешь). Я могу попробовать это объяснить в отдельных репликах. А то я уже напечатал довольно подробный текст и потерял, теперь буду кусками.
(no subject)
Date: 2008-06-07 07:59 am (UTC)(no subject)
Date: 2008-06-07 08:01 am (UTC)(no subject)
Date: 2008-06-07 08:04 am (UTC)(no subject)
Date: 2008-06-07 08:09 am (UTC)Я понятно излагаю? Мне пока вроде всё понятно. Дай знать, если тебе нужны дополнительные пояснения.
(no subject)
Date: 2008-06-07 08:18 am (UTC)