'เกมแห่งชีวิต' ของคณิตศาสตร์เผยให้เห็นรูปแบบการทำซ้ำที่ตามหามานาน | นิตยสารควอนต้า

ในปี 1969 นักคณิตศาสตร์ชาวอังกฤษ จอห์น คอนเวย์ ได้คิดค้นกฎเกณฑ์ง่ายๆ ที่น่าหลงใหลสำหรับการสร้างพฤติกรรมที่ซับซ้อน เกมแห่งชีวิตของเขา ซึ่งมักเรียกง่ายๆ ว่าชีวิต แผ่ออกไปบนตารางเซลล์สี่เหลี่ยมอันไม่มีที่สิ้นสุด แต่ละเซลล์สามารถเป็นได้ทั้ง "มีชีวิต" หรือ "ตาย" ตารางจะวิวัฒนาการไปตามผลัดกัน (หรือ "รุ่น") โดยชะตากรรมของแต่ละเซลล์จะกำหนดโดยแปดเซลล์ที่อยู่รอบ ๆ กฎมีดังนี้:

1. เกิด: ห้องขังที่มีเพื่อนบ้านที่ยังมีชีวิตอยู่สามคนกลับมีชีวิตขึ้นมา
2. การเอาชีวิตรอด: ห้องขังที่มีชีวิตเพื่อนบ้านสองหรือสามคนยังมีชีวิตอยู่
3. ความตาย: เซลล์ที่มีชีวิตซึ่งมีเพื่อนบ้านที่มีชีวิตน้อยกว่าสองหรือมากกว่าสามคนตาย

กฎง่ายๆ เหล่านี้สร้างอาร์เรย์ของรูปแบบหรือ "รูปแบบชีวิต" ที่หลากหลายอย่างน่าอัศจรรย์ ซึ่งวิวัฒนาการมาจากการกำหนดค่าเริ่มต้นที่แตกต่างกันมากมายของกริด ผู้ชื่นชอบเกมได้นับและจัดหมวดหมู่รูปแบบเหล่านี้ให้เพิ่มมากขึ้นเรื่อยๆ แคตตาล็อกออนไลน์. คอนเวย์ค้นพบรูปแบบที่เรียกว่าไฟกระพริบ ซึ่งแกว่งไปมาระหว่างสองรัฐ

ปีต่อมา เขาพบรูปแบบที่ซับซ้อนกว่ามากที่เรียกว่าพัลซาร์ ซึ่งแกว่งไปมาระหว่างสามรัฐที่แตกต่างกัน

ไม่นานหลังจากค้นพบออสซิลเลเตอร์ นักสำรวจยุคแรกเริ่มสงสัยว่ามีออสซิลเลเตอร์ในทุกยุคสมัยหรือไม่ “ในตอนแรก เราเห็นเฉพาะช่วง 1, 2, 3, 4 และ 15 เท่านั้น” บิล กอสเปอร์ โปรแกรมเมอร์คอมพิวเตอร์และนักคณิตศาสตร์ กล่าว ซึ่งจะค้นพบออสซิลเลเตอร์แบบใหม่ที่แตกต่างกัน 17 ตัวในช่วงหลายทศวรรษต่อจากนี้ ออสซิลเลเตอร์ช่วง 15 (แสดงด้านล่าง) ปรากฏขึ้นบ่อยครั้งอย่างน่าประหลาดใจในการสุ่มค้นหา

ความประหลาดใจซ่อนตัวอยู่สำหรับผู้ที่เต็มใจที่จะพบพวกเขา “จากการรับชมหลายชั่วโมงและหลายวัน ช่วงเวลาที่ 5 ดูเหมือนจะเป็นไปไม่ได้” กอสเปอร์กล่าว จากนั้นในปี 1971 สองปีหลังจากการประดิษฐ์เกมนี้ ก็มีผู้ค้นพบเกมหนึ่ง การตามล่าหาออสซิลเลเตอร์ใหม่ๆ กลายเป็นจุดสนใจหลักของเกม ภารกิจที่ได้รับการสนับสนุนจากการกำเนิดของเทคโนโลยีคอมพิวเตอร์ เรื่องราวของการค้นหาอย่างลับๆ ที่ดำเนินการบนคอมพิวเตอร์ในสำนักงานได้กลายเป็นรากฐานสำคัญของนิทานพื้นบ้านของเกม “เวลาคอมพิวเตอร์ที่ถูกขโมยไปจากเมนเฟรมขององค์กรและมหาวิทยาลัยนั้นมีจำนวนมหาศาล” Gosper กล่าว

ตลอดช่วงทศวรรษ 1970 นักคณิตศาสตร์และนักเล่นงานอดิเรกเติมเต็มช่วงเวลาสั้นอื่นๆ และพบว่ามีช่วงที่ยาวกว่านั้นอีกเล็กน้อย ในที่สุดนักคณิตศาสตร์ก็ค้นพบวิธีที่เป็นระบบในการสร้างออสซิลเลเตอร์คาบยาว แต่ออสซิลเลเตอร์ที่มีช่วงเวลาระหว่าง 15 ถึง 43 นั้นหาได้ยาก “ผู้คนพยายามหาทางตรงกลางมาหลายปีแล้ว” กล่าว ไมอา คาร์โปวิชนักศึกษาระดับบัณฑิตศึกษาจากมหาวิทยาลัยแมรีแลนด์ การเติมเต็มช่องว่างทำให้นักวิจัยต้องฝันถึงเทคนิคใหม่ๆ มากมายที่ขยายขอบเขตของสิ่งที่คิดว่าเป็นไปได้ด้วยออโตมาตาเซลลูลาร์ ตามที่นักคณิตศาสตร์เรียกว่ากริดที่กำลังพัฒนาเช่นชีวิต

ตอนนี้ Karpovich และผู้เขียนร่วมหกคนได้ประกาศใน พิมพ์ล่วงหน้าเดือนธันวาคม ว่าพวกเขาได้พบช่วงที่ขาดหายไปสองช่วงสุดท้าย: 19 และ 41 เมื่อช่องว่างเหล่านั้นถูกเติมเต็ม บัดนี้ชีวิตจึงเป็นที่รู้กันว่าเป็น "ทุกช่วง" - ตั้งชื่อจำนวนเต็มบวก และก็มีรูปแบบที่ซ้ำรอยเดิมหลังจากหลายขั้นตอนนั้น

ชุมชนที่กำลังขยายตัวซึ่งอุทิศให้กับการศึกษาเรื่อง Life ซึ่งรวมถึงนักคณิตศาสตร์เพื่อการวิจัยจำนวนมาก แต่ยังรวมถึงผู้ที่เป็นงานอดิเรกอีกด้วย ไม่เพียงแต่ค้นพบออสซิลเลเตอร์เท่านั้น แต่ยังมีรูปแบบใหม่ทุกประเภทอีกด้วย พวกเขาได้พบรูปแบบที่เดินทางข้ามตาราง ยานอวกาศที่ถูกขนานนาม และรูปแบบที่สร้างรูปแบบอื่นๆ เช่น ปืน ตัวสร้าง และผู้เพาะพันธุ์ พวกเขาพบรูปแบบที่คำนวณจำนวนเฉพาะ และแม้แต่รูปแบบที่สามารถใช้อัลกอริทึมที่ซับซ้อนได้ตามอำเภอใจ

ออสซิลเลเตอร์ที่มีระยะเวลาสั้นกว่า 15 สามารถพบได้ด้วยตนเองหรือด้วยอัลกอริธึมพื้นฐานที่ค้นหาออสซิลเลเตอร์ทีละเซลล์ แต่เมื่อเวลาผ่านไป ความซับซ้อนก็เพิ่มขึ้น ทำให้การค้นหาแบบเดรัจฉานมีประสิทธิภาพน้อยลงมาก “ในช่วงเวลาเล็กๆ คุณสามารถค้นหาได้โดยตรง” Matthias Merzenich ผู้ร่วมเขียนรายงานฉบับใหม่ที่ค้นพบออสซิลเลเตอร์งวด 31 ตัวแรกในปี 2010 กล่าว “แต่คุณไม่สามารถไปไกลกว่านั้นได้จริงๆ คุณไม่สามารถเลือกช่วงเวลาและค้นหาได้” (Merzenich ได้รับปริญญาเอกสาขาคณิตศาสตร์จาก Oregon State University ในปี 2021 แต่ปัจจุบันทำงานในฟาร์ม)

ในปี 1996 David Buckingham ที่ปรึกษาคอมพิวเตอร์อิสระชาวแคนาดาและผู้ที่ชื่นชอบชีวิตซึ่งค้นหารูปแบบมาตั้งแต่ช่วงปลายทศวรรษ 1970 แสดงให้เห็นว่ามีความเป็นไปได้ที่จะสร้างออสซิลเลเตอร์ในช่วง 61 และสูงกว่าโดยการส่งรูปแบบไปรอบ ๆ แทร็กปิดในวงวนไม่สิ้นสุด . ด้วยการควบคุมความยาวของวง และเวลาที่ต้องใช้รูปแบบในการเดินทางไปกลับหนึ่งรอบ บัคกิงแฮมพบว่าเขาสามารถทำให้ช่วงเวลานั้นใหญ่ขึ้นได้ตามที่เขาชอบ “มันเป็นเคมีที่ไม่มีกลิ่นตลกๆ หรือเครื่องแก้วแตก” เขากล่าว “เหมือนกับการสร้างสารประกอบแล้วสำรวจปฏิสัมพันธ์ระหว่างพวกมัน” นั่นหมายความว่าในคราวเดียว เขาได้คิดวิธีสร้างออสซิลเลเตอร์ที่มีระยะเวลานานตามอำเภอใจ ตราบใดที่พวกมันมีความยาวมากกว่า 61 ปี

มีผลสำเร็จมากมายในช่วงกลางทศวรรษ 1990 เมื่อออสซิลเลเตอร์ที่หายไปจำนวนมากระหว่าง 15 ถึง 61 ปีถูกค้นพบผ่านการผสมผสานอย่างสร้างสรรค์ของออสซิลเลเตอร์ที่รู้จัก ซึ่งได้รับการตั้งชื่อหลากสีสัน ผู้จัดเลี้ยงรวมกับสัญญาณไฟจราจร ภูเขาไฟพ่นประกายไฟ และผู้กินกินเครื่องร่อน

เมื่อถึงช่วงเปลี่ยนศตวรรษที่ 21 มีเพียงช่วงเวลาเดียวเท่านั้นที่ยังคงโดดเด่น “ดูเหมือนเป็นไปได้มากที่จะแก้ปัญหานี้” เมอร์เซนิชกล่าว ในปี 2013 การค้นพบใหม่ที่เรียกว่า Snark loop ได้รับการปรับปรุงโดยใช้เทคนิคของ Buckingham ในปี 1996 และลดจุดตัดลงซึ่งง่ายต่อการสร้างออสซิลเลเตอร์จาก 61 เป็น 43 เหลือเพียงห้าช่วงเวลาที่หายไป มีการค้นพบอีก 2019 รายการในปี 2022 และอีก 19 รายการในปี 41 เหลือเพียง XNUMX และ XNUMX เท่านั้น ซึ่งเป็นจำนวนเฉพาะทั้งคู่ “ไพรม์นั้นยากกว่าเพราะคุณไม่สามารถใช้ออสซิลเลเตอร์คาบสั้นเพื่อสร้างพวกมันได้” Merzenich กล่าว

Mitchell Riley นักวิจัยหลังปริญญาเอกที่ New York University Abu Dhabi และผู้ร่วมเขียนรายงานฉบับใหม่นี้ รู้สึกทึ่งมานานแล้วกับออสซิลเลเตอร์ประเภทหนึ่งที่เรียกว่ายุ่งยาก “วิธีการทำงานของผู้ก่อกวนคือ คุณมีรูปแบบที่กระตือรือร้นอยู่ตรงกลาง และมีบางสิ่งที่มั่นคงด้านนอกซึ่งทำปฏิกิริยากับมัน” ไรลีย์อธิบาย สิ่งที่เสถียรซึ่งเรียกว่าตัวเร่งปฏิกิริยา จะอยู่ตรงนั้นเพื่อดันรูปแบบที่ใช้งานอยู่ให้กลับสู่สถานะดั้งเดิม

การออกแบบมันเป็นเรื่องยาก “รูปแบบทั้งหมดเหล่านี้เปราะบางอย่างไม่น่าเชื่อ” Riley กล่าว “ถ้าคุณวางจุดใดจุดหนึ่งผิด ปกติพวกมันจะระเบิด”

Riley สร้างโปรแกรมชื่อ Barrister เพื่อค้นหาตัวเร่งปฏิกิริยาใหม่ “สิ่งที่เรากำลังมองหาคือหุ่นนิ่งที่แข็งแกร่ง ประเด็นทั้งหมดคือเราต้องการให้พวกเขาโต้ตอบกับสิ่งที่เกิดขึ้นตรงกลางแล้วจึงฟื้นตัว” ไรลีย์กล่าว

Riley ป้อนตัวเร่งปฏิกิริยาที่ Barrister พบในโปรแกรมค้นหาอื่นที่จับคู่กับรูปแบบที่ใช้งานอยู่ สิ่งนี้นำไปสู่ความล้มเหลวเป็นส่วนใหญ่ เขากล่าว “ค่อนข้างหายากที่ตัวเร่งปฏิกิริยาตัวใดตัวหนึ่งจะรอดจากการโต้ตอบได้ ไม่มีการรับประกันความสำเร็จ คุณแค่ไขว้นิ้วและหวังว่าคุณจะถูกแจ็คพอต มันให้ความรู้สึกเหมือนการพนัน”

ในที่สุดการเดิมพันของเขาก็หมดลง หลังจากพลาดไปไม่กี่ครั้ง — และการปรับเปลี่ยนโค้ดที่ขยายการค้นหาให้รวมรูปแบบสมมาตร — เขาพบปฏิสัมพันธ์ของตัวเร่งปฏิกิริยาที่สามารถรักษาออสซิลเลเตอร์คาบ 19 ได้ “ผู้คนพยายามทำการค้นหาที่ซับซ้อนจริงๆ ทุกรูปแบบโดยใช้ตัวเร่งปฏิกิริยาจำนวนมากและมีสิ่งที่ออกฤทธิ์หายากอยู่ตรงกลาง แต่สิ่งที่จำเป็นก็คือการค้นหาตัวเร่งปฏิกิริยาก้อนใหม่นี้” ไรลีย์กล่าว

ช่วงเวลาที่หายไปครั้งสุดท้ายคือ 41 ถูกค้นพบโดยนิโคโล บราวน์ ผู้ร่วมเขียนอีกคนหนึ่ง ซึ่งยังคงเป็นนักศึกษาเอกคณิตศาสตร์ระดับปริญญาตรีที่มหาวิทยาลัยแคลิฟอร์เนีย ซานตาครูซ บราวน์ใช้เครื่องร่อนเป็นตัวเร่ง ซึ่งเป็นแนวคิดที่เมอร์เซนิชเสนอเป็นครั้งแรก

“เราค้นพบพฤติกรรมที่ลึกซึ้งมากมายในช่วง 10 ปีที่ผ่านมา” คาร์โปวิชกล่าว “ทุกคนเฉลิมฉลองกันเป็นเวลาหนึ่งสัปดาห์ จากนั้นก็ย้ายไปทำอย่างอื่นต่อไป มีปัญหาอื่นอีกมากมายที่ต้องแก้ไข” ออสซิลเลเตอร์ในช่วงเวลาที่กำหนดสามารถทำให้เล็กลงได้หรือไม่? ออสซิลเลเตอร์สามารถพบได้โดยที่ทุกเซลล์มีการแกว่งไปมาหรือไม่? ปืนสามารถสร้างในช่วงเวลาใดเวลาหนึ่งได้หรือไม่? ยานอวกาศสามารถเดินทางด้วยความเร็วเฉพาะได้หรือไม่?

ดังที่บัคกิงแฮมกล่าวไว้ “มันเหมือนกับการเป็นเด็กในร้านขายของเล่นที่ไม่มีที่สิ้นสุด”