Введение

Самоссылочный парадокс. Парадокс Берри — это самоссылочный парадокс, возникающий из выражения, подобного: «Наименьшее положительное целое число, которое нельзя определить менее чем в шестидесяти символах» (фраза состоит из пятидесяти семи символов). Бертран Рассел, первым обсудивший этот парадокс в печати, приписал его Г. Г. Берри (1867–1928), младшему библиотекарю Бодлианской библиотеки Оксфордского университета. Рассел называл Берри «единственным человеком в Оксфорде, понимавшим математическую логику». Жан-Ив Жирар назвал этот парадокс «парадоксом Ришара».

Резолюция

Парадокс Берри, сформулированный выше, возникает из-за систематической двусмысленности в слове "определимый". В других формулировках парадокса Берри, например, в той, что звучит как: "не называемый менее чем...", термин "называемый" также обладает этой систематической двусмысленностью. Такие термины порождают логические порочные круги. Другие термины с подобной двусмысленностью: выполнимый, истинный, ложный, функция, свойство, класс, отношение, кардинал и ординал. Решение одного из этих парадоксов означает точное определение места, где мы допустили ошибку в использовании языка, и предоставление ограничений на использование языка, позволяющих их избежать. Это семейство парадоксов можно разрешить, включив в язык стратификацию значений. Термины с систематической двусмысленностью можно записывать с индексами, указывающими, что один уровень значения считается приоритетнее другого при их интерпретации. "Число, которое нельзя назвать менее чем одиннадцатью словами" может быть названо менее чем одиннадцатью словами в рамках этой схемы. Однако, можно обратиться к работам Альфреда Тарски по парадоксу лжеца, чтобы понять, как это решение в языках оказывается несостоятельным. Альфред Тарски диагностировал парадокс как возникающий только в "семантически замкнутых" языках, под которыми он понимал язык, в котором возможно одному предложению утверждать истинность (или ложность) другого предложения в том же языке (или даже самого себя). Чтобы избежать самопротиворечия, при обсуждении значений истинности необходимо представлять уровни языков, каждый из которых может утверждать истинность (или ложность) только предложений на более низком уровне. Таким образом, когда одно предложение ссылается на значение истинности другого, оно семантически выше. Предложение, на которое ссылаются, является частью "язык объекта", в то время как ссылающееся предложение считается частью "мета-языка" по отношению к языку объекта. Допустимо, чтобы предложения в "языках", находящихся выше в семантической иерархии, ссылались на предложения ниже в "языковой" иерархии, но не наоборот. Это предотвращает самореферентность системы. Однако эта система неполна. Было бы желательно иметь возможность делать утверждения, такие как: "Для каждого утверждения на уровне α иерархии существует утверждение на уровне α+1, утверждающее, что первое утверждение ложно". Это истинное и содержательное утверждение об иерархии, определяемой Тарски, но оно относится к утверждениям на каждом уровне иерархии, следовательно, должно находиться выше каждого уровня иерархии и, таким образом, не может существовать внутри самой иерархии (хотя ограниченные версии этого утверждения возможны). Саулу Крипке приписывают выявление этой неполноты в иерархии Тарски в его широко цитируемой статье "Очерк теории истины", и она признана общей проблемой в иерархических языках.

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

Используя программы или доказательства ограниченной длины, можно построить аналог выражения Берри на формальном математическом языке, как это сделал Грегори Чейтин. Хотя формальный аналог и не приводит к логическому противоречию, он доказывает определенные теоремы о невозможности, основанные на формализованной версии парадокса Берри, и позволяет доказать теорему о неполноте Гёделя новым и значительно более простым способом. Основная идея его доказательства заключается в том, что высказывание, истинное для x тогда и только тогда, когда x = n для некоторого натурального числа n, можно назвать определением для n, а множество {(n, k): существует определение для n длиной k символов} можно показать представимым (с использованием чисел Гёделя). Затем высказывание "m – первое число, не имеющее определения длиной менее k символов" можно формализовать и показать, что оно само является определением в вышеупомянутом смысле.

Связь с Колмогоровской сложностью

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