Текстовый парадокс

[psilogic]

Тексты могут определять целые числа. Например текст "три" определяет число 3, текст "два в квадрате" определяет число 4.

Рассмотрим все возможные тексты на русском языке длиной не более 1000 символов. Количество таких текстов конечно. Верхний предел - количество возможных комбинаций из 1000 символов. Каждый символ может быть русской буквой (большой или малой), пробелом, знаком препинания, цифрой. В общем, число разных символов тоже ограничено, скажем сотней. Итого может быть не более 100 в степени 1000 текстов. Число астрономически большое, но конечное.

Среди текстов возьмем тот, который определяет самое большое целое число по сравнению с другими текстами. Возьмем число на единицу большее.
--
Текст выше черточек "--" написан на русском языке и длиной длиной не более 1000 символов. Он определяет целое число, которое... больше максимально возможного для таких текстов. Парадокс.
--
В чем здесь дело?


Данный парадокс представляет собой чистый софизм, то бишь рассуждение со скрытой логической ошибкой. Неявно предполагалось, что учитываются только те тексты, которые определяют только одно число. Для рассуждения важно, чтобы число определенных чисел было конечно, поскольку конечное подмножество целых чисел имеет максимум. Если же хотя бы один текст определяет бесконечное количество целых чисел, то рассуждение не получается. Например, текст "все целые числа" все портит.

Кажется очевидным, что такие тексты не надо при подсчете принимать во внимание, как и те тексты, которые не выражают вообще никаких чисел или выражают, но не целые (чтобы не заморачиваться введением меры).

Но приведенный текст как раз и относится к тем текстам, что не определяют конкретного числа, либо определяют бесконечное количество чисел, просто это хорошо скрыто.

В тексте есть инструкция: "возьмем тот, который определяет самое большое целое число по сравнению с другими текстами". Допустим мы определили максимум M для всех прочих текстов. А какое число определяет текст из парадокса?

Надо признать, что никакое, т.е. этот текст должен быть исключен из рассмотрения. И максимальное число - по прежнему M.

Если же мы предположим, что текст определяет некое конкретное число Z, тогда, перечитав текст еще раз, мы придем к выводу, что он определяет число max(Z,M) + 1. Перечитав еще раз, мы придем к выводу, что он определяет число max(Z,M) + 2. И так далее, бесконечная рекурсия (или индукция - как кому нравится). Тогда этот текст определяет бесконечное количество чисел, а такие тексты тоже полагается из рассмотрения исключать. И максимальное число - по прежнему M, и никакого парадокса.

Comments

[a-v-k-73.livejournal.com]

Вообще-то, это модификация классического парадокса наивной теории множеств.

[psilogic.livejournal.com]

Они оба используют рекурсию. В остальном - это разные вещи.

Парадокс Рассела - настоящий парадокс, который соблюдает правила логической системы, в которой он построен (правила наивной теории множеств). там нет никаких скрытых уловок, спрятанных нарушений логики. И, тем не менее, он приводит к противоречию. То есть, наивная теория множеств противоречива.

Это же парадокс содержит скрытое нарушение логики. Как только нарушение устраняется, противоречие исчезает. Поэтому это парадокс из разряда софизмов как апории Зенона.

[a-v-k-73.livejournal.com]

Я не о классическом Расселе, вообще-то.

Рассмотрим множество, содержащее все объекты, которые с использованием русского языка могут быть описаны фразой, состоящей из менее, чем двадцати слов. Рассмотрим объект, который не может быть описан фразой, состоящей из менее чем двадцати слов. С одной точки зрения, этот объект попадает в множество, с другой — не попадает :)

[psilogic.livejournal.com]

Это парадокс тоже из разряда софизмов. Не определено строго понятие "описан фразой".

"объект, который не может быть описан фразой, состоящей из менее чем двадцати слов" - это фраза. Но описывает ли она объект? Непонятно.

Если определить понятие более строго, то можно прийти к разным выводам. Например, к тому, что такого объекта не существует, а описать можно все объекты. Например, фраза "любой объект" - описывает все объекты.

Или, как вариант, можно прийти к тому, что фраза все-таки не описывает объект. Надо уточнять, что есть "описан фразой".

[a-v-k-73.livejournal.com]

Ну да, ну да... Но это рассуждение как раз очень хорошо иллюстрирует основную слабость наивной теории множеств :)

[psilogic.livejournal.com]

А вообще тот парадокс, что я привел, он, конечно классический - в том смысле, что давно известен :) Как и само развлечение - рассматривать парадоксы :)

[a-v-k-73.livejournal.com]

Да, я в курсе :) Есть куча его вариантов, в том числе и тот, что я написал...

[psilogic.livejournal.com]

Опять же свойство "быть вариантом чего-либо" строго не определено, так что - как пожелаете ;)

[fregimus.livejournal.com]

Конечно, никакого парадокса тут нет. Например, текст «самое большое целое число» не определяет некоего самого большого целого числа. Русский язык не обладает строгостью формальной символьной системы, поскольку он опирается на понятия вне системы. Иными словами, причинение смысла строке из русских букв происходит вне системы, в которой она формально образуется, и потому, несомненно, является произволом.

[fregimus.livejournal.com]

А Вы математик по образованию или психолог, если не секрет? Фраза «чтобы не вводить меру» выдает математика с головой… :-)

[psilogic.livejournal.com]

По второму свежеполученному образованию - психолог. А по первому образованию я системный программист. А поскольку в те времена компьютеры рассматривались в первую очередь (и почти в последнюю) как _вычислительная_ техника, то часы нам распределяли перимерно так: 40% - математика, 20% - физика разных сортов (ну а какая физика без математики), 30% - программирование, ну и 10% - все остальное. В СССР любили эдакое "фундаментальное" образование, и я, в общем, не жалею - мозги прочищает и вполе подготавливает к веселостям профессии :)

[fregimus.livejournal.com]

В СССР любили эдакое "фундаментальное" образование
Так и я, собственно, оттуда же.

[psilogic.livejournal.com]

:)

концовка

[falcao.livejournal.com]

Я считаю, что тексты, которые не задают какое-то одно число, рассматривать вообще не надо. То есть текст "два или три" не задаёт никакого конкретного числа по определению.

С тем текстом, который у Вас, происходит немного более сложное явление. Прежде всего, может так получиться, что числа, задаваемые текстами, расположены не подряд. Например, числа типа 10^10^10... с "каскадом" степеней можно задать вполне короткими текстами, в то время как промежуточные -- уже не обязательно. Поэтому "концовка" Вашей истории должна выглядеть так. Число M обладает тем свойством, что среди уже "зарегистрированных" текстов есть такие, которые задают все числа 1, 2, ..., M, но число M+1 уже не задаётся. (При этом числа M+2, M+3, ... вполне могут чем-то задаваться.) В такой ситуации "нашему" тексту мы должна сопоставить M+1. Но далее при "ревизии" происходит вот что. Теперь уже числа 1, 2, ..., M+1 какими-то текстами заданы, и надо найти такое k>=2, что M+k -- наименьшее из чисел, пока что ничем не задаваемое. Как уже говорилось, совсем не обязательно k=2. При "повторном чтении" мы сопоставляем M+k "нашему" тексту, но теперь число M+1 у нас высвободилось. Это значит, что если мы снова читаем текст, то присваиваем ему M+1. И далее происходит не увеличение значений, а "мерцание" между M+1 и M+k.

Re: концовка

[psilogic.livejournal.com]

Так это получается уже немного другой парадокс. Вместо слов:

"Среди текстов возьмем тот, который определяет самое большое целое число по сравнению с другими текстами."

надо напейсать:

"Среди текстов возьмем тот, который определяет самое малое целое число (M), после которого идет минимальное число (M+1), не заданное другими текстами."

- и тогда да, получится мерцание, и тут можно припомнить уже парадокс лжеца, где тоже мерцание :)

[andy1618.livejournal.com]

Кстати, интересно, чему равны максимальные значения для текстов небольшой длины (1, 2, 3, ...)?
Подозреваю, что эти тексты будут состоять из циферок и значков факториала :)

[psilogic.livejournal.com]

ага, что-нибудь типа:
9!!!...
:)

[andy1618.livejournal.com]

Похоже, всё интереснее - в википедии пишут (http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB) про знак двойного факториала. К примеру, 9!! = 1*3*5*7*9. Т.е., по-видимому, для повторного применения обычного факториала надо ввести скобки: (9!)! - это уже 5 знаков :)
Тогда вырисовываются следующие рекордсмены:
9
9!
99!
А вот с 4-мя символами уже сложнее. Есть вариант 999!, но есть и 9^9! (крышка - возведение в степень). Причём, независимо от приоритета операций (крышка vs факториал), второе число будет больше:
999! ~= 10^2500
9^(9!) ~= 10^300000
(9^9)! > 10^400000000

И, самый интересный вопрос: начиная с какой длины в строке-рекордсмене появятся русские буквы? Есть подозрения, что ни с какой, т.е. задача инвариантна к языку :)
Даже пресловутый "googol" тут не поможет :)

[psilogic.livejournal.com]

А если так: "факториал, примененный миллиард раз к 9"? :)

[andy1618.livejournal.com]

Во, отлично! Задачка реанимирована! (а то было бы неинтересно). :)

Господин логик, не найдете ли ошибку?..

[alisarin.livejournal.com]

Просто я думаю, что приводимое ниже рассуждение ошибочно, и прошу совета:

В доказательстве теоремы о неполноте Гедель следовал схеме рассуждений, близкой к той, что проводится в так называемом «парадоксе Ришара» (по имени описавшего его в 1905 году французского математика).
В чем же состоит этот парадокс? Возьмем какой-нибудь язык (например, русский), средствами которого можно описывать и определять все чисто арифметические свойства чисел. Рассмотрим определения, которые можно сформулировать на этом языке. Ясно, что некоторые термины, относящиеся к арифметическим свойствам, определить явным образом все равно не удастся, хотя, конечно, мы можем понимать смысл этих слов и без определений. Несущественно, какие именно термины принять за исходные; мы можем, например, считать, что мы понимаем смысл предложений «целое число делится на другое целое число», «целое число является произведением двух целых чисел» и т.п. Свойство быть простым числом тогда можно определить следующим образом: «не делится ни одно целое число, кроме самого себя и числа 1»; свойство быть точным квадратом: «быть произведением некоторого целого числа на то же число» и т.п.
Каждое такое определение состоит из конечного числа слов, а потому и из конечного числа букв алфавита. Поэтому мы можем ввести для таких словесных определений отношение порядка, считая одно определение предшествующим другому, если число букв, из которых состоит первое определение, меньше числа букв, составляющих второе определение. В тех же случаях когда два определения состоят из одного и того же числа букв, одно из них считать предшествующим другому в обычном лексикографическом (алфавитном, словарном) порядке. Исходя из такого упорядочения можно расположить все определения рассматриваемого вида в последовательность, сопоставив каждому из них единственное натуральное число – номер в этой же последовательности. Тогда самое короткое (и стоящее ранее других в алфавитном порядке) определение получит номе 1, следующее за ним – номер 2 и т.д.
Поскольку каждому определению сопоставлено некоторое натуральное число, то может оказаться, что в некоторых случаях число, сопоставленное какому-нибудь определению, само будет обладать определяемым свойством. Приведем пример. Пусть определяющее выражение «не делится ни на одно натуральное число, кроме самого себя и числа 1» оказалось в нашей последовательности на 17-м месте. Ясно, что сопоставленное ему число 17 само подпадает под это определение. Пусть, с другой стороны, определяющее выражение «быть произведением некоторого натурального числа на то же самое число» получило номер 15. само число 15, очевидно, не является точным квадратом и потому данным свойством не обладает. Назовем числа, не обладающие свойствами, определяемыми предложениями, которым они соответствуют в описанной выше нумерации, ришаровыми. Таким образом, «х – ришарово число» – это просто сокращенное выражение «х не обладает свойством, определяемым предложением, имеющим номер х в данной словарной последовательности определяющих предложений». Таким образом, число 17 в приведенном примере не является ришаровым, а число 15 является.
Теперь можно сформулировать парадокс Ришара. Определяющее выражение для свойства быть ришаровым числом описывает, очевидно, некоторое арифметическое свойство натуральных чисел. Значит, само определяющее выражение входит в описанную выше последовательность определяющих выражений. Но тогда оно имеет в этой последовательности некий номер. Обозначим его через n. Является ли число n ришаровым? Здесь неизбежно противоречие: число n является ришаровым в том и только в том случае, если оно не обладает свойством, описанном в предложении, которое имеет номер n, т.е. не обладает свойством быть ришаровым! Короче говоря, n ришарово тогда и только тогда, когда оно не ришарово, т.е. утверждение «n – ришарово» является одновременно и истинным и ложным.

--
Правилен ли данный вывод? (Из: http://sergey-shilov.livejournal.com/4248.html)

Re: Господин логик, не найдете ли ошибку?..

[psilogic.livejournal.com]

То, что я в этом топике рассмотрел - это и есть парадокс Ришара (или вариация на тему). То, что привели вы - это другая вариация на ту же тему. Ошибка в рассуждении - второе слово "очевидно".

Re: Господин логик, не найдете ли ошибку?..

[alisarin.livejournal.com]

Спасиба!

Я бы философски помудрил бы эту ошибочность иначе, но ладно :)

[vot2.livejournal.com]

Вот привожу свои размышления, которые в большинстве своем совпадают с приведенными выше.

Составим упрощенную модель приведенного парадокса.
Введем псевдоязык. Для начала, в нем будет один символ "1" (единица или палочка). Теперь с помощью этого текста будем формировать числа: "1", "11", "111", - ограничим длину в 3 символа. Тогда в нашем случае получим, что максимальное число будет "111" (тройка).
Введем в наш псевдоязык следующий символ "м"(эм или максимум). Определим его так - это максимальное число, которое мы можем составить с помощью нашего псевдоязыка и ограничиваясь 3-мя символами (определение сформулировано по аналогии с ситуацией в парадоксе).
Начнем с того, что "м" будет равен уже известному нам максимуму - "м"="111". Теперь мы можем сделать еще большее число "м1". И тогда наш максимум "м" становится не самым максимальным, который можно построить из "1" и "м".
Конец модели, далее размышления.

    Думаю здесь стоит разбираться с самим определением максимума "м". В одном случае можно считать, что "ммм" будет окончательным максимумом (9 единичек), самым большим числом нашей системы. В другом - как бы заново попытаться присвоить "м"-максимуму новое значение в виде числа "ммм", и получить масаракш в виде "м"="ммм".
    В обоих случаях нужно дорабатывать определение символа "м", раз уж такая неоднозначность имеет место быть. А для второго случая, наверное, следует доработать еще и саму систему, добавив туда понятие итерации или еще чего полезное из чего можно будет получить хоть какой-то результат. Также, доработав систему или определение, можно исключить из нее все сочетания вида "м1", "м11", "мм1"... - похожие на число большее чем "м"="111". Но последнее, наверно, равносильно исключению символа "м" из нашего псевдо языка, оставляя понятие максимум на уровне подразумеваемости, вне системы.
    Кроме определения максимального числа в условиях данного парадокса есть еще неточности. Так, например, можно "реализовать" любое наперед заданное число. Достаточно подразумевать под символом "м" число равное этому наперед заданному числу. Или под "м" подразумевать такую операцию с помощью которой можно будет получить это самое число (вроде х="м1" или х="1м1"). А еще, символом "м" мы можем обозначить самое большое число на свете. И по условиям нашей подразумеваемости прибавить к такому числу что-либо будет уже делом некорректным.