информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медСетевые кракеры и правда о деле ЛевинаСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Phrack #70/0x46 
 Возможно, Facebook наступил на... 
 50 лет электронной почте 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





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

Нет, и быть не может.

Неповторяющаяся последовательность - это аналог иррационального числа записанного в дискретной системе счисления.

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

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

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

Увеличивающийся набор переменных можно выразить в виде рекурсии, либо как постепенное до-выделение памяти по ходу работы.

> И еще:
> А что является достаточным доказательством ирациональности?
> Невозможность выразить в виде дроби m/n, где m и n - целые?
> А кАк ето доказать?! Невырождение цифровой
> последовательности в циклически-повторяющуюся? А как Ето
> доказать?! Вот, доказать вырождение в цикл на основе
> алгоритма вычисления, это можно... Так, уже теплее!

В общем случае (насколько я знаю) это не просто, нет никакого "универсального" способа.
Один из вариантов - доказать, что искомое число раскладывается в бесконечный ряд, а потом доказать что в пределе образующий число интеграл не сходится в рациональной точке.
<theory> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach