Newsgroups: relcom.sci.philosophy
Subject: Проблема Остановки в замкнутой Вселенной все же неразрешима!
From: "Alexandr Semеnоv"
Date: Tue, 23 Jul 2002 01:29:10 +0300
--------
Здравствуй ALL и Андрей, который ...
Богатырев,
который...
> в Калифорнии.
у которого...
>... высшее математическое образование.
которого...
>Когда-то давно ... учили ДОКАЗЫВАТЬ теорему Гёделя
>И нумеровать машины Тьюринга.
и у которого GEB, ...
>... английский вариант стоит ... в шкафчике.
И о чем, тогда мы спорим ? :)
Ладно бы мы не понимали разницы между реальностью и математической
абстракцией. Для такого понимания, как утверждают профессиональные
математики, нужна некоторая "математическая культура" которая у простого
смертного отсутствует, если у него нет соответствующего образования (я в
этом смысле мещанин во дворянстве - жалкое зрелище). Но у вас, я так понял,
есть! О чем же тогда спор?
Поэтому давайте определимся с позициями. В справедливости теоремы Тьюринга
об остановки ни вы ни я не сомневаемся. В том, что для всякой конечной
машины проблема остановки разрешима, ни вы ни я так же не сомневаемся. Тогда
в чем противоречие?
Я позволю себе бестактность предположить.
"Спор", возможно, в том, что вы обнаружили "оригинальную идею", а я ее
таковой (ну естественно!) не считаю (мое - оригинально, не мое - банально:)
Конечно, я мог бы найти смелость признать, что ваша идея в последние сутки
крайне заинтриговала меня. Но это буден не совсем прилично.
Поэтому сей постин я построю следующим образом. Сначала я, естественно,
объясню почему ваша идея - чистейшей воды банальность (типа я на нее
не обратил серьезного внимания потому что и обращать на нее нечего!).
Далее я попробую ею (так уж и быть) проиграть типа: "ну-ка ну-ка ... молодой
человек... гм... а в этой вашей ерунде... что-то есть. . ." А в конце, я
надеюсь
вам подсунуть крайне изящную свинью. Я все же докажу, что по большему
счету, вы все равно не правы. Проблема остановки в любом случае
неразрешима!
И так-с начнем.
Сначала о банальности.
Я сейчас буду высказывать здесь прописные истины, а вы будете меня
поправлять (я думаю придраться будет к чему).
Что мы называем функцией в математике? Функция или отображение это такое
отношение между множеством А и В, при котором каждому элементу из множества
В соответствует не более чем один элемент из А.
Задать (определить) такое отношение можно разными способами. Вот один из
них. Назовем его "крестики-нолики" (Тьюринг, если вы читали очерк Долмачева,
любил в юности поиграть в нее на бесконечном поле. Но вполне возможно вы об
этом читали из какого-нибудь другого источника, более обширного... Возможно
у
вас в шкафчике стоит биография Тьюринга, которую еще не перевели на русский
язык и даже и не помышляют переводить.. извините, но я сс завистью
представляю этот ваш шкафчик, так и стоит он у меня перед глазами...
посередине знойной Калифорнии... :).
И так, строим таблицу где столбцы - элементы множества В, а строки элементы
множества А. В ячейках такой таблицы ставится "нолик" если отношение между
элементам данной строки (из А) и элементом данного столбца из В отсутствует
и
ставиться "крестик" если отношение существует. В случае функционального
отношения (то есть отображения) такая таблица будет иметь ту особенность,
что в каждой строке будет не более чем один "крестик". Если в строке
"крестика" вообще нет, то говорят что для данного аргумента функция не
определена.
Не надо иметь много ума, чтобы представить себе такую таблицу для двух
конечных множеств. Но нужно обладать пресловутой "математической культурой"
чтобы представить себе такую таблицу для двух бесконечных множеств как
актуально законченную конструкцию (то есть уже определенную или заданную).
Такая таблица будет бесконечной как в ширину так и в длину и говоря о том,
что мы имеем некоторую функцию на двух бесконечных множествах f: A ->B, мы
имеем в виду что кто-то построил эту бесконечную таблицу. Очевидно Господь
Бог.
Вообще то, иметь в руках некоторую конструкцию, значит иметь возможность ею
манипулировать. И здесь речь идет уже не о эстетическом созерцании и
культурном наслаждении, а о пользе и выгоде. И вот в этом смысле бесконечная
таблица, построенная Богом малополезна для нас, людей.
Именно поэтому у некоторых математиков возник вопрос о каким-либо другим
способе задать функцию, более конструктивно. То есть их стал мучить вопрос:
можно ли эту нефинитную конструкцию свернуть во что-то конечных размеров?
"Можно!" - Ответили отцы-основатели Черч-Пост-Тьюринг-Марков и каждый
предложил свое определения алгоритма или вычислимой в интуитивном смысле
функции. Правда на них это дело не закончилось. После того как появились
рекурсивные функции, машина Поста и машина Тьюринга, а так же нормальный
алгоритм Маркова, тут же следом появились подражатели и предложили такие
экзотические устройства как "клеточный автомат", "бильярдный вычислитель" и
"машина с неограниченным регистром" (как не вспомнить Охоту на Снарка Л.
Кэрролла? Был отряд на подбор, Первым шел Билетер, дальше следовал шляпный
Болванщик ... : ). Но эта кавалькада уже никого не впечатлила.
Обо всем этом стоило упоминать только для того, чтобы сказать, что всякой
машине Тьюринга (как и прочим воплощениям понятия "быть вычислимым" из
рук человеческих) мы можно поставит в соответствие некоторую бесконечную
таблицу в виде "крестиков-ноликов" из рук божих...
Теперь давайте построим произвольную функцию над конечными множествами
в виде таблицы. Такой труд человеку посилен.
Давайте договоримся,что эта функция будет определена не для всех аргументов.
Некоторые строчки будут пустыми (вернее заполнены только "ноликами").
Построив все это зададимся вопросом: можно ли имея такую таблицу выяснить
для каждого аргумента определена ли для него функция, или нет? Разумеется
можно.
Вот эта процедура:
Мы идем вдоль строчки принадлежащей данному аргументу и дойдя до конца
обнаруживаем что крестик не встретился. Значит функция не определена.
В противном случае, если крестик где-то попался, значит функция определена.
И так, для таблицы "крестики-нолики" существует разрешающая процедура.
Но если мы предположим, что существует более компактный способ задать эту же
функцию в виде программы машины Тьюринга, то очевидно и для нее должна
существовать подобная разрешающая процедура. То есть должна быть программа,
которая бы выясняла определена данная функция для данного аргумента или нет.
Что произойдет с программой если вычисляемая ею функция для данного
аргумента не определена? Это значит что она зациклится.
Вопрос "определена- не определена" для программы
означает "зациклиться- не зациклится"
Попробуем такую процедуру построить.
Программа, вычисляющая функцию над конечными множествами на машине
Тьюринга отличается тем, что ей не нужна бесконечная лента. То есть
существует
такой диапазон ленты, за пределы которой головка никогда не должна выходить
в
процессе вычисления. Тогда факт выхода головки за этот предел и будет
означать что программа зациклилась (вернее вылетела, оверфлоу!).
Но только ли это? Можно представить ситуацию когда головка никогда и не
выйдет за пределы ленты, но будет бегает по кругу внутри нее бесконечно.
Однако это означало бы то, о чем вы, Андрей, с таким энтузиазмом говорите.
Бесконечно бегая по конечному участку ленты с конечным числом ячеек,
записывая в них символы из конечного алфавита и имея конечное число
внутренних состояний машина рано или поздно повториться. Значит, построив
процедуру, которая следила бы за этими двумя событиями (выход за пределы
ленты и повторение состояния системы) можно однозначно понять зациклилась
программа (вычислима ли функция при данном аргументе) или нет.
Это разрешающая процедура ибо обязательно произойдет одно из двух событий.
Либо программа остановиться и выдаст ответ, либо проверяющая процедура
выдаст сообщение что программа вылетела или зациклилась.
Итак, разрешающая процедура для подобных программ существует.
Но было бы куда удивительней, если бы это было не так! Ведь мы говорим об
одной и той же функции только заданной двумя разными способами. И коль один
способ позволяет что-то сделать, то должен позволять и другой. И наоборот.
Если нельзя сделать одним, значит нельзя и другим.
Так например, для бесконечной таблицы предложенная ранее для конечной
таблицы разрешающая процедура не сработает, потому как, если функция
действительно не определена на некотором аргументе, то нам придется
двигаться вдоль его строчки бесконечно долго. Аналогичная ситуация и для
программ. Нельзя построить некую общую процедуру которая бы определила
зациклиться ли программа или нет при некоторых данных на входе.
Вот это я и имел в виду когда говорил:
> ... для конечных машин вообще
> НЕ СУЩЕСТВУЕТ НИКАКИХ ПРОБЛЕМ.
> Всякая функция, заданная на конечных множествах может быть представлена
> как ТАБЛИЦА КОНЕЧНЫХ РАЗМЕРОВ. О каких проблемах тут вообще может
> идти речь?!
Но это так, если смотреть на проблему с точки зрения математики.
Насколько я понял, Андрей, вам эта сторона не то что неизвестна (каюсь что
пытался просветить), но даже неинтересна. То есть "радость открытия" может
быть направлена в два других русла:
1 Чисто прикладное.
А ведь действительно, никто никогда и не пытался снабдить компиляторы хоть
какой-нибудь проверкой на зацикливание! Пускай не на все случаи но на
некоторые ведь можно! Не потому ли что все были слишком загипнотизированы
результатами Тьюринга?
2. Чисто философской.
Если наша Вселенная на самом деле имеет конечные размеры (о чем можно
спорить до опупения) то Проблема Остановки оказывается совершенно надуманной
математиками проблемой (и положенная им раз в четыре года премия - им не
положена! Отобрать, у стервецов, и отдать философам! ). В общем эта проблема
оказывается по ту сторону реальности, а потому как бы отменяется....
Разберемся с первым вопросом. И так процедура Богатырева следит за двумя
событиями. Переполнение и петли. Если сообщением "оверфлоу!" ни кого не
удивишь, то замкнутые цикл или петли в алгоритмах вылавливать никто не
пробовал.
Здесь хорошо бы выяснить какие ресурсы нам понадобятся для того чтобы
отследить подобную петлю.
Предположим простейший случай. Имеется переменная, которая занимает N бит
памяти и от значения которой зависит выход из цикла. Тогда в худшем случае
нам придется запомнить 2^N состояний этой переменной то есть следует иметь
N*2^N бит памяти для хранения всей предыстории. Теперь, если внутри цикла
существeт еще одна переменная, которая каким-то образом влияет на ключевую
переменную, то теперь нам надо следить и за ней. В общем случае, если на
результат цикла будет влиять m переменных, по N бит каждая, то нам
потребуется m*N*2^N бит памяти (если я нигде не ошибаюсь)
И это в том случае, если речь идет об одном цикле. Интересно было бы
рассмотреть случай цикла вложенного в цикл. Но одно пока ясно. Проверяя
программу на зацикливание мы не сможем обойтись памятью меньшей чем
необходимо самой программе.
Поэтому, как мне кажется, для отслеживания циклов даже в очень простой
программе потребуются значительные ресурсы памяти. И это делает достаточно
сомнительным вопрос о том насколько подобная проверка интересно с точки
зрения практического применения. Хотя... если мы увеличиваем число
переменных,
то количество памяти необходимое под процедуру Богатырева растет линейно.
Однако если мы будем увеличивать разрядность переменных, то мы получим
пресловутую NP-зависимость со всеми вытекающими отсюда ужасами.
Но мне куда интереснее другой, философский момент.
Поразмыслив над ним, я, кажется, натолкнулся на изумительную идею.
Я утверждаю, что если мы живем во Вселенной ограниченных размеров, то
существует некоторое множество программ, для которых процедура Богатырева не
сработает и утверждение о том, что не для всякой программы можно определить
остановиться ли она или нет остается в силе.
Назовем это в шутку теоремой Семенова.
Действительно. Давайте предположим, что вселенная состоит из Z частиц (Z - c
некоторых пор мое любимое число) и поэтому мы не можем запустить в ней
программу, для вычисления которой нужен объем памяти более чем Z бит. Теперь
допустим, программируя некоторую функцию, мы всегда встраиваем в нее
процедуру Богатырева делая ее тем самым всюду определенной. Это значит, что
если для вычисления некоторого значения функции по некоторой программе, нам
нужно m бит памяти хотя бы под одну "сомнительную переменную", то теперь,
снабдив программу процедурой Богатырева нам потребуется еще по крайней мере
m*2^m бит памяти для контроля этой переменной. Легко понять, что
в ограниченной Z вселенной существует такое граничное R, что Z=R + R*2^R
(скромно назовем его "радиус Семенова":). То есть любое число, большее R
определяет такой объем памяти, при котором если еще и можно вычислить
значение функции внутри данной вселенной, но уверенно проверить ее на
зацикливание уже невозможно. Тогда все программы, требующие для
вычисления памяти большее чем R окажутся, хотя и вычислимы, но
будет неопределимы в смысле зацикливания. То есть все возвращается
на круги своя.
Не всякую программу можно проверить зациклилась она или нет.
Более того. Я даже рискнул бы сей тезис распространить на более скромную
систему чем Вселенная. Например, на любой компьютер с конечной памятью.
На вопрос как его зациклить так, чтобы он сам об этом не догадался есть
простой ответ. Надо узнать объем его памяти и построить такой длины петлю,
чтобы в памяти компьютера она поместилась, но для отлавливания ее
процедуре Богатырева памяти не хватило. И он, компьютер, сам никогда
о том, что его зациклили, "не догадается"!
Какой изящный "бумеранг", не правда ли?!
Если мы заранее определимся с памятью, то получим дырку в виде недостатка
памяти для процедуры Богатырева. Но если мы не станем определяться с
границами, то получим бесконечность и все равно получим дырку в виде теоремы
Тьюринга!
В любом случае мы получим дыру.
Или я не прав?
:)))
А. Семенов
Built by Text2Html