Парадокс в основах устного счета

[terminator-II]

я транслирую сюда топик из другого форума, ответьте plz

rtf на scientific.ru 29.04.09 13:51 писал(а):

Пусть нам задано число `N`, что это означает? Это означает, что задан алгоритм достижения числа, представленного в самой простой, т.е. унарной системе счисления.

Наверное, наиболее абстрактно задать число можно так:

для числа `N` представленного в унарной системе счисления, подбирается алгебраическая структура, с множеством продукций, задается порядок и число продукций `n` и задаются начальные символы (как в грамматике) или базис, в результате применений продукций к базису мы и достигаем `N`.

Можно ли утверждать, что для заданного `N` нельзя найти кодировку, в которой представлены алгебраическая структура `A(N)`, базис и продукции, зависящие от конкретного `N`, требующие меньше позиций для записи, чем `log_2 (N)`?

Можно ли "доказать", короме непосредственной проверки, что число `N` сложное по Колмогорову?

А если только непосредственной проверкой, то какой смысл может она иметь, если нам надо будет перебрать `N` чисел, и для каждого проверить, что это не кодировка алгоритма сжимающего `N`?

Надеюсь я не нарушаю правил этого форума.

// Отредактировано: добавлена цитата. / GAA

[Утундрий]

terminator-II, Вы убили мой моск (

[ASA]

Поток сознания.

[Xaositect]

Не понял, в чем вопрос.
Если у нас есть некая единая система обозначений для чисел, то в ней длина обозначения числа $N$ $l(N) \geq c \log N$ для бесконечного числа значений $N$.
Если нам заранее задано число $N_0$, то мы всегда сможем взять систему обозначений, в которой оно представляется одним символом (ну хотя бы такую: обозначением для $N$ будет двоичная запись $N - N_0$)

[GAA]

Участники форума оценили сообщение как недостаточно четко формулирующее предмет обсуждения. Тема перемещена из "Помогите решить/разобраться (M)" в карантин. Почему это произошло, можно понять, прочитав тему Что такое карантин и что нужно делать, чтобы там оказаться. Там же описано, как исправлять ситуацию (см. 4. Недостаточно внятная информация о предмете обсуждения).