ปัญหาการบีบอัดข้อมูลในรูปแบบที่ง่ายที่สุดอาจเกี่ยวข้องกับตัวเลขและสัญลักษณ์ของมัน ตัวเลขสามารถแสดงด้วยตัวเลข ("สิบเอ็ด" สำหรับหมายเลข 11) นิพจน์ทางคณิตศาสตร์ ("สองในยี่สิบ" สำหรับ 1048576) นิพจน์สตริง ("ห้าเก้า" สำหรับ 99999) ชื่อเฉพาะ ("จำนวนสัตว์ร้าย" สำหรับ 666, "ปีแห่งการเสียชีวิตของทัวริง" สำหรับปี 1954) หรือการรวมกันโดยพลการของสิ่งเหล่านั้น การกำหนดใด ๆ ที่เหมาะสมซึ่งคู่สนทนาสามารถกำหนดหมายเลขที่เรากำลังพูดถึงได้อย่างชัดเจน แน่นอนบอกคู่สนทนาของคุณ "แฟกทอเรียลของแปด" มีประสิทธิภาพมากกว่าสัญกรณ์ที่เทียบเท่า “สี่หมื่นสามร้อยยี่สิบ”. คำถามเชิงตรรกะเกิดขึ้นที่นี่: สัญกรณ์ที่สั้นที่สุดสำหรับตัวเลขที่กำหนดคืออะไร?
นักปรัชญา เบอร์ทรานด์ รัสเซลล์ ตีพิมพ์ในปี 1908 ซึ่งกระทบถึงประเด็นสัญกรณ์ตัวเลขจากฝั่งตรงข้าม: จำนวนที่น้อยที่สุดที่ไม่ต้องใช้ตัวอักษรแปดสิบตัวคืออะไร?
ต้องมีตัวเลขดังกล่าว: จากตัวอักษรรัสเซียแปดสิบตัวและช่องว่างคุณสามารถสร้างได้เพียง 3480 ตำแหน่งซึ่งหมายความว่าเมื่อใช้ตัวอักษรแปดสิบตัวคุณสามารถกำหนดตัวเลขได้ไม่เกิน 3480 ตัว ซึ่งหมายความว่าเป็นไปไม่ได้ที่จะกำหนดหมายเลขหนึ่งให้ไม่เกิน 3480 ด้วยวิธีนี้
ซึ่งหมายความว่าหมายเลขนี้จะสอดคล้องกับการกำหนด “เลขน้อยที่สุดแปดสิบตัวก็ไม่พอ”ซึ่งมีเพียง 78 ตัวอักษรเท่านั้น! ในด้านหนึ่ง ตัวเลขนี้จะต้องมีอยู่ ในทางกลับกัน หากมีหมายเลขนี้อยู่ การกำหนดก็ไม่สอดคล้องกับหมายเลขนั้น พาราด็อกซ์!
วิธีที่ง่ายที่สุดในการขจัดความขัดแย้งนี้คือการอ้างอิงถึงความไม่เป็นทางการของสัญลักษณ์ทางวาจา เช่น หากอนุญาตให้ใช้เฉพาะชุดนิพจน์ที่กำหนดไว้โดยเฉพาะในสัญกรณ์แล้ว “เลขน้อยที่สุดแปดสิบตัวก็ไม่พอ” จะไม่ใช่สัญกรณ์ที่ถูกต้อง แต่สัญกรณ์ที่มีประโยชน์ในทางปฏิบัติเช่น "แฟกทอเรียลของแปด" ก็คงเป็นที่ยอมรับ
มีวิธีที่เป็นทางการในการอธิบายลำดับ (อัลกอริทึม) ของการกระทำกับตัวเลขหรือไม่? มีมากมายและเรียกว่าภาษาโปรแกรม แทนที่จะใช้คำพูด เราจะใช้โปรแกรม (เช่น ใน Python) ที่แสดงตัวเลขที่ต้องการ ตัวอย่างเช่นสำหรับห้าเก้าโปรแกรมก็เหมาะสม print("9"*5). เราจะสนใจโปรแกรมที่สั้นที่สุดตามจำนวนที่กำหนดต่อไป ความยาวของโปรแกรมดังกล่าวเรียกว่า ตัวเลข; มันเป็นขีดจำกัดทางทฤษฎีที่สามารถบีบอัดจำนวนที่กำหนดได้
แทนที่จะเป็นความขัดแย้งของ Berry ตอนนี้เราสามารถพิจารณาสิ่งที่คล้ายคลึงกัน: จำนวนที่น้อยที่สุดที่โปรแกรมกิโลไบต์ไม่เพียงพอที่จะส่งออกคืออะไร?
เราจะให้เหตุผลเหมือนเดิม: มีข้อความ 2561024 กิโลไบต์ซึ่งหมายความว่าโปรแกรมกิโลไบต์สามารถส่งออกตัวเลขได้ไม่เกิน 2561024 หมายเลข ซึ่งหมายความว่าไม่สามารถหาจำนวนที่แน่นอนไม่เกิน 2561024 ด้วยวิธีนี้ได้
แต่มาเขียนโปรแกรมใน Python ที่สร้างข้อความกิโลไบต์ที่เป็นไปได้ทั้งหมด รันข้อความเหล่านั้นเพื่อดำเนินการ และหากข้อความแสดงตัวเลขออกมา ให้เพิ่มตัวเลขนี้ลงในพจนานุกรมของข้อความที่เข้าถึงได้ หลังจากตรวจสอบความเป็นไปได้ทั้งหมด 2561024 รายการ ไม่ว่าจะใช้เวลานานเท่าใด โปรแกรมจะค้นหาตัวเลขที่น้อยที่สุดที่หายไปจากพจนานุกรมและพิมพ์ตัวเลขนั้นออกมา ดูเหมือนชัดเจนว่าโปรแกรมดังกล่าวจะพอดีกับโค้ดขนาดกิโลไบต์ - และจะส่งออกจำนวนที่โปรแกรมกิโลไบต์ไม่สามารถส่งออกได้!
ตอนนี้จับอะไรได้บ้าง? ไม่สามารถนำมาประกอบกับความไม่เป็นทางการของสัญกรณ์ได้อีกต่อไป!
หากคุณสับสนกับความจริงที่ว่าโปรแกรมของเราต้องการหน่วยความจำจำนวนมหาศาลในการทำงาน - พจนานุกรม (หรืออาร์เรย์บิต) ขององค์ประกอบ 2561024 - คุณสามารถทำสิ่งเดียวกันได้โดยไม่ต้องใช้มัน: สำหรับตัวเลข 2561024 แต่ละตัวในทางกลับกัน ให้ผ่านโปรแกรมที่เป็นไปได้ทั้งหมด 2561024 โปรแกรมจนกว่าจะไม่มีโปรแกรมที่เหมาะสม ไม่สำคัญว่าการค้นหาดังกล่าวจะใช้เวลานานมากเมื่อตรวจสอบน้อยกว่า (2561024)2 คู่จากหมายเลขและโปรแกรมก็จะสิ้นสุดและพบหมายเลขที่รักมาก
หรือมันจะไม่จบ? แน่นอนว่าในบรรดาโปรแกรมทั้งหมดที่จะลองก็จะมี while True: pass (และแอนะล็อกเชิงฟังก์ชัน) - และเรื่องนี้จะไม่ไปไกลกว่าการทดสอบโปรแกรมดังกล่าว!
ต่างจากความขัดแย้งของ Berry ตรงที่การจับได้อยู่ในความไม่เป็นทางการของสัญกรณ์ ในกรณีที่สอง เรามีการกำหนดรูปแบบที่ปกปิดไว้อย่างดี . ความจริงก็คือมันเป็นไปไม่ได้ที่จะระบุผลลัพธ์จากโปรแกรมในเวลาอันจำกัด โดยเฉพาะอย่างยิ่งความซับซ้อนของ Kolmogorov : ไม่มีอัลกอริธึมที่จะยอมให้สำหรับตัวเลขที่กำหนด ค้นหาความยาวของโปรแกรมที่สั้นที่สุดที่จะพิมพ์ตัวเลขนี้ ซึ่งหมายความว่าไม่มีทางแก้ไขปัญหาของ Berry ได้ - ต้องหาความยาวของการกำหนดวาจาที่สั้นที่สุดสำหรับตัวเลขที่กำหนด
ที่มา: will.com