Секей Г. Парадоксы в теории вероятностей и математической статистике (1990) (1151962), страница 41
Текст из файла (страница 41)
Существует бесконечно много неинтересных чисел, но «неинтересность» можно доказать лишь для конечного числа из них. в) Объяснение парадокса Сначала может показаться удивительной возможность существования чего-то такого, что нельзя проверить, однако с подобным явлением мы встречаемся не только в мире математики. Например, если все сто тысяч мест на стадионе заняты, но было продано только девяносто девять тысяч билетов, то ясно, что тысяча человек проникли на стадион без билетов. Однако поиск этих людей безнадежен (особенно, если у каждого на входе билеты отбираются). Таким образом, мы знаем наверняка, что на стадионе присутствует тысяча человек, попавших туда без балета, но мы не можем доказать, что любой конкретный человек прошел на стадион без билета.
В математике подобные явления встречаются часто. Вовсе неудивительно, что большинство чисел неинтересны. Достаточно вспомнить, как трудно бывает даже в семизначном телефонном номерс «обнаружить» какую-либо регулярность, чтобы легче его запомнить. Еще сложнее найти регулярность для большей доли чисел, записываемых сотней или тысячью знаками. Так что более удивительна вторая часть парадокса, особенно для тех, кто недостаточно хорошо знаком с парадоксами логики ХХ века. Среди этих парадоксов наиболее близок к нашему парадокс Г.
Берри. (Этот парадокс впервые был опубликован 70 лет назад в работе Б. Рассела и А. Уайтхеда «Рг!ос!р1а Ма(ешайса».) <Компьютеризированный вариант» парадокса Берри принадлежит Э. Бгккенбаку. В нем утверждается, что неинтересные натуральные числа не могут существовать, потому что наименьшее из них было бы интересным. Иными словами: наименьшее из чисел, которые строятся только с помощью длинных программ на ЭВМ, можно также генерировать с помощью короткой программы, что, безусловно, является противоречием. Необходимо признать, что некоторые числа являются неинтересными, даже если мы не можем этого доказать, Если система аксиом и правила вывода содержат л бит информации, то можно показать, что свойство «неинтересности» числа нельзя доказать в том случае, когда его количество информации намного больше, чем п бит. г) Замгчамие Важным критерием случайности знаков в записи числа является невозможность их экстраполировать, или предсказывать.
Возникает вопрос, существует ли какое-нибудь (неслучайное) число, которое может быть точно определено, но цифры которого нельзя предсказать. Утвердительный ответ дан в примере Шайгина. Пусть случайная последовательность из «гербов» и «решек», возникающая при бросании монеты, или соответствующая ей последовательность из нулей и единиц, вводится в некоторую машину, а именно в машину Тьюринга.
Вероятность того, что машина Тьюринга остановится в какой-то момент ввода случайной последовательности, и определяет число Шайтина. (Теоретически машина может работать как угодно долго, потому что она не получает команд, заставляющих ее остановиться.) Можно доказать, что число Шайтина «неинтересно» и цифры этого числа предсказать нельзя. В то же время это «неинтересное» число Шайтина обладает рядом интересных свойств. Например, если бы было известно несколько первых тысяч цифр в его десятичной записи, то тем самым мы получили бы решения некоторых классических нерешенных проблем в математике таких, как великан теорема Ферма и лроблема Гоньдбаха.
Великая теорема Ферма (которая утверждает, что уравнение к" + у" = я«не имеет решений в натуральных числах к, у, г при л ) 2)') теоретически может быть доказана или опровергнута с помощью компьютерной программы — «программы Ферма», которая для данных значений н и г проверяет, существуют лн целые числа к и 1д являющиеся решением уравнения Ферма. При постепенном увеличении значений и и г будут рассмотрены все случаи. Когда решение будет найдено, вычислительная машина остановится. Если машина когда-нибудь остановится, то теорема Ферма будет опровергнута, в противном случае доказана.
«Единственная» проблема состоит в следующем; как бы долго уже не работала машина, мы никогда не можем быть уверены, что она не остановится на следующем шаге. Эту проблему можно было бы обойти, если знать постоянную Шайтина. Рассмотрим всевозможные вводимые последовательности в двоичном коде конечной длины и попробуем определить те программы (вводимые последовательности), которые останавливают машину. Сначала посмотрим, останавливает ли машину первая программа на первом шаге, затем — останавливает ли машину вторая программа на первом шаге.
Далее, позволим первой программе выполняться до второго шага, третьей программе до первого шага, второй программе до второго шага и первой программе до третьего шага и т. д. Если машина остановится на некоторой входной последовательности, которая записана в двоичных кодах, и ее длина й, то положим мысленно 1/2' долю единицы веса в мешок. Постепенно мешок будет становиться все тяжелей и его вес будет сходиться к постоянной Шайтина (так как с вероятностью !/2" любая конкретная двоичная последовательность длины й появляется среди последовательностей, соответствующих бросанию симметричной монеты).
Пусть пт — длина двоичной «программы Ферма». Предположим, что программы выполняются до тех пор, пока разность между постоянной Шайтина и весом, накопленным в мешке, не станет меньше, чем 1/2". Если к этому моменту великая теорема Ферма нс оказалась опровергнутой, то она должна быть справедливой, так как если «программа Ферма» остановит машину позднее, мы должны будем положить в мешок 1/2ы единицы веса, что противоречит тому факту, что мы нашли значение постоянной Шайтина с точностью лучшей, чем !/2 .
Постоянная Шайтина позволяет получить решения (нли дает теоретическую возможность решений) всех проблем, которые можно свести к задаче об остановке, подобной той, которую мы только что обсудили. ') Недавно немецкий математин Г. Фалтиигс доказал очень глубокую теорему, нз которой следует, что возможные (по существу различные! решения уравнения Ферма конечны.
Это большой шаг на пути решения проблемыы Ферма. д) Литература СЬащп Сг. й кйапаовпеаа апг) вайева1ка! Ргоот', Зсс Апгег., 232, 47— 62, (1976). Сагспег М, "ТЬе гапаов пшпЬег огпеяа Ь!г)а 1а!г 1о Ьо!6 йе вуа!енес о1 йе ип)еегае", Зсс Атег., 241, 22 — 31, (1979) Сш1!оиг) 3., Воиуег М. Уп т!Шоп г(е г(ес!те!и ее гс.
Рона, 1974 М!е! С. "Ап а1аог!(ьв (ог са)си)аиоп о1 и". Тае Атег. Мо(Ь. Мопй1у, 86, (8), (1979). анап)га О., Фгепсь й %. "Са1си1аноп о1 и (о 100000 г)ес!ва!а", Мо!ЬетоГгса о) Сотри!оГ!оц 18, 76 — 99, (1962), 5. Парадокс случайных графов а) История парадокса Структурныс проблемы в ряде областей науки (например, проблему электронных схем) можно легко промоделировать и решить с помощью графов, т.
е. точек и линий, их соединяющих. Точки называются вершинами, алипии — ребрами графа. Ребра могут также отражать связь, носящую случайный характер. Поэтому очень важно изучение структуры случайных графов. Теория случайных графов была разработана в основном в работах Паула Эрдеша и Альфреда Реньи. Предположим, что у графа и вершин, и все ребра проводятся с вероятностью р независимо от существования других ребер. Пусть е>0 — произвольное число. В !920 г. Эрдеш и Репьи доказали, что если . (1 — е) !оаа и р ей то вероятность того, что граф является связным, стремится к 0 с ростом п.
С другой стороны, если (! + а) 1оаап рР то эта вероятность стремится к !. (Говорят, что граф является связным, если из каждой вершины можно по ребрам попасть в любую другую вершину.) Таким образом, вероятность (!она и)/и играет роль «водораздела». За последние два десятилетия теория случайных графов была обобщена на графы с бесконечным числом вершин. В связи с такими бесконечными графами Эрдеш и Репьи обратили внимание на следующий парадокс. б) Парадокс Говорят, что два графа бг и ба изоморфны, если существует взаимно однозначное соответствие между множествами вершин гРафов Ог и ба 1 пРи этом Две веРшины в бг соеДинены тогДа и только тогда, когда соответствуюШие вершины в 02 также соединены.
У изоморфных графов мощности множеств их вершин одинаковы, но лишь одного этого недостаточно для изоморфизма. Однако, если множества вершин бесконечны, точнее, их мощность совпадает с мощностью множества натуральных чисел, и если любые две вершины в каждом графе соединяются с вероятностью 1/2 независимо от других ребер, то эти графы изоморфны с вероятностью 1. Следовательно, в этом смысле все бесконечные случайные графы одинаковы! е) Объяснение парадокса Говорят, что граф универсален, если для произвольных последовательностей вершин и!, иь ..., и„ и оь оь ..., о„ (отличных друг от друга) существует вершина ш, отличная от и! и о; и такая, что ш соединена С каждой вершиной и; и ни с одной о;.
Легко показать, что если графы 6! и Ог универсальны, то они и изоморфны. Вероятность того, что случайные графы, о которых говорится в парадоксе, не универсальны, равна О (т.е. ш существует с вероятностью 1). г) Замечания Помимо исследований по случайным графам за последние несколько лет был проведен анализ и других случайных структур (случайных матриц, случайных алгебраических уравнений, случайных степенных рядов и т. д.), который также дал интересные результаты.
Например, О. Б. Маслова доказала следуюшую теорему: если коэффициенты Х; случайного алгебраического уравнения ~, Ха!=О ! ! являются независимыми одинаково распределенными случайными величинами с нулевыми математическими ожиданиями (но сами величины не равны тождественно О) н е()х ) ') ( для некоторого положительного е, то число действительных корней этого уравнения распределено нормально с математиче- 2 скнм ожиданием — )пи и стандартным отклонением 2 ~/и-! (1 — 2п-') (п и. д) Литература Егейа Р., 5репсег 3. РгоЬпЬ!Таис Месйоек 1п Сеть!пп!от!па, Акаееш!а! К!пап, Впеареи, 1974.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
