ส่วนแรกของคำตอบนี้มีไว้สำหรับ รุ่นก่อนหน้าของคำถาม, กับ $x_0$ เหตุผลแทนด้วยบิตสตริงขนาดใหญ่โดยพลการ
มีฟังก์ชั่นอยู่ $f$ เพื่อไม่ให้อัลกอริทึมสามารถทำนายบิตถัดไปของลำดับผลลัพธ์ได้
ตัวอย่างง่ายๆคือ $f(x)=\begin{cases}2x&\text{if }x<1/2\2x-1&\text{มิฉะนั้น}\end{cases}$.
ด้วยฟังก์ชันนี้ ลำดับเลขฐานสองที่สร้างขึ้นจะเป็นตัวแทนเลขฐานสองของ $x_0$ (เริ่มที่บิตแรกหลังจุดทศนิยม) ซึ่งไม่สามารถคาดเดาได้ คือว่า $f$ "แผนที่วุ่นวาย"?ผมบอกไม่ได้
เราสามารถทำให้ $f$ ต่อเนื่อง เช่น $f(x)=\begin{cases}2x&\text{if }x<1/2\2-2x&\text{มิฉะนั้น}\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â¦$