Алгоритмическая теория информации… на случайности.
Добавлено: Сб май 16, 2009 10:43 amСтатья Грегори Дж.Чейтин. Полный текст : http://www.ega-math.narod.ru/Nquant/Random.htm
Эпиграф: «Невозможно доказать, конечное или бесконечное число решений имеет каждое уравнение из семейства алгебраических уравнений: ответ варьирует случайным образом, и, следовательно, не может быть найден с помощью математического рассуждения»
Что может быть бесспорнее того факта, что 2 плюс 2 равняется 4? Со времён древних греков математики считали, что более несомненной вещи, чем доказанная теорема, не сыскать. Действительно, математические утверждения, истинность которых может быть доказана, часто считались более надёжным основанием для системы мышления, чем любой моральный или даже физический принцип. Немецкий философ и математик XVII века Готфрид Вильгельм Лейбниц считал возможным создать «исчисление» рассуждений, которое когда-нибудь позволит улаживать все споры с помощью слов: «Давайте вычислим, господа!». К началу нашего столетия прогресс в разработке символической логики дал основание немецкому математику Давиду Гильберту заявить, что все математические вопросы в принципе разрешимы, и провозгласить окончательную кодификацию методов математического рассуждения.
В 30-е годы нашего столетия этот оптимизм совершенно развеялся под влиянием удивительных и глубоких открытий К. Гёделя и А. Тьюринга. Гёдель доказал, что не существует системы аксиом и методов рассуждения, охватывающей все математические свойства целых положительных чисел. Позднее Тьюринг облёк остроумные, но сложные гёделевы доказательства в более понятную форму. Как показал Тьюринг, гёделева теорема о неполноте эквивалентна утверждению, что не существует общего метода для систематического принятия решения о том, остановится ли когда-нибудь компьютерная программа, т.е. приведёт ли она когда-нибудь компьютер к остановке. Разумеется, если некоторая конкретная программа приводит к остановке компьютера, этот факт легко может быть доказан непосредственным выполнением этой программы. Трудность заключается в доказательстве того, что произвольно взятая программа не останавливается.
Недавно мне удалось сделать ещё один шаг по пути, намеченному Гёделем и Тьюрингом. Преобразовав некоторую конкретную компьютерную программу в алгебраическое уравнение такого типа, который был знаком ещё древним грекам, я показал, что область чистой математики, известная под названием теории чисел, содержит в себе случайность. Это исследование демонстрирует, говоря словами Эйнштейна, что Бог ПОРОЙ использует целые числа для игры в кости.
Полученный результат, входящий составной частью в то, что было названо алгоритмической теорией информации, не является причиной для пессимизма; он не вносит в математику анархию. (В самом деле, большинство математиков продолжают работать над своими проблемами, как и раньше.) Он означает лишь, что в некоторых ситуациях должны применяться математические законы особого рода — статистические. Подобно тому как физика не в состоянии предсказать, в какой именно момент распадётся данный атом радиоактивного вещества, математика порой бессильна дать ответ на некоторые вопросы. Однако физики могут надёжно предсказать средние значения физических величин, отнесённые к большому количеству атомов. Математики в некоторых случаях должны, вероятно, ограничиваться таким же подходом.
………………….
Но каким же образом теорема Гёделя о неполноте, проблема остановки Тьюринга и моя работа влияют на математику? Большинство математиков не обращают внимания на эти результаты. Конечно, в принципе они согласны, что любая конечная система аксиом неполна, но на практике они игнорируют этот факт, как непосредственно не относящийся к их работе. Но иногда, к сожалению, его нельзя игнорировать. Хотя в исходном виде теорема Гёделя казалась применимой лишь к необычным математическим предложениям, не имеющим практического интереса, алгоритмическая теория информации показала, что неполнота и случайность являются естественными и распространёнными повсюду свойствами. Это подсказывает мне, что следует более серьёзно относиться к возможности поиска новых аксиом относительно целых чисел.
Тот факт, что многие математические проблемы оставались веками и даже тысячелетиями нерешёнными, похоже, подтверждает мою точку зрения. Математики непоколебимо стоят на том, что причина неудач в решении подобных проблем заключена только в самих проблемах, но не заключается ли она в неполноте системы их аксиом? Например, вопрос о том, существуют ли нечётные совершенные числа, не поддаётся решению со времён древних греков. (Совершенным называется число, равное сумме своих делителей, исключая само это число. Например, 6 — совершенное число, поскольку 6=1+2+3.) Не может ли быть так, что утверждение «Не существует нечётных совершенных чисел» недоказуемо? Если это так, то не лучше ли принять его за аксиому?
Большинству математиков это предположение может показаться смехотворным, но для физика или биолога оно не выглядит столь уж абсурдным. Для тех, кто работает в эмпирических областях науки, основным критерием, позволяющим судить о том, следует ли рассматривать некоторое суждение как основание теории, служит полезность этого суждения, а вовсе не обязательно его «самоочевидная истинность». Если имеется много догадок, которые можно обосновать обращением к некоторой гипотезе, учёные-эмпирики принимают эту гипотезу. (Из несуществования нечётных совершенных чисел, по-видимому, не следует важных выводов, и, согласно этому критерию, такая аксиома не является полезной.)
На самом деле в некоторых случаях математики в своей работе опираются на недоказанные, но полезные предположения. Например, так называемая гипотеза Римана, хотя она никогда не была доказана, часто считается верной, потому что на ней основано много важных теорем. Более того, эта гипотеза была эмпирически проверена с помощью самых мощных компьютеров, и ни один опровергающий её пример не был найден. Компьютерные программы (которые, как я уже сказал, эквивалентны математическим утверждениям) проверяются таким же способом — тестированием некоторого числа вариантов, а не строгим математическим доказательством.
Существуют ли проблемы в других областях науки, для решения которых был бы полезен этот экскурс в основания математики? Я думаю, алгоритмическая теория информации может применяться в биологии. Регуляторные гены развивающегося зародыша являются по существу вычислительной программой построения организма. «Сложность» этой биохимической компьютерной программы можно, как мне думается, определить в терминах, аналогичных тем, что я развил при квантификации информационного содержания Ω.
Хотя Ω совершенно случайна (или бесконечно сложна) и никогда не может быть вычислена точно, её можно аппроксимировать с произвольной точностью, если в распоряжении имеется бесконечный отрезок времени. Мне кажется, что «сложность» живого организма может быть приближена таким же образом. Последовательность Ωn, аппроксимирующую Ω, можно рассматривать как метафору эволюции, и, возможно, она содержит зерно математической модели, описывающей эволюцию «сложности» биологического организма.
В конце своей жизни Дж. фон Нейман призвал математиков заняться созданием абстрактной математической теории происхождения и эволюции жизни. Эта фундаментальная проблема, подобно большинству проблем такого масштаба, бесконечно трудна. Возможно, алгоритмическая теория информации позволит найти путь, по которому следует идти.
Этой работе 20 лет. Из последних публикаций, могу предложить лекцию В.И.Арнольда «С ложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств» ( http://elementy.ru/lib/430178/430281 )
Одна выдержка из лекции В.И.Арнольда: «Утверждение состоит в том, что вот этот логарифм или, наоборот, геометрическая прогрессия, обратная функция, — распределены их значения, вообще значения, хаотическим образом. Оказывается... нарисуем график для обычных картинок... ну там вот есть какая-нибудь функция... ну или там логарифм... вот он имеет какой-нибудь гладкий график вот... в обычном случае... А в нашей арифметической задаче оттого что мы берем остатки от всего этого, то оказывается, получается функция, у которой график ведет себя вот так. Безобразный график получается, хаотический. Он не непрерывный, конечно, это конечное число точек, это облако точек некоторое. Но если нарисовать этот график аккуратно, то есть одна точка здесь, одна здесь, получается случайный набор точек на плоскости.
В каком смысле он случайный? Это надо определять. Что такое случайность, что такое случайный набор... Все это можно сделать, проверить, посчитать... Я вот занимался когда-то с Яковом Борисовичем Зельдовичем случайностью распределения галактик и скопления галактик во Вселенной и применял потом здесь, в этой задаче, те же самые критерии, при помощи которых определяли, случайно галактики распределены или нет, можно и к этим точкам. Удовлетворяют всем критериям, по которым Зельдович считал, что галактики случайно в какой-то области распределены... Так и здесь: те же самые критерии можно применить, и получается, что это случайные точки.
Так вот теперь спрашивается: а где брать случайные точки вообще? В криптографии очень нужны случайные точки — для того чтобы код делать случайный... И как их получать? И вот я сейчас хочу рассказать... эта теория, про которую я здесь рассказываю, в частности дает некоторые очень странные алгоритмы построения случайных последовательностей.
Я придумал такие алгоритмы для разных других задач, но все-таки использовал такие два алгоритма. Один алгоритм я взял такой: я взял список академиков Национальной академии наук США и других академий, в которых я состою, значит тоже брал. И брал списки телефонных номеров по алфавитному списку академиков, и брал средние цифры телефонного номера, чтобы не учитывать, что там какой-нибудь там... нули в конце или там какой-нибудь 192 в начале, чтобы не попадали одинаковые, чтобы, несмотря на то, где они там, в Гарварде или в Принстоне, чтобы этот Гарвард не влиял. Получается последовательность, которая, как и галактики, как и эти вычеты, удовлетворяет всем распределениям случайности.
А я сделал еще... второй опыт я сделал такой. Я взял и мимо нашего Математического института имени Стеклова проходящие номера машин списал. Значит, взял несколько сотен машин, списал номера, а потом взял и обработал теми же методами. Опять получается.»
От себя:
Я сформулирю свой вопрос так: Поддаётся ли математическому анализу (моделированию) утверждение: «На всё воля аллаха»? И пока мой лично ответ: судя по всему ДА, по меньшей мере, направления поиска ответа на этот вопрос обозначены достаточно убедительно.
Можно возразить, да хорошо. Но это мир вещественных чисел, та же квантовая механика с ним дел не имеет. Есть твисторы Пенроуза, которые уводят пространство-время в область "ирррельных комплексных чисел". Есть... И тогда нет особой нужды в "сложностях последовательностей нулей и единиц" с привнесением в них случайностей и непредсказуемости. В каком же мире мы живём: в комплексном или вещественном? Как будет выкристаллизовываться единый математический модельный аппарат для микро- и макро- мира? Какой вариант лучше: синергетика + непредсказуемый вещественный мир, или комплексный мир + модификация ОТО и КТ? Или....? Об этом я ничего не знаю
Эпиграф: «Невозможно доказать, конечное или бесконечное число решений имеет каждое уравнение из семейства алгебраических уравнений: ответ варьирует случайным образом, и, следовательно, не может быть найден с помощью математического рассуждения»
Что может быть бесспорнее того факта, что 2 плюс 2 равняется 4? Со времён древних греков математики считали, что более несомненной вещи, чем доказанная теорема, не сыскать. Действительно, математические утверждения, истинность которых может быть доказана, часто считались более надёжным основанием для системы мышления, чем любой моральный или даже физический принцип. Немецкий философ и математик XVII века Готфрид Вильгельм Лейбниц считал возможным создать «исчисление» рассуждений, которое когда-нибудь позволит улаживать все споры с помощью слов: «Давайте вычислим, господа!». К началу нашего столетия прогресс в разработке символической логики дал основание немецкому математику Давиду Гильберту заявить, что все математические вопросы в принципе разрешимы, и провозгласить окончательную кодификацию методов математического рассуждения.
В 30-е годы нашего столетия этот оптимизм совершенно развеялся под влиянием удивительных и глубоких открытий К. Гёделя и А. Тьюринга. Гёдель доказал, что не существует системы аксиом и методов рассуждения, охватывающей все математические свойства целых положительных чисел. Позднее Тьюринг облёк остроумные, но сложные гёделевы доказательства в более понятную форму. Как показал Тьюринг, гёделева теорема о неполноте эквивалентна утверждению, что не существует общего метода для систематического принятия решения о том, остановится ли когда-нибудь компьютерная программа, т.е. приведёт ли она когда-нибудь компьютер к остановке. Разумеется, если некоторая конкретная программа приводит к остановке компьютера, этот факт легко может быть доказан непосредственным выполнением этой программы. Трудность заключается в доказательстве того, что произвольно взятая программа не останавливается.
Недавно мне удалось сделать ещё один шаг по пути, намеченному Гёделем и Тьюрингом. Преобразовав некоторую конкретную компьютерную программу в алгебраическое уравнение такого типа, который был знаком ещё древним грекам, я показал, что область чистой математики, известная под названием теории чисел, содержит в себе случайность. Это исследование демонстрирует, говоря словами Эйнштейна, что Бог ПОРОЙ использует целые числа для игры в кости.
Полученный результат, входящий составной частью в то, что было названо алгоритмической теорией информации, не является причиной для пессимизма; он не вносит в математику анархию. (В самом деле, большинство математиков продолжают работать над своими проблемами, как и раньше.) Он означает лишь, что в некоторых ситуациях должны применяться математические законы особого рода — статистические. Подобно тому как физика не в состоянии предсказать, в какой именно момент распадётся данный атом радиоактивного вещества, математика порой бессильна дать ответ на некоторые вопросы. Однако физики могут надёжно предсказать средние значения физических величин, отнесённые к большому количеству атомов. Математики в некоторых случаях должны, вероятно, ограничиваться таким же подходом.
………………….
Но каким же образом теорема Гёделя о неполноте, проблема остановки Тьюринга и моя работа влияют на математику? Большинство математиков не обращают внимания на эти результаты. Конечно, в принципе они согласны, что любая конечная система аксиом неполна, но на практике они игнорируют этот факт, как непосредственно не относящийся к их работе. Но иногда, к сожалению, его нельзя игнорировать. Хотя в исходном виде теорема Гёделя казалась применимой лишь к необычным математическим предложениям, не имеющим практического интереса, алгоритмическая теория информации показала, что неполнота и случайность являются естественными и распространёнными повсюду свойствами. Это подсказывает мне, что следует более серьёзно относиться к возможности поиска новых аксиом относительно целых чисел.
Тот факт, что многие математические проблемы оставались веками и даже тысячелетиями нерешёнными, похоже, подтверждает мою точку зрения. Математики непоколебимо стоят на том, что причина неудач в решении подобных проблем заключена только в самих проблемах, но не заключается ли она в неполноте системы их аксиом? Например, вопрос о том, существуют ли нечётные совершенные числа, не поддаётся решению со времён древних греков. (Совершенным называется число, равное сумме своих делителей, исключая само это число. Например, 6 — совершенное число, поскольку 6=1+2+3.) Не может ли быть так, что утверждение «Не существует нечётных совершенных чисел» недоказуемо? Если это так, то не лучше ли принять его за аксиому?
Большинству математиков это предположение может показаться смехотворным, но для физика или биолога оно не выглядит столь уж абсурдным. Для тех, кто работает в эмпирических областях науки, основным критерием, позволяющим судить о том, следует ли рассматривать некоторое суждение как основание теории, служит полезность этого суждения, а вовсе не обязательно его «самоочевидная истинность». Если имеется много догадок, которые можно обосновать обращением к некоторой гипотезе, учёные-эмпирики принимают эту гипотезу. (Из несуществования нечётных совершенных чисел, по-видимому, не следует важных выводов, и, согласно этому критерию, такая аксиома не является полезной.)
На самом деле в некоторых случаях математики в своей работе опираются на недоказанные, но полезные предположения. Например, так называемая гипотеза Римана, хотя она никогда не была доказана, часто считается верной, потому что на ней основано много важных теорем. Более того, эта гипотеза была эмпирически проверена с помощью самых мощных компьютеров, и ни один опровергающий её пример не был найден. Компьютерные программы (которые, как я уже сказал, эквивалентны математическим утверждениям) проверяются таким же способом — тестированием некоторого числа вариантов, а не строгим математическим доказательством.
Существуют ли проблемы в других областях науки, для решения которых был бы полезен этот экскурс в основания математики? Я думаю, алгоритмическая теория информации может применяться в биологии. Регуляторные гены развивающегося зародыша являются по существу вычислительной программой построения организма. «Сложность» этой биохимической компьютерной программы можно, как мне думается, определить в терминах, аналогичных тем, что я развил при квантификации информационного содержания Ω.
Хотя Ω совершенно случайна (или бесконечно сложна) и никогда не может быть вычислена точно, её можно аппроксимировать с произвольной точностью, если в распоряжении имеется бесконечный отрезок времени. Мне кажется, что «сложность» живого организма может быть приближена таким же образом. Последовательность Ωn, аппроксимирующую Ω, можно рассматривать как метафору эволюции, и, возможно, она содержит зерно математической модели, описывающей эволюцию «сложности» биологического организма.
В конце своей жизни Дж. фон Нейман призвал математиков заняться созданием абстрактной математической теории происхождения и эволюции жизни. Эта фундаментальная проблема, подобно большинству проблем такого масштаба, бесконечно трудна. Возможно, алгоритмическая теория информации позволит найти путь, по которому следует идти.
Этой работе 20 лет. Из последних публикаций, могу предложить лекцию В.И.Арнольда «С ложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств» ( http://elementy.ru/lib/430178/430281 )
Одна выдержка из лекции В.И.Арнольда: «Утверждение состоит в том, что вот этот логарифм или, наоборот, геометрическая прогрессия, обратная функция, — распределены их значения, вообще значения, хаотическим образом. Оказывается... нарисуем график для обычных картинок... ну там вот есть какая-нибудь функция... ну или там логарифм... вот он имеет какой-нибудь гладкий график вот... в обычном случае... А в нашей арифметической задаче оттого что мы берем остатки от всего этого, то оказывается, получается функция, у которой график ведет себя вот так. Безобразный график получается, хаотический. Он не непрерывный, конечно, это конечное число точек, это облако точек некоторое. Но если нарисовать этот график аккуратно, то есть одна точка здесь, одна здесь, получается случайный набор точек на плоскости.
В каком смысле он случайный? Это надо определять. Что такое случайность, что такое случайный набор... Все это можно сделать, проверить, посчитать... Я вот занимался когда-то с Яковом Борисовичем Зельдовичем случайностью распределения галактик и скопления галактик во Вселенной и применял потом здесь, в этой задаче, те же самые критерии, при помощи которых определяли, случайно галактики распределены или нет, можно и к этим точкам. Удовлетворяют всем критериям, по которым Зельдович считал, что галактики случайно в какой-то области распределены... Так и здесь: те же самые критерии можно применить, и получается, что это случайные точки.
Так вот теперь спрашивается: а где брать случайные точки вообще? В криптографии очень нужны случайные точки — для того чтобы код делать случайный... И как их получать? И вот я сейчас хочу рассказать... эта теория, про которую я здесь рассказываю, в частности дает некоторые очень странные алгоритмы построения случайных последовательностей.
Я придумал такие алгоритмы для разных других задач, но все-таки использовал такие два алгоритма. Один алгоритм я взял такой: я взял список академиков Национальной академии наук США и других академий, в которых я состою, значит тоже брал. И брал списки телефонных номеров по алфавитному списку академиков, и брал средние цифры телефонного номера, чтобы не учитывать, что там какой-нибудь там... нули в конце или там какой-нибудь 192 в начале, чтобы не попадали одинаковые, чтобы, несмотря на то, где они там, в Гарварде или в Принстоне, чтобы этот Гарвард не влиял. Получается последовательность, которая, как и галактики, как и эти вычеты, удовлетворяет всем распределениям случайности.
А я сделал еще... второй опыт я сделал такой. Я взял и мимо нашего Математического института имени Стеклова проходящие номера машин списал. Значит, взял несколько сотен машин, списал номера, а потом взял и обработал теми же методами. Опять получается.»
От себя:
Я сформулирю свой вопрос так: Поддаётся ли математическому анализу (моделированию) утверждение: «На всё воля аллаха»? И пока мой лично ответ: судя по всему ДА, по меньшей мере, направления поиска ответа на этот вопрос обозначены достаточно убедительно.
Можно возразить, да хорошо. Но это мир вещественных чисел, та же квантовая механика с ним дел не имеет. Есть твисторы Пенроуза, которые уводят пространство-время в область "ирррельных комплексных чисел". Есть... И тогда нет особой нужды в "сложностях последовательностей нулей и единиц" с привнесением в них случайностей и непредсказуемости. В каком же мире мы живём: в комплексном или вещественном? Как будет выкристаллизовываться единый математический модельный аппарат для микро- и макро- мира? Какой вариант лучше: синергетика + непредсказуемый вещественный мир, или комплексный мир + модификация ОТО и КТ? Или....? Об этом я ничего не знаю