(9 оценок, среднее: 4,78 из 5)
Загрузка...
Учебная работа. Реферат: Случайность в арифметике
Грегори Дж.Чейтин
Что быть может бесспорнее того факта, что 2 плюс 2 приравнивается 4? Со времён старых греков арифметики считали, что наиболее бесспорной вещи, чем доказанная аксиома, не сыскать. Вправду, математические утверждения, истинность которых быть может подтверждена, нередко числились наиболее надёжным основанием для системы мышления, чем хоть какой моральный либо даже физический принцип. Германский философ и математик XVIIвека Готфрид Вильгельм Лейбниц считал вероятным сделать «исчисление» рассуждений, которое когда-нибудь дозволит улаживать все споры при помощи слов: «Давайте вычислим, господа!». К началу нашего столетия прогресс в разработке символической логики отдал основание германскому арифметику Давиду Гильберту заявить, что все математические вопросцы в принципе разрешимы, и объявить окончательную кодификацию способов математического рассуждения.
В 30-е годы нашего столетия этот оптимизм совсем развеялся под воздействием умопомрачительных и глубочайших открытий К.Гёделя и А.Тьюринга. Гёдель обосновал, что не существует системы аксиом и способов рассуждения, обхватывающей все математические характеристики целых положительных чисел. Позже Тьюринг облёк смышленые, но сложные гёделевы подтверждения в наиболее понятную форму. Как показал Тьюринг, гёделева аксиома о неполноте эквивалентна утверждению, что не существует общего способа для периодического принятия решения о том, остановится ли когда-нибудь компьютерная программка, т.е. приведёт ли она когда-нибудь комп к остановке. Очевидно, если некая определенная программка приводит к остановке компа, данный факт просто быть может подтвержден конкретным выполнением данной нам программки. Трудность заключается в подтверждении того, что произвольно взятая программка не останавливается.
Не так давно мне удалось создать ещё один шаг по пути, намеченному Гёделем и Тьюрингом. Преобразовав некую определенную компьютерную программку в алгебраическое уравнение такового типа, который был знаком ещё старым грекам, я показал, что область незапятанной арифметики, популярная под заглавием теории чисел, содержит внутри себя случайность. Это исследование показывает, говоря словами Эйнштейна, что Бог иногда употребляет целые числа для игры в кости.
Приобретенный итог, входящий составной частью в то, что было названо алгоритмической теорией инфы, не является предпосылкой для пессимизма; он не заносит в арифметику анархию. (По правде, большая часть математиков продолжают работать над своими неуввязками, по-прежнему.) Он значит только, что в неких ситуациях должны применяться математические законы особенного рода — статистические. Подобно тому как физика не в состоянии предсказать, в которой конкретно момент распадётся данный атом радиоактивного вещества, математика иногда бессильна отдать ответ на некие вопросцы. Но физики могут надёжно предсказать средние значения физических величин, отнесённые к большенному количеству атомов. Арифметики в неких вариантах должны, возможно, ограничиваться таковым же подходом.
Моя работа служит естественным продолжением работы Тьюринга, но если Тьюринг анализировал, остановится либо нет случайная программка, я рассматриваю возможность того, что всепригодный комп закончит работу, если его программка выбрана совсем случаем. Что я имею в виду, говоря «выбрана совсем случаем»? Так как неважно какая программка быть может сведена к последовательности двоичных разрядов — битов (любой из которых может принимать программка, состоящая из n битов, эквивалентна результату n бросаний монеты (где «орёл» представляется нулём, а «решка» — единицей, либо напротив).
Возможность того, что таковая совсем случайная программка остановится (обозначим эту возможность эмблемой Ω), выражается вещественным числом, заключённым меж 0 и 1. (Утверждение Ω=0 будет означать, что никакая случайная программка не остановится, a Ω=1 — что всякая случайная программка остановится. Если мы имеем дело с всепригодным компом, ни одно из этих последних значений не реализуемо.) Так как Ω — вещественное число, на сто процентов представить его можно только как нескончаемую последовательность разрядов. В двоичной системе это последовательность нулей и единиц.
Наверняка, самым увлекательным свойством данной нам нескончаемой цепочки будет то, что она алгоритмически случайна: она не быть может сжата в программку (рассматриваемую как цепочка битов) длиной, наименьшей чем она сама. Это определение случайности, играющее главную роль в алгоритмической теории инфы, было независимо сформулировано посреди 60-х годов русским академиком А.Н.Колмогоровым и мною. (Потом это определение мне пришлось подправить.)
Основная мысль такового определения ординарна. Некие последовательности битов могут быть сжаты в программки, наиболее недлинные, чем сами эти последовательности, поэтому что они построены по какой-нибудь схеме либо подчиняются какому-либо правилу. к примеру, 200-битовая последовательность вида 0101010101… быть может очень сжата, если её задать как «100 повторений пары 01». Непременно, такие последовательности не являются случайными. С иной стороны, 200-битовая последовательность, порождённая бросанием монеты, не быть может сжата, так как для этого процесса, совершенно говоря, отсутствует закономерность в чередовании нулей и единиц; это совсем случайная последовательность.
Из всех вероятных последовательностей битов большая часть несжимаемы и, как следует, случайны. Так как последовательность битов можно разглядывать как идет о двоичном представлении, то при стремлении числа разрядов к бесконечности, нулей и единиц будет в точности по 50%.
Для того чтоб Ω имела смысл, обязано производиться одно техническое условие: программка на входе обязана быть самоограничивающейся. Другими словами, информация о её общей длине (в битах) обязана содержаться в самой программке. (Это на 1-ый взор малозначительное условие, тормозившее прогресс в данной области в течение практически 10-ка лет, принудило переопределить понятие алгоритмической случайности.) Имеющиеся языки программирования предусмотрены для построения самоограничивающихся программ, так как в этих языках предусмотрены механизмы начала и окончания программки. Такие конструкции разрешают программке содержать верно определённые подпрограммы, которые в свою очередь могут включать в себя остальные вложенные подпрограммы. Так как самоограничивающиеся программки строятся с помощью конкатенации (объединения 2-ух последовательностей, скажем, строк либо файлов, в одну. — Ред.) и вложения самоограничивающихся подпрограмм, программка синтаксически полна только тогда, когда крайняя открытая подпрограмма «закрыта». На самом деле механизмы начала и окончания программ и подпрограмм работают соответственно как левая и правая скобка в математических выражениях.
Если б программки не были самоограничивающимися, их недозволено было бы выстроить из подпрограмм, и суммирование вероятностей остановки для всех программ отдало бы нескончаемый итог. Если же вы рассматриваете только самоограничивающиеся программки, то Ω не только лишь ограничена 0 и 1, но её можно очевидно вычислить «в пределе снизу». Иными словами, можно вычислять элементы нескончаемой последовательности оптимальных чисел (выраженных конечной последовательностью битов), каждое из которых поближе к четкому значению Ω, чем предшествующее.
один из методов создать это — систематически вычислять Ωn
для растущих значений n; тут Ωn
— возможность того, что совсем случайная программка длиной до n битов остановится через n секунд, если она производится на данном компе. Так как имеется 2k
вероятных программ длиной k битов, Ωn
можно в принципе вычислить: для всякого значения k от 1 до n нужно найти, сколько из этих вероятных программ по сути останавливается через n секунд, помножить это число на 2–k
, а потом просуммировать все приобретенные произведения. По другому говоря, любая таковая останавливающаяся k-битовая программка заносит собственный вклад, равный 2–k
, в
Если б мы каким-то чудом узнали неувязка остановки для всех программ размером меньше k битов. естественно, для разумного значения k требуемое для вычисления время было бы большим.
До сего времени при обсуждении препядствия остановки я обращался только к её компьютерно-программной интерпретации, но в свете работы Дж.Джоунса из Института в Калгари и Ю.В.Матиясевича из Ленинградского отделения Математического института им.Стеклова АНСССР в данной нам дилемме возникает новое «измерение». Исследования упомянутых создателей дают способ, позволяющий представить эту делему в виде утверждений о диофантовых уравнениях определённого класса. Эти алгебраические уравнения, составленные с помощью операций над целыми числами — умножения, сложения и возведения в целую степень, названы по имени греческого математика Диофанта Александрийского, жившего в IIIвеке н.э.
Выражаясь поточнее, способ Джоунса и Матиясевича дозволяет отождествить утверждение о том, что некая определенная программка не остановится, с утверждением о том, что одно из уравнений из определённого класса диофантовых уравнений не имеет решений в целых числах. Как и в уникальной версии препядствия остановки для компов, тут, если решение существует, это просто обосновать: всё, что требуется, — это подставить правильные числа и проверить, равными ли вышли левая и правая части уравнения. Обосновать же несуществование решения (если оно вправду отсутствует) намного труднее.
Класс уравнений строится исходя из базисного уравнения, которое содержит определенную переменную k, именуемую параметром и принимающую значения 1, 2, 3 и т.д. (см. набросок ниже). Таковым образом, имеется нескончаемо большенный класс уравнений (по одному уравнению на каждое 1-го базисного уравнения для каждой программки из «семейства» программ. Математическое утверждение о том, что диофантово уравнение с параметром k не имеет решения, равносильно утверждению, что k-я компьютерная программка никогда не остановится. С иной стороны, если k-я программка останавливается, то соответственное уравнение имеет в точности одно решение. В неком смысле истинность (либо ложность) утверждений этого типа является математически неопределённой, так как она меняется непредсказуемым образом, когда параметр k воспринимает разные значения.
«Класс» уравнений порождается путём придания параметру k базисного уравнения разных целочисленных значений.
Мой подход к непредсказуемости в арифметике подобен этому, но он приводит к еще наиболее высочайшей степени случайности. Заместо «арифметизации» компьютерных программ (которые могут либо не могут останавливаться) как класса диофантовых уравнений, я применяю способ Джоунса и Матиясевича для арифметизации единственной программки вычисления k-го разряда Ωn
.
Этот способ основан на любопытном свойстве чётности биномиальных коэффициентов, которое было увидено Э.Лючка 100 лет вспять, но до сего времени оставалось неоценённым по достоинству. Биномиальные коэффициенты представляют собой множители при степенях xk
в разложении выражений вида (x+1)n
. Эти коэффициенты просто рассчитываются при помощи так именуемого треугольника Паскаля (см. набросок ниже).
В аксиоме Лючка утверждается, что коэффициент при xk
в разложении (x+1)n
нечётен лишь тогда, когда любой разряд в двоичном представлении числа k меньше либо равен соответственному уровню в двоичном представлении числа n (сравнение начинается с правых частей). Это можно выразить проще, сказав, что коэффициент при xk
в разложении (x+1)n
нечётен, если для всякого разряда k, равного 1, соответственный разряд n тоже равен 1; в неприятном случае коэффициент чётен. К примеру, коэффициент при x2
в разложении двучлена (x+1)4
равен 6, т.е. чётный. Соответственно единица в двоичном представлении двойки (10) не стоит на том же месте, что и единица в двоичном представлении четвёрки (100).
Треугольник Паскаля (вверху) служит для вычисления коэффициентов разложения выражений вида (x+1)n
. Начав с треугольника из единиц, вычисляют значения на любом поочередном уровне путём сложения примыкающих чисел; крайней ставят единицу. Таковым образом можно найти, к примеру, что
(x + 1)4
= 1×4
+ 4×3
+ 6×2
+ 4x + 1×0
.
Этот треугольник можно перевоплотить в симпатичный фрактальный узор, если поменять нечётные коэффициенты единицами, а чётные — нулями (понизу). Узор показывает свойство коэффициентов, используемое при «арифметизации» компьютерных программ, которая конвертирует их в алгебраические уравнения.
Хотя мысль арифметизации ординарна и роскошна, выполнение этого построения представляет собой массивную программистскую задачку. Тем не наименее мне чудилось, что это быть может увлекательным. Потому я разработал программку «компилятор» для получения уравнений из программ для «регистровой машинки». Регистровая машинка представляет собой комп, состоящий из маленького огромного количества регистров для хранения чисел случайной величины. Очевидно, это абстракция, так как хоть какой настоящий комп имеет регистры ограниченного объёма.
Подав на вход настоящего компа, имеющего программу-компилятор, программку регистровой машинки, которая делает аннотации на языке Лисп, получим через несколько минут на выходе уравнение длиной около 200 страничек, содержащее приблизительно 17000 неотрицательных целых переменных. Итак, я могу вывести диофантово уравнение с параметром k, кодирующее k-й разряд Ωn
, путём обычный подстановки программки на Лиспе (в двоичной форме), созданной для вычисления k-го разряда Ωn
, в 200-страничное уравнение. Для хоть какой данной пары значений k и n диофантово уравнение имеет в точности одно решение, если k-й разряд Ωn
равен 1, и не имеет решения, если k-й разряд Ωn
равен 0.
Арифметизация Ω производится путём подстановки двоичного представления определенной программки для вычисления k-го разряда Ωn
(в двоичной форме) заместо переменной в уравнение, приобретенное из программки для всепригодного компа. Ωn
является n-й аппроксимацией Ω — вероятности остановки компа при условии, что биты, составляющие его программку, определены случайным образом, к примеру с помощью бросания монеты.
Так как это правильно для хоть какой пары значений k и n, можно, совершенно говоря, зафиксировать k и систематически наращивать значения n. Для малых значений n k-й разряд Ωn
будет хаотично флуктуировать меж 0 и 1. В конце концов, но, он станет равным 1 либо 0, так как для весьма огромных значений n он должен быть равен k-му уровню Ω, который неизменен. Как следует, диофантово уравнение в реальности имеет нескончаемое число решений для определенного значения собственного параметра k, если k-й разряд Ω оказывается равным 1, и только конечное число решений, если k-й разряд Ω оказывается равным 0. Таковым образом, заместо того чтоб выяснять, имеет ли диофантово уравнение решения для всякого значения собственного параметра k, я узнаю, имеет ли оно нескончаемо много решений.
На 1-ый взор может показаться, что мы не много выигрываем, спрашивая «имеет ли уравнение нескончаемо много решений», заместо «имеет ли оно совершенно решения». Но по сути это весьма принципиальное различие: ответы на эти вопросцы логически независимы. Два математических утверждения числятся логически независящими, если одно недозволено вывести из другого, т.е. если ни одно из их не является логическим следствием другого. Это понятие независимости обычно различают от понятия независимости, применяемого в статистике. Крайнее состоит в том, что два случайных действия именуются независящими, если финал 1-го из их не оказывает воздействия на финал другого. к примеру, итог бросания монеты никаким образом не влияет на итог последующего бросания: эти результаты статистически независимы.
Я использую оба понятия независимости. Ответ на мой вопросец для 1-го значения k логически независим от ответа на этот вопросец для другого значения k. Причина состоит в том, что определенные разряды Ω, определяющие ответ, независимы статистически.
Просто обосновать, что приблизительно для половины значений k число решений естественно, а для иной половины число решений нескончаемо, но не существует метода «сжать» эти ответы в формулу либо набор правил: они вроде бы «подражают» результатам бросания монеты. Так как Ω алгоритмически случайна, то даже познание ответов для 1000 значений k не поможет отыскать верный ответ для 1001-го значения k. Устанавливая, имеет ли конкретное уравнение конечное либо нескончаемое число решений, математик находится в положении игрока, бросающего монету. Какие бы теоремы и подтверждения мы ни применяли для диофантова уравнения с одним значением k, они будут неприменимы для такого же самого уравнения при другом значении k.
Математическое рассуждение оказывается в этом случае в принципе никчемным, так как нет логических взаимосвязей меж приобретенными таковым методом диофантовыми уравнениями. Будь ты хоть 7 пядей во лбу, выведи длиннейшее подтверждение, применяй сложнейшие математические теоремы, построенный нескончаемый ряд предложений, устанавливающий, естественно либо нескончаемо число решений диофантова уравнения, окажется никчемным, если k прирастить. Итак, даже в простых разделах теории чисел, связанных с диофантовыми уравнениями, появляются случайность, неопределённость и непредсказуемость.
Но каким же образом аксиома Гёделя о неполноте, неувязка остановки Тьюринга и моя работа влияют на арифметику? Большая часть математиков не обращают внимания на эти результаты. естественно, в принципе они согласны, что неважно какая конечная система аксиом неполна, но на практике они игнорируют данный факт, как конкретно не относящийся к их работе. Но время от времени, к огорчению, его недозволено игнорировать. Хотя в начальном виде аксиома Гёделя казалась применимой только к необыкновенным математическим предложениям, не имеющим практического энтузиазма, алгоритмическая теория инфы показала, что неполнота и случайность являются естественными и распространёнными всюду качествами. Это дает подсказку мне, что следует наиболее серьёзно относиться к способности поиска новейших аксиом относительно целых чисел.
Тот факт, что почти все математические препядствия оставались веками и даже тысячелетиями нерешёнными, похоже, подтверждает мою точку зрения. Арифметики неколебимо стоят на том, что причина неудач в решении схожих заморочек заключена лишь в самих дилеммах, но не заключается ли она в неполноте системы их аксиом? К примеру, вопросец о том, есть ли нечётные совершенные числа, не поддаётся решению со времён старых греков. (Совершенным именуется число, равное сумме собственных делителей, исключая само это число. к примеру, 6 — совершенное число, так как 6=1+2+3.) Не может ли быть так, что утверждение «Не существует нечётных совершенных чисел» недоказуемо? Если это так, то не лучше ли принять его за теорему?
Большинству математиков это предположение может показаться смехотворным, но для физика либо биолога оно не смотрится настолько уж абсурдным. Для тех, кто работает в эмпирических областях науки, главным аспектом, позволяющим судить о том, следует ли разглядывать некое суждение как основание теории, служит полезность этого суждения, а совсем не непременно его «самоочевидная истинность». Если имеется много догадок, которые можно доказать воззванием к некой догадке, учёные-эмпирики принимают эту догадку. (Из несуществования нечётных совершенных чисел, по-видимому, не следует принципиальных выводов, и, согласно этому аспекту, таковая теорема не является полезной.)
По сути в неких вариантах арифметики в собственной работе опираются на недоказанные, но полезные догадки. к примеру, так именуемая догадка Римана, хотя она никогда не была подтверждена, нередко считается верной, поэтому что на ней основано много принципиальных теорем. Наиболее того, эта догадка была эмпирически испытана при помощи самых массивных компов, и ни один опровергающий её пример не был найден. Компьютерные программки (которые, как я уже произнес, эквивалентны математическим утверждениям) проверяются таковым же методом — тестированием некого числа вариантов, а не серьезным математическим подтверждением.
Есть ли препядствия в остальных областях науки, для решения которых был бы полезен этот экскурс в основания арифметики? Я думаю, алгоритмическая теория инфы может применяться в биологии. Регуляторные гены развивающегося эмбриона являются по существу вычислительной программкой построения организма. «Сложность» данной нам биохимической компьютерной программки можно, как мне думается, найти в определениях, подобных тем, что я развил при квантификации информационного содержания Ω.
Хотя Ω совсем случайна (либо нескончаемо сложна) и никогда не быть может вычислена буквально, её можно аппроксимировать с случайной точностью, если в распоряжении имеется нескончаемый отрезок времени. Мне кажется, что «сложность» живого организма быть может приближена таковым же образом. Последовательность Ωn
, аппроксимирующую Ω, можно разглядывать как метафору эволюции, и, может быть, она содержит зерно математической модели, описывающей эволюцию «трудности» био организма.
В конце собственной жизни Дж. фонНейман призвал математиков заняться созданием абстрактной математической теории происхождения и эволюции жизни. Эта базовая неувязка, подобно большинству заморочек такового масштаба, нескончаемо трудна. Может быть, алгоритмическая теория инфы дозволит отыскать путь, по которому следует идти.
Перечень
литературы
1. G.J.Chaitin. Algorithmic information theory. Cambridge University Press, 1987.
2. G.J.Chaitin. Information, randomness & incompleteness. World Scientific Publishing Co. Pte. Ltd., 1987.
3. I.Stewart. The ultimate in undecidability. In: Nature, 1988, v.232, No.6160, pp.115–116.
4. Я.М.Бардзинь. Алгоритмическая теория инфы. В кн.: Математическая энциклопедия. т.1. М.: Русская энциклопедия, 1977.
5. А.Н.Колмогоров, В.А.Успенский. методы и случайность. Теория вероятностей и её внедрения, 1987, т.32, вып.3.
6. М.Клайн. Математика. Утрата определённости. М.: мир, 1984.
]]>