Первая часть этого ответа предназначена для предыдущая версия вопроса, с $x_0$ рациональное представление, представленное произвольно большой битовой строкой.
Существуют функции $f$ так что никакие алгоритмы не могут предсказать следующий бит выходной последовательности.
Простой пример $f(x)=\begin{cases}2x&\text{если}x<1/2\2x-1&\text{иначе}\end{cases}$.
С помощью этой функции двоичная последовательность получается ¹ двоичным представлением $x_0$ (начиная с первого бита после запятой), что невозможно предсказать. В том, что $f$ "хаотичная карта"? Я не могу сказать.
Мы можем сделать $f$ непрерывный, напр. $f(x)=\begin{cases}2x&\text{если}x<1/2\2-2x&\text{иначе}\end{cases}$.
Связь между бинарным представлением $x_0$ и последовательность остается такой, что изменение $ я ^ \ текст {й} $ бит этого двоичного представления $x_0$ изменяет $ я ^ \ текст {й} $ бит последовательности. Кажется, я видел эту функцию или ее близкого родственника, получившего название "хаотичная карта".
Мы можем сделать $f$ бесконечно выводимый с $f(x)=\frac{43}{11}\,x\,(1-x)$ (случай "логистическая карта с рациональным параметром", и "хаотичная карта" по большинству оценок). Без доказательства: для любой битовой строки в $\{0,1\}^{n+1}$ существует $x_0$ такой, что первый $n+1$ выходные биты являются этой битовой строкой, поэтому следующий бит нельзя предсказать с уверенностью.
Теперь для пересмотренный вопрос с
для любой $n$, даже когда $n >|x_0|$ куда $|x_0|$ длина битовой строки, представляющей $x_0$.
Без доказательства: с $f(x)=\frac{43}{11}\,x\,(1-x)$ и большинство $x_0$, генератор вопроса требует работы, экспоненциальной по количеству произведенных битов (аргумент: $f^n(x)$ является полиномом степени $2^n$, таким образом кажется, что оценка его с заданной точностью требует знания $х$ с экспоненциальным числом битов). Таким образом, генератор вопроса не соответствует стандартным критериям алгоритма с полиномиальным временем и, следовательно, не соответствует стандартному определению PRG, независимо от предсказуемости. По крайней мере, стоимость и требования к памяти растут настолько быстро, что на практике это бесполезно.
С другой стороны, для большинства фиксированных $x_0$ (возможно, все те, которые не делают сгенерированную битовую последовательность в конечном счете периодической), можно сделать частичный предиктор. В частности, выходная последовательность значительно смещена в сторону $1$. Таким образом, различитель намного проще, чем вычисление последовательности. Я думаю, что простые исправления, такие как изменение порога $1/2$ к ожидаемому среднему по-прежнему позволит различать полиномиальное время, просто вычисляя частоту последовательностей ряда битов.
¹ Для чисел с двумя двоичными представлениями, то есть в форме $а/2^к$, сначала возьмите лексикографически: например. $3/4$ является $.1011111111111111111…$
