Newsgroups: relcom.sci.philosophy
Subject: Re: Чаитин лекция-2 (Столетие противоречий в математике)
From: "Alexandr Semеnоv"
Date: Sun, 14 Apr 2002 16:25:04 +0300
--------
Evgenij Barsukov пишет в сообщении <3cc96d87.146143037@news.kreonet.re.kr>
...
>Очень интересная статья, спасибо за перевод. Кстати
>хороший перевод получился как на мой вкус. Не поставить
> ли его на сайт в информационные статьи?
Спасибо, Евгений.
Про размещение на сайте - вам решать (я на него тоже иногда заглядываю и
мне казалось, вы его забросили). О качестве же перевода этой лекции могу
сказать следующее. Действительно оно лучше чем у первой " Хаос и сложность
в чистой математике..." Перевод первой лекции - ужасен. Его непременно надо
рихтовать. (я потерял ссылку на его оригинал в и-нете, но у меня он
сохранен как текст, желающим могу переслать)
>Не удивительно что не пришло много ответов, так-как чтиво явно не каждому
>по зубам.
Не знаю о зубах (изложено вороде популярно), но объем слегка "нетрадиционен"
для конференции.
Я думаю многие увидев размер 61, 59 Килосов, просто не стали смотреть,
а если и посмотрели, то не осилили до конца, хотя как мне кажется обе лекции
очень живые. Не в пример высокоумному бубнению, принятому в
отечественной литературе.
Кроме того, тема, опять же, "что-то там в носу", по популярности на
"парадокс близнецов", не тянет :)(
Я лично бросился искать Чаитина в И-нете ухватив всего одну реплику
в комментарии к статье в НГ-наука о знаменитом противоборстве
Арнольа с Бурбаки. Тот комментатор придавал анафеме Чаитенские
идеи, мол до чего мы докатились, а меня эта гиена мат-разврата жутко
заинтриговала.
Вы, наверное помните, что я обожаю подобные темы?!
Более того, я помню, что и вам, Евгений, вроде как эта тема небезразлична.
Я бы на вашем месте, еще, поискал бы статью тех английских физиков и
сравнил бы их идеи о творении вселенной из хаоса с вашей идеей
о "вероятностью творения".
>Лично мне нравится общая идея о возможности "расходимости" логики в больших
>системах, равно как и хвала "эксперементальной" математики. Однако с самими
>его доказательствами у меня проблемы. Конечно публичная статья не лучшее
>место чтобы объяснять суть доказательств. Возможно позже появатся сайты где
> это разъясняют более детально.
Обе лекции (особенно последняя, 2000 года для компьютерщиков - бизнесменов)
пробегают "галопом по европам". Имеются огромные дыры, которые приходится
принимать на веру.
Но Чаитин живописен, а тема _по_настоящему_ захватывающая.
Вариация на тема "Как, на самом деле, был изобретен компьютер"
вообще, как мне кажется, достойна подражанию и тиражированию.
Я думаю это полезно превратить в научный миф (люди же кроме
мифов ничего не воспринимают)
Что же касается более подробных разъяснений то я сомневаюсь
о возможности их получения.
На сайте самого Чаитина
http://www.cs.umaine.edu/~chaitin/index.html
есть еще кое-какой материал, но все детали - в его книгах,
которые вряд ли будут изданы у нас.
Кому это интересно?
А в англоязычном интернете им мешает появится принцип
неприкосновенности авторского права.
>Но из того что я увидел мне почудилось следующее
>1) генерируем случайную програму N бит
>2) вычисляем вероятность ее остановки (не понял для какого базиса данных?
>Данные уже вложены в случайную цепочку? Т.е. они тоже случайны?)
>3) верояность остановки получается абсолютно случайным числом, хотя ее
>вычисление алгоритмично.
Идея вот в чем.
Пусть P это текст программы (конечная цепочка символов).
Давайте зафиксируем для всех программ один и тот же вход (число Z) и
обозначим невычислимую функцию G так:
1, если программа P остатанвивается при входе Z
Gz (P) = {
0, если программа Р не останавливается при входе Z
Совсем просто получить функцию L, которая вычисляет целое число S
- длину программы, например, в битах.
S = L( P )
Тогда, если бы G была вычислима, то Омега Чаитина вычислялась бы так
беск-сть
О = Сумма { G(P) * 2^(-L(P)) }
1
Давайте определим математический смысл этой Омеги.
Коль скоро программа это цепочка бит, то давайте выпишем
все возможные цепочки в порядке возрастания их длинны.
Я их расположу не в цепочку а нарежу в пирамиду согласно
их длинен.
S=1... 1 0
S=2... 00 01 10 11
S=3... 000 001 010 011 100 101 110 111
И так далее
Теперь, рассмотрим каждую цепочку как программу для какой-то машины.
Зафиксировав машину и вход для нее мы определяем для каждой программы
остановиться она или нет.
Имея в одной руке конкретную машину, в другой конкретную программу
для нее, а в третьей ... скажем... руке, исходные данные, мы всегда получаем
ответ:
или 1 - остановиться,
или 0 - не остановится.
Третьего не дано.
Это объективный математический факт.
Отлично.
Теперь давайте нашу пирамиду перепишем так. Если данная
цепочка-программа остановиться, значит пишем на ее месте 1.
Если не остановиться, значит пишем 0. Это как бы результат применения
функции G(P) которую на самом деле применить нельзя.
(но "в ручную", исследовав каждый отдельный случай можно! Почему же нет?
Если потратить бесконечность, то можно)
Допустим это будет так:
S=1 ... 0 0
S=2 ... 1 0 0 1
S=3 ... 0 1 0 0 0 1 0 1
И так далее
Теперь давайте оценим чему равна вероятность того, что выбранная наугад
программа длинной не более 3 бита остановиться? Очевидно отношению общего
числа возможных цепочек к числу тех цепочек, которые остановились. В нашем
случае это 5/14.
Это совершенно конкретное число независимо от того как мы это получили.
Правильно?
Но если мы теперь продолжим эту пирамиду до бесконечности, то отношение
числа останавливающихся программ к общему числу программ хотя и будет
меняться, но останется СОВЕРШЕННО КОНКТЕТНЫМ ЧИСЛОМ в интервале
от 0 до 1. И предел этого отношения на бесконечности и будет вероятностью
того,
что взятая наугад программа (с наугад полученной длинной) остановиться.
Именно это невычислимое число формула Чаитина и "вычисляет".
Меня смущало в ней то, что более длинные программы вносят меньший вклад в
вероятность остановки, чем короткая. Об этом и шел разговор на мат.
конференции.
Но это уже детали.
Конечно Омегу нельзя вычислить. Но это все же совершенно конкретный
математический объект. И этот объект обладает рядом совершенно конкретных
свойств.
Математика знакома с такого рода невычислимыми объектами.
Например "странная" функция Дирихле определяется так:
1, если X рациональное число
Y= {
0, если X иррациональное число
Функция всюду определена, для любого Х. Но формулы для ее вычисления
не существует. А жаждущие выпучить глаза от удивления могут попробовать
построить ее график (а за одно и производную)... :)
Но это функция! Функция во всех ее смыслах!
Не менее странным мат. объектом является и Омега Чаитина.
Это число не вычислимо, но оно обладает одним очень ценным свойством.
(кстати, это число должно быть непременно иррациональным, а как это
доказать я не вижу)
Как Чаитин доказывает абсолютную нормированность Омеги я тоже не
уловил из того что он рассказал в обеих лекциях.
Скорей всего через математическую нередуцируемость (которая, в свою
очередь, следует из невычислимости). Действительно, если бы это число
в каком-либо основании было не норимрованным, то мы могли бы в этом
основании его записать компактнее чем в другом. А это бы
противоречило бы принципу несжимаемости или полной
хаотичности данного числа.
В этом, как я понял, вся тонкость.
Но масса вопросов осталась за кадром.
>При этом у меня возникает вопрос "где-же мясо"? Мы взяли на входе абсолютно
>случайное числы, сделали с ним неслучайные манипуляции и получили на выходе
>опять абсолютно случайное число. Ну и что - а разве могло быть иначе?.
> Можно поступить проще, взять случайную выборку на 1024 бит, взять ее
первую
> половину и умножить на вторую половину. Потом взять первую половину и
> разделить на вторую половину. Из обеих результатов слепить новую выборку
> 1024 бит. Она будет так-же случайна как и начальная, хотя все манипуляции
> были сделаны сугубо причинно. Не является ли это эквивалентом логики
> Чаитина?
Первоначально я тоже так подумал. Но "на вход" он кладет регулярную
математику вместе с проблемой остановки (или неполнотой), а на выходе
он получает число, которое нормировано во всех основания. Абсолютный хаос.
Ведь могло случиться так, что такого абсолютно нормированного числа в
математике вообще не существует!
А он, его откопал (как сам утверждает).
Шаманство с подбрасыванием монет возникает из-за того, что нам надо ВЫБРАТЬ
одну конкретную программу из бесконечного числа программ закрыв глаза.
Говоря о вероятности остановки нам надо получить конкретную программу
не зная что это за программа и какова ее длинна.
Мы должны суметь сделать выбор, должны ткнуть пальцем и сказать
"дайте одну из многих".
Для этого и возникает эта игра с монетой.
А сама Омега - это отношение общего числа программ к числу
останавливающихся.Никакой привнесенной извне (из нашего мира)
случайности в нем нет.
Я так понял, это далеко не единственный способ найти полный хаос в
регулярной математики. Например, в первой лекции он использует другую
математическую неразрешимость - отсутствие общего решения для
диофантовых уравнений высших порядков.
(для этого он там строит монства в 17 000 переменных! )
Из материалов лекций тяжело судить о надежности его методов. Но
свои идеи он двигает с 60-70-х годов. И задвинуть их пока никто
не смог (а желающие наверняка есть, хотя не так много как на
СТО или ОТО :).
Если бы могли, уже бы задвинули (у него там были ошибки но
они несущественны и он их устранил).
В общем, вполне возможно, что он прав!
:)
С уважением, А. Семенов
Built by Text2Html