Ягодный парадокс - Berry paradox

Парадокс Берри является самоссылающиеся парадокс , возникающий из выражения , как «наименьшее натуральное число , не определимых в рамках шестидесяти букв» (фраза , с пятьдесят семь букв).

Бертран Рассел , первый обсудить парадокс в печати, приписал Г.Г. Берри (1867-1928), младший библиотекарь в Оксфорде «s Бодлеанской библиотеки . Рассел назвал Берри «единственным человеком в Оксфорде, который понимал математическую логику».

Обзор

Рассмотрим выражение:

«Наименьшее натуральное число, не определяемое менее шестидесяти букв».

Поскольку в английском алфавите всего двадцать шесть букв, существует конечное число фраз, состоящих из менее шестидесяти букв, и, следовательно, конечное число положительных целых чисел, которые определяются фразами из менее шестидесяти букв. Поскольку существует бесконечно много положительных целых чисел, это означает, что существуют положительные целые числа, которые не могут быть определены фразами из менее чем шестидесяти букв. Если существуют положительные целые числа, удовлетворяющие данному свойству, то существует наименьшее положительное целое число, удовлетворяющее этому свойству; следовательно, существует наименьшее натуральное число, удовлетворяющее свойству «не может быть определено менее чем шестьюдесятью буквами». Это целое число, к которому относится приведенное выше выражение. Но приведенное выше выражение состоит всего из пятидесяти семи букв, поэтому его можно определить менее шестидесяти букв и не является наименьшим положительным целым числом, не определяемым менее шестидесяти букв, и не определяется этим выражением. Это парадокс: должно быть целое число, определяемое этим выражением, но поскольку выражение противоречит самому себе (любое целое число, которое оно определяет, можно определить менее шестидесяти букв), оно не может быть определено целым числом.

Возможно, еще одной полезной аналогией с парадоксом Берри была фраза «неописуемое чувство». Если это чувство действительно неописуемо, тогда никакое описание чувства не будет верным. Но если слово «неописуемое» что-то сообщает о чувстве, тогда это можно рассматривать как описание: это внутреннее противоречие.

Математик и компьютерный ученый Грегори Дж. Чейтин в «Непознаваемом» (1999) добавляет следующий комментарий: «Что ж, мексиканский историк математики Алехандро Гарсидиего потрудился найти это письмо [Берри, из которого Рассел написал свои замечания], и это скорее Другой парадокс. В письме Берри на самом деле говорится о первом ординале, который не может быть назван конечным числом слов. Согласно теории Кантора, такой порядковый номер должен существовать, но мы только что назвали его конечным числом слов, что противоречие ".

разрешение

Формулированный выше парадокс Берри возникает из-за систематической двусмысленности слова «определяемый». В других формулировках парадокса Берри, например, в том, который вместо этого гласит: «... не именуемое меньшим ...», термин «именуемый» также имеет эту систематическую двусмысленность. Подобные термины порождают заблуждения о порочном круге . Другие термины с таким типом двусмысленности: выполнимый, истинный, ложный, функция, свойство, класс, отношение, кардинал и порядковый номер. Разрешить один из этих парадоксов - значит точно определить, где мы неправильно использовали язык, и ввести ограничения на использование языка, которые могут их избежать.

Это семейство парадоксов можно разрешить, включив в язык смысловое расслоение. Термины с систематической двусмысленностью могут быть написаны с нижними индексами, обозначающими, что один уровень значения считается более приоритетным, чем другой в их интерпретации. «Число, не имеющее названия 0 менее чем из одиннадцати слов», может быть обозначено 1 менее чем из одиннадцати слов по этой схеме.

Формальные аналоги

Используя программы или доказательства ограниченной длины, можно построить аналог выражения Берри на формальном математическом языке, как это сделал Грегори Чейтин . Хотя формальный аналог не приводит к логическому противоречию, он доказывает определенные результаты о невозможности.

Джордж Булос (1989) построил на формализованной версии парадокса Берри, чтобы доказать теорему Гёделя о неполноте новым и гораздо более простым способом. Основная идея его доказательства состоит в том, что утверждение, которое справедливо для x тогда и только тогда, когда x = n для некоторого натурального числа n, можно назвать определением для n , и что множество {( n , k ): n имеет определение, которое имеет длину k символов} можно показать как представимые (с использованием чисел Гёделя ). Тогда утверждение « m - первое число, которое не может быть определено менее чем k символами» может быть формализовано и показано как определение в только что изложенном смысле.

Отношения с Колмогоровской сложностью

В целом невозможно однозначно определить, какое минимальное количество символов требуется для описания данной строки (с учетом конкретного механизма описания). В этом контексте термины строка и число могут использоваться взаимозаменяемо, поскольку число на самом деле представляет собой строку символов, например, английское слово (например, слово «одиннадцать», используемое в парадоксе), в то время как, с другой стороны, возможно для обозначения любого слова с номером, например, по номеру его позиции в данном словаре или подходящей кодировкой. Некоторые длинные строки можно точно описать с помощью меньшего количества символов, чем требуется для их полного представления, что часто достигается с помощью сжатия данных . Затем сложность данной строки определяется как минимальная длина, которая требуется описанию для (однозначно) ссылки на полное представление этой строки.

Сложность Колмогорова определяется с использованием формальных языков или машин Тьюринга, что позволяет избежать неоднозначности в отношении того, какая строка является результатом данного описания. Можно доказать, что сложность Колмогорова невычислима. Доказательство от противного показывает, что если бы можно было вычислить колмогоровскую сложность, то также можно было бы систематически генерировать парадоксы, подобные этому, то есть описания короче, чем то, что подразумевает сложность описываемой строки. То есть определение числа Берри парадоксально, потому что на самом деле невозможно вычислить, сколько слов требуется для определения числа, и мы знаем, что такое вычисление невозможно из-за парадокса.

Смотрите также

Примечания

использованная литература

внешние ссылки