Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Нет, и быть не может. 26.08.05 13:50 Число просмотров: 3633
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 26.08.05 14:23 Количество правок: 1
|
> А можно ли получить бесконечную последовательность с
> использованием конечной рекурсии? Т.е. используя
> ограниченное количество последних знаков предыдущего
> результата? Я предполагаю, что - нет. Доказательство (не
> строгое): поскольку количество разрядов ограничено, то
> неизбежно повторение, максимум через 2^n циклов, где n -
> ширина фрейма, т.е. число используемых двоичных разрядов.
> Па-амоему я прав? Тада наличие бесконечной рекурсии в
> алгоритме вычисления будет необходимым (но не достаточным)
> условием ирациональности.
>
> И тут вкрались сомнения... Где-то здесь, похоже проскакивал
> алгоритм вычисления Пи с конечной рекурсией. Или, все-таки
> с бесконечной? Я их не смотрел - некогда. Кто с ними имел
> дело - ответте, плз.
Нет, и быть не может.
Неповторяющаяся последовательность - это аналог иррационального числа записанного в дискретной системе счисления.
Алгоритм "вычисляющий" иррациональное число может быть только итеративным, иначе сам алгоритм будет тем-же числом, записанным в другой форме (что само-по-себе очень интересно).
Любой дискретный алгоритм можно представить как некую булеву функцию от множества переменных, которая даёт результат очередной итерации.
Так как результат этой функции зависит только от входящих значений, то для генерации неповторяющийся последовательности (иррациональности), количество входящих переменных должно становиться постепенно больше и больше. Иначе результат булевой функции, рано или поздно, пробежит по всему множеству значений и зациклится.
Увеличивающийся набор переменных можно выразить в виде рекурсии, либо как постепенное до-выделение памяти по ходу работы.
> И еще:
> А что является достаточным доказательством ирациональности?
> Невозможность выразить в виде дроби m/n, где m и n - целые?
> А кАк ето доказать?! Невырождение цифровой
> последовательности в циклически-повторяющуюся? А как Ето
> доказать?! Вот, доказать вырождение в цикл на основе
> алгоритма вычисления, это можно... Так, уже теплее!
В общем случае (насколько я знаю) это не просто, нет никакого "универсального" способа.
Один из вариантов - доказать, что искомое число раскладывается в бесконечный ряд, а потом доказать что в пределе образующий число интеграл не сходится в рациональной точке.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
