Счётные задачи

Kisena · Post by **Kisena** » 16 Dec 2001 18:18

Ответ на первую задачу содержится в теореме:

Не более чем счетное объединение не более чем счетных множеств - не более чем счетно.

Что касается второй задачи, то мы не особо сильны в физике, но если существует некое минимальное расстояние между атомами (неважно сколь малым оно является), а также если мы примем на веру, что мир трехмерен, то вроде пересчитать атомы проблем особых нет. [img:55f26d960d]images/smiles/icon_smile.gif[/img:55f26d960d]

DmitryL · Post by **DmitryL** » 16 Dec 2001 21:59

Посвящается 100-летию Борхеса.

Есть Библиотека. В ней собраны все книги, когда-либо написанные на Земле (включая, разумеется, и те, что ещё только будут написаны). Можно ли пронумеровать эти книги натуральными числами? (1, 2, ...)
Корректнее так: достаточна ли для этой задачи мощность множества натуральных чисел?

Попутно ещё одна задача (ответа на эту вторую я не знаю):
Можно ли, используя натуральные числа, пересчитать число атомов во Вселенной _в один момент времени_?

-ЭР- · Post by **-ЭР-** » 16 Dec 2001 23:05

<blockquote>quote:<hr>Originally posted by DmitryL:
Посвящается 100-летию Борхеса.

Есть Библиотека. В ней собраны все книги, когда-либо написанные на Земле (включая, разумеется, и те, что ещё только будут написаны). Можно ли пронумеровать эти книги натуральными числами? (1, 2, ...)
Корректнее так: достаточна ли для этой задачи мощность множества натуральных чисел?
<hr></blockquote>

Вот мое понимание "Вавилонской библиотеки" Борхеса.

Возьмем буквы алфавита, неважно какого, например латинского, определим правила транслитерации, что несложно и далее рассмотрим все комбинации этих букв до длины N - объем самой большой книги в буквах. Я не очень хорошо помню комбинаторику, но по-моему, это называется размещения с повторениями. Допустим у нас есть m букв и правила транслитерации такие, что ставят конечные множества символов в соответствие этим m оригинальным буквам. Сумма размещений от 1 до N будет конечна, если N конечно. Разумно предположить, что это так (т.е. N конечно). Тогда нам хватит конечного количества натуральных чисел, чтобы занумеровать все эти книги.

Kisena · Post by **Kisena** » 16 Dec 2001 23:40

Правда, там попросили перенумеровать в том числе те, которые только будут написаны. Люди будут изобретать новые алфавиты и т.п. В общем, возможно что нужен весь натуральный ряд а не конечное множество.

-ЭР- · Post by **-ЭР-** » 17 Dec 2001 05:50

<blockquote>quote:<hr>Originally posted by Kisena:
Правда, там попросили перенумеровать в том числе те, которые только будут написаны.<hr></blockquote>

Вот именно. Допустим для начала у нас один алфавит и максимальное количество букв в любой уже написанной или той, которая только будет написана книге равно N. Любая книга, с точки зрения этой задачи, это всего лишь комбинация букв. Если мы рассмотрим все комбинации из m букв алфавита длиной 1, затем 2, 3, и так далее до N букв, то получим все возможные книги объема до N букв - и те которые написаны и те, которые предстоит написать. Это есть конечное число, если N конечно. Первая книга будет "a", вторая -"b". Далее, например, могут быть "aaa", "abba" и "asdfasdfasdfa dlkwerij".

<blockquote>quote:<hr>Originally posted by Kisena:
Люди будут изобретать новые алфавиты и т.п. <hr></blockquote>

В этом случае, если есть правила транслитерации, про которые я говорил, то все вроде бы работает. Просто у вас есть "Война и мир", написанная латинскими буквами, esli basovyi alfavit - latinitca. Момент, который я не очень понимаю - какие правила должны быть для транслитерации. Мне кажется, что просто конечности нового алфавита достаточно для конечности количества книг, хотя не уверен.

Kisena · Post by **Kisena** » 17 Dec 2001 15:54

Число правил транслитерации конечно только если Вы подразумеваете конечное число языков. Если языки будут появляться и появляться, то конечного алфавита все-таки не хватит.

Vovka · Post by **Vovka** » 17 Dec 2001 16:52

<blockquote>quote:<hr>Originally posted by DmitryL:

Есть Библиотека... <hr></blockquote>

Ну а почему-бы просто не нумеровать книги в хронологическом порядке их появления? При этом, даже если с практической точки зрения время будет дискретным, то всё равно в каждую единицу времени кол-во появившихся книг не только счётно, но даже конечно.

Vovka · Post by **Vovka** » 17 Dec 2001 17:41

<blockquote>quote:<hr>Originally posted by Kisena:
 Что касается второй задачи, то мы не особо сильны в физике, но если существует некое минимальное расстояние между атомами (неважно сколь малым оно является), а также если мы примем на веру, что мир трехмерен, то вроде пересчитать атомы проблем особых нет. [img:ed74147bac]images/smiles/icon_smile.gif[/img:ed74147bac] <hr></blockquote>

А зачём требование трёхмерности?

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

Выберем произвольно одну такую точку - номер один, и упорядочим все остальные по расстоянию до первой.
Этот способ работает для любого n-мерного пр-ва.

Drom · Post by **Drom** » 17 Dec 2001 20:59

<blockquote>quote:<hr>Originally posted by Vovka:

А зачём требование трёхмерности?
<hr></blockquote>

наверное, необходимо требование ограниченномерности (если не рассматривать извратов типа нецелочисленных измерений):

если число измерений счетно, но бесконечно, а атом - точка на этой координатной сетке, то возмем вершины куба со всеми координатами от 0 до 1 (т. е. расстояние между ними не меньше 1). тогда координатами вершины будет бесконечный вектор из нулей и единиц. ставим ему в соответствие подмножество координатных осей по которым у него 1 и получаем соответствие вершин множеству всех подмножеств счетного числа координатных осей - множество несчетное.

хмм... нигде не наврал?

-ЭР- · Post by **-ЭР-** » 17 Dec 2001 22:53

<blockquote>quote:<hr>Originally posted by Kisena:
Число правил транслитерации конечно только если Вы подразумеваете конечное число языков. Если языки будут появляться и появляться, то конечного алфавита все-таки не хватит.<hr></blockquote>

А если так посмотреть. Я считаю количесвто букв в "Войне и мире" - N и далее с поправкой на правила транслитерации, делаю все возможные комбинации. Одна из них будет оригинальной версией "Войны и мира", но латинскими буквами. Здесь философский вопрос - другая-ли эта книга по сравнению с кириллическим текстом. Я думаю, что нет.

Далее, пусть появляются новые языки и алфавиты. Это просто будет означать, с учетеом правил транслитерации, что многие комбинации, которые до этого не имели смысла - приобрели его.

Как вам такая точка зрения?

Kisena · Post by **Kisena** » 18 Dec 2001 22:29

Нам такая точка зрения нормально. [img:3ca1ab3efe]images/smiles/icon_smile.gif[/img:3ca1ab3efe] Только если допускать, что языки появляются и появляются, то нумеровать надо все конечные (но произвольной длины) слова конечного алфавита, коих счетное число.

-ЭР- · Post by **-ЭР-** » 18 Dec 2001 22:59

<blockquote>quote:<hr>Originally posted by Kisena:
Нам такая точка зрения нормально. [img:f46317fb64]images/smiles/icon_smile.gif[/img:f46317fb64] Только если допускать, что языки появляются и появляются, то нумеровать надо все конечные (но произвольной длины) слова конечного алфавита, коих счетное число.<hr></blockquote>

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

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

Та же логика может быть применена и к комбинации слов, т.е. книге.

Что я пропускаю в этих рассуждениях?

Drom · Post by **Drom** » 18 Dec 2001 23:16

<blockquote>quote:<hr>Originally posted by -ЭР-:


...

Что я пропускаю в этих рассуждениях?<hr></blockquote>

то, что книги бывают с картинками?

-ЭР- · Post by **-ЭР-** » 18 Dec 2001 23:18

<blockquote>quote:<hr>Originally posted by Drom:


то, что книги бывают с картинками?<hr></blockquote>

Тада сдаюсь [img:365ece9cd6]images/smiles/icon_smile.gif[/img:365ece9cd6]

Drom · Post by **Drom** » 18 Dec 2001 23:43

<blockquote>quote:<hr>Originally posted by -ЭР-:


Тада сдаюсь [img:6a04a5976a]images/smiles/icon_smile.gif[/img:6a04a5976a] <hr></blockquote>

[img:6a04a5976a]images/smiles/icon_smile.gif[/img:6a04a5976a] [img:6a04a5976a]images/smiles/icon_razz.gif[/img:6a04a5976a] [img:6a04a5976a]images/smiles/icon_wink.gif[/img:6a04a5976a] извините, непроизвольно вырвалось.

а вообще русские не сдаются! (дисклаймер: слово "русские" употреблено здесь в хорошем, широком смысле и к полу, национальности, сексуальной ориентации, цвету кожи и порокам опорно-двигательного аппарата никакого отношения не имеет)

1. возмем разрешение, например, человеческого глаза или другой критерий, позволяющий растризовать печатный текст (в самом плохом случая шаг растра будет межатомным расстоянием)
2. переведем все книги в растр (черно-белые в (0,1), с цветными при необходимости тоже что-нибудь придумаем)
в результате конечное число точек растра на странице и конечное число страниц в книге может составить двоичное число, которым мы эту книгу и пронумеруем!

dimach · Post by **dimach** » 18 Dec 2001 23:51

<blockquote>quote:<hr>Originally posted by Drom:


[img:54eefe0274]images/smiles/icon_smile.gif[/img:54eefe0274] [img:54eefe0274]images/smiles/icon_razz.gif[/img:54eefe0274] [img:54eefe0274]images/smiles/icon_wink.gif[/img:54eefe0274] извините, непроизвольно вырвалось.

а вообще русские не сдаются! (дисклаймер: слово "русские" употреблено здесь в хорошем, широком смысле и к полу, национальности, сексуальной ориентации, цвету кожи и порокам опорно-двигательного аппарата никакого отношения не имеет)

1. возмем разрешение, например, человеческого глаза или другой критерий, позволяющий растризовать печатный текст (в самом плохом случая шаг растра будет межатомным расстоянием)
2. переведем все книги в растр (черно-белые в (0,1), с цветными при необходимости тоже что-нибудь придумаем)
в результате конечное число точек растра на странице и конечное число страниц в книге может составить двоичное число, которым мы эту книгу и пронумеруем!<hr></blockquote>

а как быть с форматом (физическим размером) книжек ? [img:54eefe0274]images/smiles/icon_wink.gif[/img:54eefe0274]

dimach · Post by **dimach** » 18 Dec 2001 23:55

p.s. да и к чему маяться - есть ведь ISBN [img:1016084c73]images/smiles/icon_smile.gif[/img:1016084c73]

Drom · Post by **Drom** » 19 Dec 2001 00:06

<blockquote>quote:<hr>Originally posted by dimach:


а как быть с форматом (физическим размером) книжек ? [img:80623915e3]images/smiles/icon_wink.gif[/img:80623915e3] <hr></blockquote>

Boo! [img:80623915e3]images/smiles/icon_sad.gif[/img:80623915e3] так и знал - кто-нибудь постарается "уточнить" [img:80623915e3]images/smiles/icon_wink.gif[/img:80623915e3] ...
есть готовые решения - возмите формат файлов картинок (естесственно [img:80623915e3]images/smiles/icon_wink.gif[/img:80623915e3] ), архивов, сетевых протоколов - любой можно использовать для передачи размера последующего числа/текста/whatever и их частей, можно отделять в двоичных числах ширину, высоту и содержимое цифрой 2 и говорить, что получилось троичое число - мало ли что там фантазия подскажет

dimach · Post by **dimach** » 19 Dec 2001 00:11

<blockquote>quote:<hr>Originally posted by Drom:


Boo! [img:4ff93f3341]images/smiles/icon_sad.gif[/img:4ff93f3341] так и знал - кто-нибудь постарается "уточнить" [img:4ff93f3341]images/smiles/icon_wink.gif[/img:4ff93f3341] ...
есть готовые решения - возмите формат файлов картинок (естесственно [img:4ff93f3341]images/smiles/icon_wink.gif[/img:4ff93f3341] ), архивов, сетевых протоколов - любой можно использовать для передачи размера последующего числа/текста/whatever и их частей, можно отделять в двоичных числах ширину, высоту и содержимое цифрой 2 и говорить, что получилось троичое число - мало ли что там фантазия подскажет<hr></blockquote>

я имею ввиду - вот есть книжка из одного листочка А4, совершенно чистого (ну вот такая модерновая книга [img:4ff93f3341]images/smiles/icon_wink.gif[/img:4ff93f3341] )
складываем листочек пополам - получается еще более авангардистская книга формата А5, однако же результат "сканирования" обоих - одинаков (нулик). [img:4ff93f3341]images/smiles/icon_wink.gif[/img:4ff93f3341]

-ЭР- · Post by **-ЭР-** » 19 Dec 2001 00:13

<blockquote>quote:<hr>Originally posted by Drom:

[img:9f301f995a]images/smiles/icon_smile.gif[/img:9f301f995a] [img:9f301f995a]images/smiles/icon_razz.gif[/img:9f301f995a] [img:9f301f995a]images/smiles/icon_wink.gif[/img:9f301f995a] извините, непроизвольно вырвалось.
<hr></blockquote>

Да что вы, мне очень понравилось [img:9f301f995a]images/smiles/icon_smile.gif[/img:9f301f995a]

Nightmare · Post by **Nightmare** » 19 Dec 2001 05:55

<blockquote>quote:<hr>Originally posted by Drom:

[img:ddde62559f]images/smiles/icon_smile.gif[/img:ddde62559f] [img:ddde62559f]images/smiles/icon_razz.gif[/img:ddde62559f] [img:ddde62559f]images/smiles/icon_wink.gif[/img:ddde62559f] извините, непроизвольно вырвалось.

<hr></blockquote>

Ага, точно, непроизвольно вырвалось [img:ddde62559f]http://www.rusdivx.ee/rdawb/smilies/cwm8.gif[/img:ddde62559f]

[img:ddde62559f]http://www.rusdivx.ee/rdawb/smilies/cwm27.gif[/img:ddde62559f] [img:ddde62559f]http://www.rusdivx.ee/rdawb/smilies/cwm27.gif[/img:ddde62559f] [img:ddde62559f]http://www.rusdivx.ee/rdawb/smilies/cwm27.gif[/img:ddde62559f]

[ 19-12-2001: Message edited by: Nightmare ]

Kisena · Post by **Kisena** » 19 Dec 2001 18:28

<blockquote>quote:<hr>
Что я пропускаю в этих рассуждениях?
<hr></blockquote>
Ваше решение подразумевает, что при добавлении нового языка Вам, возможно, придется перенумеровать все слова. В исходной задаче требовалось найти [i:2f99428b70]одну единственную[/i:2f99428b70] нумерацию на все случаи жизни.

-ЭР- · Post by **-ЭР-** » 20 Dec 2001 01:34

<blockquote>quote:<hr>Originally posted by Kisena:

Ваше решение подразумевает, что при добавлении нового языка Вам, возможно, придется перенумеровать все слова. В исходной задаче требовалось найти [i:82c2b81584]одну единственную[/i:82c2b81584] нумерацию на все случаи жизни.<hr></blockquote>

Как не кощунственно это звучит, но слова к книге не имеют ни малейшего отношения. Я забыл сказать, что в символы любого алфавита включены все знаки препинания и пробелы, поэтому слова получаются само собой как результат комбинаций.

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