Кмк, пример с «git [command]» больше напоминает DIP и SR, не в один в один, но все же, т.е. git — это верхний абстрактный уровень, который под собой использует специфичные реализации — отдельные файлы, каждый из которых хорошо делает свою работу (SR).
Разве нет?
Согласен.
Я сейчас прихожу к мысли, что мой подход, наоборот, только еще раз показывает несчетность континуума, только с другой стороны. Пытаясь пронумеровать [0,1] способом, который я привел, мы просто получим бесконечное множество бесконечных алгоритмов, которые никогда не вычслят точный порядковый номер иррационального числа.
1. Определение: континуум — мощность множества всех чисел из сегмента [0,1].
2. Теорема: множество континуума несчетно. Доказательство опирается на расмотренный выше диагональный метод Кантора.
3.… много разных определений, лемм, теорем…
4. Теорема Теорема Кантора — Бернштейна (упрощенно): если между множествами существует биекция, то |A| = |B|.
5. Устанавливаем биекцию между [0,1] и R, из чего, согласно (4) следует равномощность [0,1] и R.
Но, равномощность-то есть, однако несчетность — это пункт 2, а его доказательство опирается на диагональный метод Кантора, который, как я писал в статье вызывает у меня сомнения. Не могу объяснить, это на каком-то интуитивном уровне происходит.
Собственно, именно с целью прояснить этот момент (в первую очередь для себя), я и згорелся идей рассмотреть данный вопрос с другого ракурса, используя алгоритмический подход. Свои размышления я запостил на хабр с целью получить обратную связь от сообщества. Иногда так бывает, что самому трудно увидеть ошибку в своих же рассуждениях :-). И, скорее всего, данный подход поможет (в первую очередь — мне) согласиться с правильностью диагонального метода Кантора. Т.к. у моего подхода уже вскрылось множество недостатков, за что спасибо всем, кто на все такие недостатки обратил внимание в комментариях.
P.S. Если предложенный мной алгоритм имеет ошибку, которую я, в силу своей невнимательности, не вижу – большая просьба написать об этом в комментариях.
P.P.S Если же ошибки нет – то получается, что |[0,1]| = |N|! Т.е. ВСЕ действительные числа из диапазона [0,1] можно пронумеровать!
Идея была вот в чем.
В множестве иррациональных чисел – любое число, например, Pi, √2, √3, e, Pi/n, e/n, √2/n, √3/n и т.д. — имеет бесконечное множество символов в записи, но это конкретное число, которое существует само по себе.
Чтобы получить все цифры в записи иррационального можно, например, воспользоваться методом приближения иррациональных чисел рациональными, но этот процесс будет бесконечным и мы никогда не получим все знаки в иррациональном числе, но при этом, это вполне конкретное число, существующее само по себе! Т.о. иррациональное число можно представить как бесконечно работающий алгоритм, который на каждой очередной итерации уточняет данное число, при этом процесс уточнения происходит бесконечно. Вопрос 1. Если нельзя, то почему?
В предложенном подходе порядковый номер любого числа N из [0,1] (обозначаемый как C(N)) есть функция от конкретных цифр его записи.
В такой интерпретации, порядковый номер иррационального числа становится таким же не определенным, как и все циры в записи самого иррационального числа. Порядковый номер иррационального будет вычисляться также бесконечно долго, как и все цифры в записи этого числа. Вопрос 2. Но, если доказано, что рациональные числа существуют сами по себе, тогда почему мы не можем утверждать, что при такой (алгоритмической) интерпретации их порядковые номера тоже существуют сами по себе?
Рассмотрим пример. Обозначим порядковый номер числа Pi/5 как C(Pi/5). С алгоритмической точки зрения, все знаки в записи числа Pi/5 будут утояняться бесконечно долго, => порядковый номер C(Pi/5) тоже будет вычисляться бесконечно долго.
Возьмем сколь угодно большое число, X.
Разложим его на сумму степеней двойки: X = 2^1 + 2^2 +… + 2^k + L(k+1)
Если L(k+1) — нечтное — то цифра на уровне k+1 — 1, если четное — то — 0.
Далее, используя соотношение: Lk = (Lk-1 — 1)*S + N + 1, мы всегда сможем вычислить порядковый номер цифры для предыдущего уровня.
Т.о. двигясь в сторону корня дерева (вверх) и мы в итоге построим конкретное десятичное число, которому соответсвует данный номер.
Но это подразумевает, что мы должны использовать опредленное значение номера. Т.е. если рассмотреть номер для числа Pi/5 — число С(Pi/5), то обратное восстановление невозможно в силу того, что сам номер — не определен, т.к. он вычисляется бесконечно долго. Как-то так…
Алгоритм не пропускает ни одного числа, т.к. он подсчитывает все числа в таблице m*nm.
m — это количество знаков после запятой, n — алфавит системы счисления.
Иными словами, алгоритм подсчитывает количество размещений с повторениями для каждой позиции после запятой. Количество размещений увеличивается экспоненциально с каждой следующей позицией.
Для десятичных дробей, записанных в десятичной системы счисления алгоритм последовательно будет выдавать такой результат (порядковые номера присваиваются слева направо):
m = 1
0,0; 0,1; ...; 0,9 — всего 10 комбинаций.
m = 2
0,00; 0,01; 0,02; ...; 0,10; 0,11; ...; 0,90; 0,91; ...; 0,99
Т.о. для m=2 получается 100 комбинаций, а для обоих уровней общее количество комбинаций — уже 110.
m = 3
Т.о. для m=3 получается 1000 комбинаций
…
m = k
Количество всевозможных комбинаций — 10k
k — растет линейно, а количество комбинаций, соответствующее k — экспоненциально.
Рассматривая проблему континуума с алгоритмической точки зрения, любое рациональное число из [0,1] — вычисляется бесконечно долго, а т.к. его порядковый номер — функция от цифр самого числа, то и порядковый номер таких чисел вычисляется бесконечно долго. Поэтому результаты арифметических действий над такими номерами тоже вычисляются бесконечно долго.
Pi/3 > 1, выходит за интервал [0,1]. Над обобщением для чисел за пределами диапазона [0,1] — еще не размышлял.
Предлагаю рассмотреть числа: Pi/4 и Pi/5.
Алгоритм проходит по всем уровням последовательно, сверу вниз, а на каждом уровне слева направо, от меньших чисел к большим, поэтому C(Pi/5) < C(Pi/4).
Да, получается, что алгоритм создает для двух разных форм записи одного и того же числа разные порядковые номера. И если решать задачу обратного отображения N -> R, то два разных N будут фактически соответсвовать одной и той же дроби, просто записанной в разных формах. Пока не знаю, как это устранить.
Согласен, что взаимо-однозначного соответсвия нет, но алгоритм устанавливает соответсвие в одну сторону каждому R на [0,1] ставит в соответствие N. Для обратной задачи нужно подумать либо доказать, что такого алгоритма нет.
Еще один изъян алгоритма, описан с комментарии: habr.com/post/358526/#comment_11354864.
Как его устранить — пока тоже нет идей.
Вот тут надо подумать, возможен ли алгоритм для обратного поиска, чтобы по номеру однозначно определять десятичную дробь, которая ему соответствует.
Пока идей как это сделать нет.
Ну в таком же ключе можно сказать, что и номер для такого числа существует сам по себе.
Есть существование числа самого по себе, а есть конкретная запись числа. Мы можем абстрагироваться от конкретных цифр числа — просто введя обозначение, например Pi/4. Точно также, мы можем асбтрагировать номер этого числа, пусть порядковый номер числа Pi/4 будет C(Pi/4). И в этом смысле он также существует сам по себе. Где противоречие?
habr.com/post/358526/#comment_11354670
Я просто предлагаю рассматривать биекцию как алгоритм. Потому что само понятие «бесконечное число» по смысло ближе всего к понятию «бесконечно работающий алгоритм, генерирующий это число». В этом смысле мы можем пронумеровать числа на [0,1]. Просто мы никогда не узнаем точного номера числа 0,01001000100001…, т.к. никогда не узнаем, как выглядит число полностью.
ну тогда надо говорить так — между числом которогоне существует и порядковым номером, которого не существует.
Число Pi/4 мы уточняем знак за знаком, это бесконечный итеративный процесс. По мере получения очередного знака, мы получаем конкретное число и вычисляем для него порядковый номер.
Т.е. бесконечную непереодическую дробь — можно рассматривать как несуществующее число, а можно рассматривать, как результат работы некоторого бесконечного алгоритма, который на каждом шаге выдает очередную цифру и в этом смысле порядковый номер можно тоже рассматривать как некое число, являющееся результатом работы бесконечного алгоритма.
Но мы же можем последовательно вычислять последовательность знаков после запятой, после чего алгоритмически вычислять порядковый номер для Pi/4. Просто это будет бесконечный процесс, т.к. у числа бесконечно много знаков после запятой. Но т.к. есть алгоритм, то и есть взаимо-однозначное соответсвие.
, то CPU читает кэш-линию (размером 64 байта) из RAM. После чего, при обращении к любому из этих байтов, время чтения будет минимально, т.к. они уже в кэше, что, собственно, и вызвало мой вопрос )) Но на самом деле нас интересуют только те индексы, которые кратны 4096.
CPU читает из RAM не побайтно, а кэш-линиями. Допустим CPU прочитал кэш-линию. Во время цикла
for (i = 0; i < 256; i++) {
if (is_in_cache(userspace_array[i*4096])) {
// Got it! *kernel_space_ptr == i
}
}
мы определяем индекс массива, который читается быстро, но в то же время рядом с ним находятся еще несколько байтов из этой же кэш-линии и которые тоже будут быстро читаться.
Вопрос: как нам понять какой именно из этих индексов — нужное нам значение из закрытой области RAM?
Рассказывать о технологиях, не упоминая области их применимости — это как рассказывать про инженерное устройство мостов, не рассказав перед этим про сопромат :-) Поэтому «сопромат» в статьях такого уровня необходим.
Не совсем согласен, т.к. у любой статьи всегда имеется определенный уровень абстракции, на который она изначально рассчитана.
Про мосты можно тоже по-разному рассказывать, можно «на-пальцах», а можно так глубоко свалиться в детали, что вообще уйти в петлевую квантовую гравитацию. :-)
Разве нет?
Я сейчас прихожу к мысли, что мой подход, наоборот, только еще раз показывает несчетность континуума, только с другой стороны. Пытаясь пронумеровать [0,1] способом, который я привел, мы просто получим бесконечное множество бесконечных алгоритмов, которые никогда не вычслят точный порядковый номер иррационального числа.
1. Определение: континуум — мощность множества всех чисел из сегмента [0,1].
2. Теорема: множество континуума несчетно. Доказательство опирается на расмотренный выше диагональный метод Кантора.
3.… много разных определений, лемм, теорем…
4. Теорема Теорема Кантора — Бернштейна (упрощенно): если между множествами существует биекция, то |A| = |B|.
5. Устанавливаем биекцию между [0,1] и R, из чего, согласно (4) следует равномощность [0,1] и R.
Но, равномощность-то есть, однако несчетность — это пункт 2, а его доказательство опирается на диагональный метод Кантора, который, как я писал в статье вызывает у меня сомнения. Не могу объяснить, это на каком-то интуитивном уровне происходит.
Собственно, именно с целью прояснить этот момент (в первую очередь для себя), я и згорелся идей рассмотреть данный вопрос с другого ракурса, используя алгоритмический подход. Свои размышления я запостил на хабр с целью получить обратную связь от сообщества. Иногда так бывает, что самому трудно увидеть ошибку в своих же рассуждениях :-).
И, скорее всего, данный подход поможет (в первую очередь — мне) согласиться с правильностью диагонального метода Кантора. Т.к. у моего подхода уже вскрылось множество недостатков, за что спасибо всем, кто на все такие недостатки обратил внимание в комментариях.
Идея была вот в чем.
В множестве иррациональных чисел – любое число, например, Pi, √2, √3, e, Pi/n, e/n, √2/n, √3/n и т.д. — имеет бесконечное множество символов в записи, но это конкретное число, которое существует само по себе.
Чтобы получить все цифры в записи иррационального можно, например, воспользоваться методом приближения иррациональных чисел рациональными, но этот процесс будет бесконечным и мы никогда не получим все знаки в иррациональном числе, но при этом, это вполне конкретное число, существующее само по себе! Т.о. иррациональное число можно представить как бесконечно работающий алгоритм, который на каждой очередной итерации уточняет данное число, при этом процесс уточнения происходит бесконечно. Вопрос 1. Если нельзя, то почему?
В предложенном подходе порядковый номер любого числа N из [0,1] (обозначаемый как C(N)) есть функция от конкретных цифр его записи.
В такой интерпретации, порядковый номер иррационального числа становится таким же не определенным, как и все циры в записи самого иррационального числа. Порядковый номер иррационального будет вычисляться также бесконечно долго, как и все цифры в записи этого числа. Вопрос 2. Но, если доказано, что рациональные числа существуют сами по себе, тогда почему мы не можем утверждать, что при такой (алгоритмической) интерпретации их порядковые номера тоже существуют сами по себе?
Рассмотрим пример. Обозначим порядковый номер числа Pi/5 как C(Pi/5). С алгоритмической точки зрения, все знаки в записи числа Pi/5 будут утояняться бесконечно долго, => порядковый номер C(Pi/5) тоже будет вычисляться бесконечно долго.
Возьмем сколь угодно большое число, X.
Разложим его на сумму степеней двойки: X = 2^1 + 2^2 +… + 2^k + L(k+1)
Если L(k+1) — нечтное — то цифра на уровне k+1 — 1, если четное — то — 0.
Далее, используя соотношение: Lk = (Lk-1 — 1)*S + N + 1, мы всегда сможем вычислить порядковый номер цифры для предыдущего уровня.
Т.о. двигясь в сторону корня дерева (вверх) и мы в итоге построим конкретное десятичное число, которому соответсвует данный номер.
Но это подразумевает, что мы должны использовать опредленное значение номера. Т.е. если рассмотреть номер для числа Pi/5 — число С(Pi/5), то обратное восстановление невозможно в силу того, что сам номер — не определен, т.к. он вычисляется бесконечно долго. Как-то так…
m — это количество знаков после запятой, n — алфавит системы счисления.
Иными словами, алгоритм подсчитывает количество размещений с повторениями для каждой позиции после запятой. Количество размещений увеличивается экспоненциально с каждой следующей позицией.
Для десятичных дробей, записанных в десятичной системы счисления алгоритм последовательно будет выдавать такой результат (порядковые номера присваиваются слева направо):
m = 1
0,0; 0,1; ...; 0,9 — всего 10 комбинаций.
m = 2
0,00; 0,01; 0,02; ...; 0,10; 0,11; ...; 0,90; 0,91; ...; 0,99
Т.о. для m=2 получается 100 комбинаций, а для обоих уровней общее количество комбинаций — уже 110.
m = 3
Т.о. для m=3 получается 1000 комбинаций
…
m = k
Количество всевозможных комбинаций — 10k
k — растет линейно, а количество комбинаций, соответствующее k — экспоненциально.
А в моих рассуждениях разве есть противоречие аксиомам поля?
Предлагаю рассмотреть числа: Pi/4 и Pi/5.
Алгоритм проходит по всем уровням последовательно, сверу вниз, а на каждом уровне слева направо, от меньших чисел к большим, поэтому C(Pi/5) < C(Pi/4).
Еще один изъян алгоритма, описан с комментарии: habr.com/post/358526/#comment_11354864.
Как его устранить — пока тоже нет идей.
Пока идей как это сделать нет.
Есть существование числа самого по себе, а есть конкретная запись числа. Мы можем абстрагироваться от конкретных цифр числа — просто введя обозначение, например Pi/4. Точно также, мы можем асбтрагировать номер этого числа, пусть порядковый номер числа Pi/4 будет C(Pi/4). И в этом смысле он также существует сам по себе. Где противоречие?
Я просто предлагаю рассматривать биекцию как алгоритм. Потому что само понятие «бесконечное число» по смысло ближе всего к понятию «бесконечно работающий алгоритм, генерирующий это число». В этом смысле мы можем пронумеровать числа на [0,1]. Просто мы никогда не узнаем точного номера числа 0,01001000100001…, т.к. никогда не узнаем, как выглядит число полностью.
Число Pi/4 мы уточняем знак за знаком, это бесконечный итеративный процесс. По мере получения очередного знака, мы получаем конкретное число и вычисляем для него порядковый номер.
Т.е. бесконечную непереодическую дробь — можно рассматривать как несуществующее число, а можно рассматривать, как результат работы некоторого бесконечного алгоритма, который на каждом шаге выдает очередную цифру и в этом смысле порядковый номер можно тоже рассматривать как некое число, являющееся результатом работы бесконечного алгоритма.
Когда мы делаем , то CPU читает кэш-линию (размером 64 байта) из RAM. После чего, при обращении к любому из этих байтов, время чтения будет минимально, т.к. они уже в кэше, что, собственно, и вызвало мой вопрос )) Но на самом деле нас интересуют только те индексы, которые кратны 4096.
мы определяем индекс массива, который читается быстро, но в то же время рядом с ним находятся еще несколько байтов из этой же кэш-линии и которые тоже будут быстро читаться.
Вопрос: как нам понять какой именно из этих индексов — нужное нам значение из закрытой области RAM?
Не совсем согласен, т.к. у любой статьи всегда имеется определенный уровень абстракции, на который она изначально рассчитана.
Про мосты можно тоже по-разному рассказывать, можно «на-пальцах», а можно так глубоко свалиться в детали, что вообще уйти в петлевую квантовую гравитацию. :-)