Prima parte a acestui răspuns este pentru un versiunea anterioară a întrebării, cu $x_0$ un rațional reprezentat printr-un șir de biți arbitrar de mare.
Există funcții $f$ astfel încât niciun algoritm nu poate prezice următorul bit al secvenței de ieșire.
Un exemplu simplu este $f(x)=\begin{cases}2x&\text{dacă }x<1/2\2x-1&\text{otherwise}\end{cases}$.
Cu această funcție, secvența binară produsă este reprezentarea binară a ¹ $x_0$ (începând cu primul bit după virgulă zecimală), care nu poate fi prezis. Este asta $f$ "o hartă haotică"? Nu pot spune.
Putem face $f$ continuu, de ex. $f(x)=\begin{cases}2x&\text{dacă }x<1/2\2-2x&\text{otherwise}\end{cases}$.
Relația dintre o reprezentare binară a $x_0$ iar secvența rămâne astfel încât schimbarea $i^\text{th}$ un pic din acea reprezentare binară a $x_0$ schimbă $i^\text{th}$ fragment din secvență. Cred că am văzut această funcție, sau un văr apropiat, numit „o hartă haotică".
Putem face $f$ nedefinit derivat cu $f(x)=\frac{43}{11}\,x\,(1-x)$ (un caz de "harta logistică cu parametru rațional", și "o hartă haotică" după majoritatea conturilor). Fără dovadă: pentru orice șir de biți în $\{0,1\}^{n+1}$ există o $x_0$ astfel încât primul $n+1$ biți de ieșire sunt acel șir de biți, astfel că următorul bit nu este previzibil cu siguranță.
Acum pentru întrebare revizuită cu
pentru orice $n$, chiar și când $n >|x_0|$ Unde $|x_0|$ este lungimea șirului de biți care reprezintă $x_0$.
Fără dovadă: cu $f(x)=\frac{43}{11}\,x\,(1-x)$ si majoritatea $x_0$, generatorul de întrebare necesită lucru exponențial în numărul de biți produși (argument: $f^n(x)$ este un polinom de grad $2^n$, astfel încât se pare că evaluarea lui la o acuratețe de date necesită cunoaștere $x$ cu un număr exponenţial de biţi). Astfel, generatorul de întrebare nu îndeplinește criteriile standard de a fi un algoritm de timp polinom și, prin urmare, nu îndeplinește definiția standard a unui PRG, indiferent de predictibilitate. Cel puțin, costul și necesarul de memorie cresc atât de repede încât nu este util în practică.
Pe de altă parte, pentru majoritatea fixă $x_0$ (poate, toți cei care nu fac secvența de biți generată în cele din urmă periodic), este posibil să se facă un predictor parțial. În special, secvența de ieșire este considerabil îndreptată spre $1$. Astfel, un deosebitor este mult mai ușor decât calcularea secvenței. Cred că remediile simple, cum ar fi schimbarea pragului $1/2$ la media așteptată, încă va permite un deosebitor polinomial-timp pur și simplu prin calculul frecvenței secvențelor unui număr de biți.
¹ Pentru numere cu două reprezentări binare, adică de forma $a/2^k$, luați mai întâi lexicografic: de ex. $3/4$ este $.1011111111111111111â¦$
