Phần đầu tiên của câu trả lời này là dành cho phiên bản trước của câu hỏi, với $x_0$ một hợp lý được đại diện bởi một chuỗi bit lớn tùy ý.
Có chức năng tồn tại $f$ sao cho không có thuật toán nào có thể dự đoán bit tiếp theo của chuỗi đầu ra.
Một ví dụ đơn giản là $f(x)=\begin{cases}2x&\text{if }x<1/2\2x-1&\text{otherwise}\end{cases}$.
Với chức năng này, chuỗi nhị phân được tạo ra là biểu diễn nhị phân¹ của $x_0$ (bắt đầu từ bit đầu tiên sau dấu thập phân), không thể dự đoán được. đó là $f$ "một bản đồ hỗn loạn"? Tôi không thể nói.
chúng ta có thể làm $f$ liên tục, v.d. $f(x)=\begin{cases}2x&\text{if }x<1/2\2-2x&\text{otherwise}\end{cases}$.
Mối quan hệ giữa biểu diễn nhị phân của $x_0$ và trình tự vẫn như vậy mà thay đổi $i^\text{th}$ bit của biểu diễn nhị phân đó của $x_0$ thay đổi $i^\text{th}$ một chút của trình tự. Tôi nghĩ rằng tôi đã thấy chức năng này, hoặc một người anh em họ gần gũi, được đặt tên là "một bản đồ hỗn loạn".
chúng ta có thể làm $f$ có thể dẫn xuất vô thời hạn với $f(x)=\frac{43}{11}\,x\,(1-x)$ (trường hợp "bản đồ logistic với tham số hợp lý", và "một bản đồ hỗn loạn" bởi hầu hết các tài khoản). Không có bằng chứng: đối với bất kỳ chuỗi bit nào trong $\{0,1\}^{n+1}$ tồn tại một $x_0$ như vậy mà đầu tiên $n+1$ bit đầu ra là chuỗi bit đó, do đó bit tiếp theo không thể dự đoán được một cách chắc chắn.
Bây giờ cho câu hỏi sửa đổi với
bất cứ gì $n$, ngay cả khi $n >|x_0|$ ở đâu $|x_0|$ là độ dài của chuỗi bit đại diện cho $x_0$.
Không có bằng chứng: với $f(x)=\frac{43}{11}\,x\,(1-x)$ và hầu hết $x_0$, trình tạo câu hỏi yêu cầu công việc theo cấp số nhân của số bit được tạo (đối số: $f^n(x)$ là một đa thức bậc $2^n$, do đó, có vẻ như việc đánh giá nó với độ chính xác nhất định đòi hỏi phải biết $x$ với số mũ của các bit). Do đó, trình tạo câu hỏi không đáp ứng các tiêu chí tiêu chuẩn là thuật toán Thời gian đa thức và do đó không đáp ứng định nghĩa tiêu chuẩn của PRG, bất kể khả năng dự đoán. Ít nhất, yêu cầu về chi phí và bộ nhớ tăng nhanh đến mức nó không hữu ích trong thực tế.
Mặt khác, đối với hầu hết cố định $x_0$ (có lẽ, tất cả những thứ không tạo ra chuỗi bit được tạo ra cuối cùng theo chu kỳ), có thể tạo một bộ dự đoán một phần. Đặc biệt, trình tự đầu ra khá thiên về $1$. Do đó, một bộ phân biệt dễ dàng hơn nhiều so với tính toán trình tự. Tôi nghĩ rằng các cách khắc phục đơn giản như thay đổi ngưỡng $1/2$ với giá trị trung bình dự kiến vẫn sẽ cho phép một bộ phân biệt thời gian đa thức chỉ đơn giản bằng cách tính toán tần số của các chuỗi của một số bit.
¹ Đối với các số có hai biểu diễn nhị phân, đó là dạng $a/2^k$, lấy từ vựng trước: ví dụ: $3/4$ Là $.1011111111111111111â¦$
