預測輸出序列中下一位的算法的存在
讓 $ X = [0, 1]\cap \mathbb{Q} $ ， 然後讓 $ f:X \rightarrow X $ 是一個混沌映射（即有理參數的邏輯映射）。我的問題如下，純粹是理論上的。選擇一些值 $ x_0 $ 從 $ X $ （注意 $ X $ 在這裡是無限的，所以使用選擇公理選擇一個值），然後考慮通過迭代生成的位序列 $ f $ 超過 $ x_0 $ ，返回一個 $ 0 $ 如果 $ f^n(x_0)\leq 1/2 $ 並返回一個 $ 1 $ 如果 $ f^n(x_0)>1/2 $ .
是否存在一種算法，當給定地圖的參數時 $ f $ 和一些位序列 $ s \in {0, 1}^n $ 迭代得到 $ f $ 超過 $ x_0 $ 並以指定的方式返回位，總共 $ n $ 次，它可以預測從 $ f^{n+1}(x_0) $ 以不可忽略的機率，對於任何 $ n $ ，即使當 $ n >|x_0| $ 在哪裡 $ |x_0| $ 是表示的位串的長度 $ x_0 $ ?
我問這個的原因是因為它似乎與詢問是否存在 PRG 不同（但我可能是錯的）。原因是我假設了“秘密”初始條件 $ x_0 $ 不是從有限集中隨機選擇的，而是從無限集中選擇的 $ X $ （雖然 $ X $ 是可數的，因此每個元素都可以用有限位串表示）。因此，我想知道這個關於如何繪製初始條件的假設是否會改變事情。
該答案的第一部分是針對該問題的早期版本，其中 $ x_0 $ 由任意大的位串表示的有理數。
存在函式 $ f $ 這樣沒有算法可以預測輸出序列的下一位。
一個簡單的例子是 $ f(x)=\begin{cases}2x&\text{if }x<1/2\2x-1&\text{otherwise}\end{cases} $ .
使用這個函式，產生的二進制序列是¹二進製表示 $ x_0 $ （從小數點後的第一位開始），這是無法預測的。就是它 $ f $ 《混沌地圖》？我說不出來。
我們可以做 $ f $ 連續的，例如 $ f(x)=\begin{cases}2x&\text{if }x<1/2\2-2x&\text{otherwise}\end{cases} $ .
二進製表示之間的關係 $ x_0 $ 並且該序列仍然使得改變 $ i^\text{th} $ 二進製表示的位 $ x_0 $ 改變 $ i^\text{th} $ 序列的位。我想我見過這個功能，或者是近親，被稱為“混沌地圖”。
我們可以做 $ 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 $ ，因此似乎評估它以達到給定的準確性需要知道 $ x $ 具有指數位數的比特）。因此，問題的生成器不符合多項式時間算法的標準標準，因此不符合 PRG 的標准定義，無論可預測性如何。至少，成本和記憶體需求增長得如此之快，以至於在實踐中沒有用處。
另一方面，對於大多數固定 $ x_0 $ （也許，所有那些不使最終生成的位序列成為周期性的），都可以製作部分預測器。特別是，輸出序列相當大地偏向 $ 1 $ . 因此，區分器比計算序列要容易得多。我認為簡單的修復就像改變門檻值 $ 1/2 $ 到預期的平均值仍然將允許多項式時間區分器，只需計算多個位的序列頻率。
¹ 對於具有兩種二進製表示形式的數字，其形式為 $ a/2^k $ ，首先按字典順序：例如 $ 3/4 $ 是 $ .1011111111111111111… $