ลูปและการเรียกซ้ำมอบพลังให้กับอัลกอริทึม ลูปช่วยให้อัลกอริทึมสามารถประมวลผลอินพุตที่มีขนาดและความซับซ้อนเท่าใดก็ได้ หากไม่มีลูป อัลกอริทึมจะจัดการได้เฉพาะกรณีอินพุตขนาดเล็กและง่ายเท่านั้น ลูปทำให้อัลกอริทึมก้าวขึ้นจากพื้นดินได้ พวกมันเปรียบเสมือนปีกของเครื่องบิน หากไม่มีปีก เครื่องบินยังคงเคลื่อนที่ได้ แต่ศักยภาพในการขนส่งอย่างเต็มที่นั้นไม่อาจบรรลุผลได้ ในทำนองเดียวกัน มีการคำนวณบางอย่างที่อัลกอริทึมสามารถอธิบายได้โดยไม่ต้องใช้ลูป แต่พลังเต็มที่ของการคำนวณจะเกิดขึ้นได้ก็ต่อเมื่อมีลูปเท่านั้น อย่างไรก็ตาม พลังดังกล่าวก็จำเป็นต้องถูกควบคุมเช่นกัน ดังที่เรื่องราวของ Groundhog Day แสดงให้เห็นอย่างชัดเจน โครงสร้างควบคุมที่เราไม่สามารถควบคุมได้นั้นไม่ใช่พร แต่เป็นคำสาป บทกวีของเกอเธ่เรื่อง "The Sorcerer's Apprentice" ก็อาจนึกถึงขึ้นมาเช่นกัน (ซึ่งอาจเป็นที่รู้จักดีกว่าในสหรัฐอเมริกาผ่านลำดับมิกกี้เมาส์ในภาพยนตร์ Fantasia ) กุญแจสำคัญในการควบคุมลูปคือการทำความเข้าใจเงื่อนไขที่ตัดสินว่ามันจะสิ้นสุดเมื่อใด ฟิล คอนเนอร์สสามารถยุติลูปที่เขาติดอยู่ในที่สุด นำไปสู่ตอนจบที่มีความสุข แต่สิ่งนี้เกิดขึ้นโดยบังเอิญมากกว่าการเป็นไปตามแผน

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

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

Out of Control (เกินการควบคุม)

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

แล้วถ้าไม่มีพรุ่งนี้ล่ะ? วันนี้ก็ไม่มีวันพรุ่งนี้อยู่แล้ว .
[วางสาย]

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

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

สถานการณ์ที่คล้ายคลึงกันนี้มีอยู่ในลูปของอัลกอริทึม บางสิ่งคงที่ตลอดการวนซ้ำที่แตกต่างกัน ในขณะที่บางสิ่งเปลี่ยนแปลงไป ตัวอย่างเช่น ในลูปเพื่อค้นหาองค์ประกอบในลิสต์ (ดู บทที่ 5 ) ลิสต์ขององค์ประกอบไม่เปลี่ยนแปลง และองค์ประกอบที่เรากำลังค้นหาก็ไม่เปลี่ยนแปลงเช่นกัน แต่ตำแหน่งปัจจุบันในลิสต์และด้วยเหตุนี้องค์ประกอบที่กำลังถูกตรวจสอบจึงเปลี่ยนแปลงในทุกการวนซ้ำจนกว่าจะพบองค์ประกอบหรือถึงจุดสิ้นสุดของลิสต์

เมื่อพิจารณาอย่างละเอียดจะพบว่า body ของลูปและเงื่อนไขการสิ้นสุดสามารถเข้าถึงสถานะของโลก ซึ่งเรียกสั้น ๆ ว่า state (สถานะ) ดังที่อธิบายไว้ใน บทที่ 10 การเข้าถึงนี้เกิดขึ้นผ่าน ตัวแปร (variables) คำแนะนำใน body ของลูปสามารถทั้งอ่านค่าและเปลี่ยนค่าของตัวแปรได้ ในทางตรงกันข้าม เงื่อนไขการสิ้นสุดสามารถอ่านค่าตัวแปรได้เท่านั้นเพื่อสร้างค่าจริงหรือเท็จเพื่อจบหรือดำเนินการลูปต่อไปตามลำดับ

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

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

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

เป็นที่ชัดเจนว่าการปรับเปลี่ยน state มีความสำคัญอย่างยิ่งต่ออัลกอริทึมการค้นหา เพราะหากไม่เปิดหน้า คุณจะไม่สามารถพบรูปภาพนั้นได้ (เว้นแต่มันจะอยู่ที่หน้าแรก)

ข้อเท็จจริงนี้ชัดเจนสำหรับฟิล คอนเนอร์ส และเขาจึงพยายามเปลี่ยนแปลงสิ่งต่าง ๆ รอบพันซ์ซูทอนีย์เพื่อให้เงื่อนไขการสิ้นสุดของลูป Groundhog Day เป็นจริง เพื่อที่เขาจะได้ออกจากลูปได้ แต่ไม่เพียงแต่ state ของลูป Groundhog Day จะใหญ่กว่ามาก—มันรวมถึงทุกคน (และพันซ์ซูทอนีย์ ฟิล) ความคิดและทัศนคติของพวกเขา และอื่น ๆ—มันยังไม่ชัดเจนด้วยซ้ำว่า state ประกอบด้วยอะไรบ้าง ดังนั้นมันจึงค่อนข้างเป็นเรื่องบังเอิญที่ในที่สุดเขาสามารถหลุดออกจากลูปได้

Figure 11.1 การคลี่ลูปหมายถึงการสร้างลำดับของสำเนาของ body ของมัน ในการวนซ้ำแต่ละครั้งของลูป จะมีการสร้างสำเนาของ body ลูปแยกต่างหาก รูปแสดง state ที่ถูกปรับเปลี่ยนและวิธีการที่มันเปลี่ยนแปลง (ถ้ามี) หาก state ไม่เคยเปลี่ยนแปลงเพื่อให้เงื่อนไขการสิ้นสุดเป็นจริง ลำดับนั้นจะไม่มีที่สิ้นสุด

คุณอาจคัดค้านว่าการเปรียบเทียบลูป Groundhog Day กับการคำนวณนั้นไม่สมเหตุสมผลเพราะคอมพิวเตอร์ที่รันมันและกฎที่มันดำเนินการนั้นเป็นเรื่องสมมติล้วน ๆ—เป็นเครื่องจักรนรกขุมภพเชิงอภิปรัชญาเพื่อสร้างคนดี แม้ว่าเรื่องราวของ Groundhog Day จะเป็นเรื่องสมมติแน่นอน แต่การเปรียบเทียบด้วยลูปของมันก็เหมาะสม มันยังแสดงให้เห็นว่าการคำนวณสามารถเกิดขึ้นได้ภายใต้สถานการณ์ที่แตกต่างกันมาก ด้วยคอมพิวเตอร์ที่ทำงานภายใต้กฎที่หลากหลาย อันที่จริง การคำนวณมักถูกใช้เพื่อจำลองโลกและสถานการณ์สมมติ ตราบใดที่กฎสำหรับการคำนวณมีเหตุผลและสอดคล้องกัน ก็ไม่มีขีดจำกัดต่อสถานการณ์ทางการคำนวณที่จินตนาการของเราจะสร้างขึ้นได้

Are We There Yet? (ถึงหรือยัง?)

ดังที่กล่าวถึงใน บทที่ 1 คำอธิบายของอัลกอริทึมและการดำเนินการของมันเป็นสองสิ่งที่แตกต่างกันมาก ลูปและพฤติกรรมการสิ้นสุดของมันทำให้ประเด็นนี้ชัดเจนขึ้น เนื่องจากเราอาจสงสัยว่าคำอธิบายอันจำกัดของลูปสามารถนำไปสู่การคำนวณที่ยาวนานอย่างไม่มีที่สิ้นสุดได้อย่างไร ปรากฏการณ์นี้สามารถเข้าใจได้ดีที่สุดผ่านวิธีการติดตามการดำเนินการของลูปที่เรียกว่า การคลี่ลูป (loop unfolding) (ดู รูปที่ 11.1 ) ในตัวอย่างการค้นหารูปดอกไม้ในหนังสือ body ของลูปประกอบด้วยการกระทำในการเปิดหน้ากระดาษ การคลี่ body ของลูปหมายถึงการสร้างลำดับของคำสั่ง "เปิดหน้า"

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

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

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

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

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

No End in Sight (ไม่มีที่สิ้นสุดในสายตา)

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

เนื่องจากการสิ้นสุดเป็นคุณสมบัติที่สำคัญมากของอัลกอริทึม—มันแยกอัลกอริทึมที่แก้ปัญหาได้จริงออกจากอัลกอริทึมที่แก้ไม่ได้—มันคงจะดีถ้าเราทราบคุณสมบัติการสิ้นสุดสำหรับอัลกอริทึมใด ๆ ก็ตามที่เราอาจต้องการใช้ อย่างไรก็ตาม การวิเคราะห์การสิ้นสุดสำหรับอัลกอริทึมไม่ใช่เรื่องง่าย และอาจใช้เวลาพอสมควรในการดำเนินการ ดังนั้น เราจึงอยากจะทำงานนี้ให้เป็นอัตโนมัติ กล่าวคือ สร้างอัลกอริทึม ชื่อว่า Halts ที่ทำการวิเคราะห์การสิ้นสุดโดยอัตโนมัติ เนื่องจากเรามีอัลกอริทึมอื่น ๆ อีกมากมายสำหรับวิเคราะห์อัลกอริทึม (เช่น สำหรับการแยกวิเคราะห์ ดู บทที่ 8 ) นี่จึงดูไม่ใช่แนวคิดที่ประหลาดเกินไป

โชคไม่ดีที่มันเป็นไปไม่ได้ที่จะสร้างอัลกอริทึม Halts ไม่ใช่ว่ามันยากเกินไปในตอนนี้ หรือนักวิทยาการคอมพิวเตอร์ยังไม่ได้คิดเกี่ยวกับปัญหานี้นานและหนักแน่นพอ ไม่เลย เรารู้ว่ามันเป็นไปไม่ได้ โดยหลักการ ที่จะสร้างอัลกอริทึม Halts มันเป็นไปไม่ได้ตอนนี้ และจะไม่มีวันเป็นไปได้ ข้อเท็จจริงนี้มักถูกอ้างถึงว่าเป็น ความไม่สามารถแก้ได้ของปัญหา halting (unsolvability of the halting problem) ปัญหา halting (halting problem) เป็นปัญหาสำคัญในวิทยาการคอมพิวเตอร์ มันถูก conceived โดยอลัน ทัวริงในปี ค.ศ. 1936 เป็นตัวอย่างของปัญหาที่ไม่สามารถตัดสินได้ (undecidable problem)

แต่ทำไมเราจึงไม่สามารถสร้างอัลกอริทึม Halts ได้? เนื่องจากอัลกอริทึมใด ๆ ก็ตามที่จะถูกวิเคราะห์โดย Halts นั้นถูกกำหนดด้วยคำอธิบายอันจำกัด ดูเหมือนว่าเราจะต้องตรวจสอบเพียงคำสั่งจำนวนจำกัดและวิธีการที่มันส่งผลต่อ state ที่กำหนดเงื่อนไขการสิ้นสุด

เพื่อทำความเข้าใจว่าทำไมมันถึงเป็นไปไม่ได้ที่จะนิยาม Halts ก่อนอื่นให้เราสร้างอัลกอริทึม Loop ซึ่งพฤติกรรมการสิ้นสุดของมันชัดเจน (ดู รูปที่ 11.2 ) Loop รับตัวเลขเป็นพารามิเตอร์และกำหนดให้กับตัวแปร x การใช้ Loop กับเลข 1—เขียนเป็น Loop (1)—ให้ผลลัพธ์เป็นการคำนวณที่กำหนด 1 ให้กับตัวแปร x และหยุด เนื่องจากเงื่อนไขการสิ้นสุดของ repeat loop เป็นจริง (กราฟิกกลางในรูป) มิฉะนั้น สำหรับตัวเลขอื่นใด มันจะวนกลับไปที่การกำหนดพารามิเตอร์ให้กับ x ตัวอย่างเช่น การใช้ Loop กับเลข 2, Loop (2), ให้ผลลัพธ์เป็นการคำนวณที่กำหนด 2 ให้กับตัวแปร x และวนซ้ำตลอดไป เนื่องจากเงื่อนไขการสิ้นสุดของ repeat loop เป็นเท็จ (กราฟิกทางขวาในรูป)

Figure 11.2 อัลกอริทึม Loop จะหยุดเมื่อเรียกด้วยเลข 1 เป็นอาร์กิวเมนต์ แต่จะวนซ้ำตลอดไปเมื่อเรียกด้วยอาร์กิวเมนต์อื่น ซ้าย: นิยามของอัลกอริทึม Loop . กลาง: การใช้ Loop กับเลข 1. ขวา: การใช้ Loop กับเลข 2.

กลยุทธ์ในการแสดงว่า Halts ไม่สามารถมีอยู่ได้คือสมมติว่ามันมีอยู่จริง แล้วแสดงให้เห็นว่าสมมติฐานนี้นำไปสู่ข้อขัดแย้ง กลยุทธ์นี้เรียกว่า การพิสูจน์โดยข้อขัดแย้ง (proof by contradiction) และถูกใช้อย่างแพร่หลายในคณิตศาสตร์

แล้วอัลกอริทึม Halts จะมีหน้าตาอย่างไร? ดังที่แสดงโดยอัลกอริทึม Loop พฤติกรรมการสิ้นสุดโดยทั่วไปขึ้นอยู่กับอินพุตของอัลกอริทึม ซึ่งหมายความว่า Halts ควรมีสองพารามิเตอร์: พารามิเตอร์หนึ่ง ชื่อว่า Alg สำหรับอัลกอริทึมที่จะถูกตรวจสอบ และอีกพารามิเตอร์หนึ่ง ชื่อว่า Inp สำหรับอินพุตที่ควรใช้ทดสอบอัลกอริทึม ดังนั้น อัลกอริทึม Halts มีโครงสร้างดังที่แสดงใน รูปที่ 11.3 . 1

ประกอบกับอัลกอริทึม Halts เราสามารถนิยามอัลกอริทึมอีกตัวหนึ่ง Selfie ซึ่งนำไปสู่ข้อขัดแย้งในสมมติฐานที่ว่า Halts สามารถมีอยู่ได้ Selfie ใช้ Halts ในวิธีที่ค่อนข้างแปลกประหลาด: มันพยายามตรวจสอบว่าอัลกอริทึมหนึ่งจะสิ้นสุดหรือไม่เมื่อรันโดยได้รับคำอธิบายของตัวมันเองเป็นอินพุต ในกรณีนั้น มันจะเข้าสู่ลูปที่ไม่สิ้นสุด มิฉะนั้น มันจะหยุด นิยามของ Selfie แสดงใน รูปที่ 11.4 .

การให้อัลกอริทึมได้รับคำอธิบายของตัวมันเองเป็นอินพุตอาจดูแปลก แต่นี่ไม่ใช่แนวคิดที่ประหลาดอะไรนัก ตัวอย่างเช่น Loop ( Loop ) กล่าวคือ Loop ถูกใช้กับตัวมันเอง จะไม่สิ้นสุดเพราะ Loop สิ้นสุดเฉพาะสำหรับอินพุต 1 เท่านั้น จะเกิดอะไรขึ้นถ้าเราใช้ Halts กับตัวมันเอง? Halts ( Halts ) จะสิ้นสุดไหม? ใช่ เนื่องจาก Halts โดยสมมติฐานระบุว่าสำหรับอัลกอริทึมใด ๆ ว่ามันหยุดหรือไม่ มันต้องสิ้นสุดเพื่อที่จะทำสิ่งนี้ ดังนั้นมันควรจะสิ้นสุดโดยเฉพาะเมื่อถูกใช้กับตัวมันเอง

เหตุผลสำหรับนิยามของ Selfie จะชัดเจนเมื่อเราพิจารณาว่าเกิดอะไรขึ้นเมื่อเราดำเนินการอัลกอริทึม Selfie โดยให้ตัวเองเป็นอินพุต อันที่จริง สิ่งนี้นำไปสู่สถานการณ์ที่ขัดแย้งซึ่งทำให้เกิดข้อกังขาต่อความเป็นไปได้ของการมีอยู่ของ Halts เราสามารถมองเห็นภาพว่าเกิดอะไรขึ้นโดยการคลี่นิยามของ Selfie เมื่อถูกใช้กับตัวมันเอง เมื่อต้องการทำเช่นนั้น เราแทนที่ Selfie สำหรับพารามิเตอร์ Alg ในนิยามของมัน ดังที่แสดงในกราฟิกกลางของ รูปที่ 11.4 สิ่งนี้นำไปสู่ลูปที่สิ้นสุดเมื่อ Selfie ที่ใช้กับนิยามของตัวมันเอง ไม่ หยุด เพราะถ้า Halts ( Selfie,Selfie ) เป็นจริง อัลกอริทึมจะวนกลับไปทดสอบเงื่อนไขอีกครั้ง และมิฉะนั้นก็จะหยุด

Figure 11.3   ซ้าย: โครงสร้างของอัลกอริทึม Halts . มันรับสองพารามิเตอร์ อัลกอริทึม ( Alg ) และอินพุตของมัน ( Inp ) และทดสอบว่าอัลกอริทึมที่ใช้กับอินพุต Alg ( Inp ) สิ้นสุดหรือไม่ กลาง: การใช้ Halts กับอัลกอริทึม Loop และเลข 1 ซึ่งให้ผลลัพธ์เป็น "ใช่" ขวา: การใช้ Halts กับ Loop และเลข 2 ซึ่งให้ผลลัพธ์เป็น "ไม่"

Figure 11.4   ซ้าย: นิยามของอัลกอริทึม Selfie . มันรับอัลกอริทึม ( Alg ) เป็นพารามิเตอร์และทดสอบว่าอัลกอริทึมที่ใช้กับตัวมันเองสิ้นสุดหรือไม่ ในกรณีนั้น Selfie จะเข้าสู่ลูปที่ไม่สิ้นสุด มิฉะนั้น มันจะหยุด กลาง: การใช้ Selfie กับตัวมันเองนำไปสู่ข้อขัดแย้ง: ถ้า Selfie ที่ใช้กับตัวมันเองสิ้นสุด มันจะเข้าสู่ลูปที่ไม่สิ้นสุด กล่าวคือ มันไม่สิ้นสุด; ถ้ามันไม่สิ้นสุด มันจะหยุด กล่าวคือ มันสิ้นสุด ขวา: การขยายนิยามของ Halts ให้มุมมองที่แตกต่างออกไปเล็กน้อยของความขัดแย้งนี้

ผังงานที่ได้อธิบายถึงการคำนวณที่ดูเหมือนจะมีพฤติกรรมดังนี้ ถ้า Selfie ที่ใช้กับตัวมันเองหยุด มันจะรันตลอดไป ในขณะที่ถ้ามันไม่หยุด มันจะหยุด ความขัดแย้งอาจชัดเจนยิ่งขึ้นถ้าเราแทนที่การเรียก Halts ด้วยนิยามของมัน ดังที่แสดงในกราฟิกทางขวาของ รูปที่ 11.4 ดังนั้น Selfie ( Selfie ) สิ้นสุดหรือไม่?

สมมติว่ามันสิ้นสุด ในกรณีนั้น อัลกอริทึม Halts —ซึ่งเราสมมติว่าสามารถตรวจสอบได้อย่างถูกต้องว่าอัลกอริทึมหนึ่งสิ้นสุดด้วยอินพุตเฉพาะหรือไม่—จะบอกว่า Selfie ( Selfie ) สิ้นสุด แต่นั่นจะทำให้ Selfie ( Selfie ) เลือก "ใช่" ในกิ่งของเงื่อนไขและเข้าสู่ลูปที่ไม่สิ้นสุด นั่นหมายความว่า ถ้า Selfie ( Selfie ) สิ้นสุด มันก็ไม่สิ้นสุด ดังนั้นสมมติฐานนั้นผิดอย่างชัดเจน มาสมมติว่า Selfie ( Selfie ) ไม่สิ้นสุด ในกรณีนี้ Halts ให้ค่าเท็จ ทำให้ Selfie ( Selfie ) เลือก "ไม่" ในกิ่งของเงื่อนไขและหยุด นั่นหมายความว่าถ้า Selfie ( Selfie ) ไม่สิ้นสุด มันก็สิ้นสุด นี่ก็ผิดเช่นกัน

ดังนั้น ถ้า Selfie ( Selfie ) หยุด มันก็รันตลอดไป และถ้ามันไม่หยุด มันก็หยุด—เป็นข้อขัดแย้งในทั้งสองกรณี สิ่งนี้ไม่สามารถเป็นจริงได้ แล้วเกิดอะไรขึ้น? ยกเว้นโครงสร้างควบคุมมาตรฐาน (ลูปและเงื่อนไข) สิ่งเดียวที่เราใช้ในการสร้างอัลกอริทึม Selfie คือสมมติฐานที่ว่าอัลกอริทึม Halts สามารถตรวจสอบพฤติกรรมการสิ้นสุดของอัลกอริทึมได้อย่างถูกต้อง เนื่องจากสมมติฐานนี้นำไปสู่ข้อขัดแย้ง มันจึงต้องผิด กล่าวอีกนัยหนึ่ง อัลกอริทึม Halts ไม่สามารถมีอยู่ได้ เพราะการสมมติว่ามันมีอยู่นำไปสู่ข้อขัดแย้งทางตรรกะ

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

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

การไม่มีอยู่ของอัลกอริทึม Halts เป็นข้อมูลเชิงลึกที่น่าประหลาดใจแต่ก็ลึกซึ้ง มันบอกเราว่ามีปัญหาทางการคำนวณที่ ไม่สามารถ แก้ไขได้ด้วยอัลกอริทึม กล่าวอีกนัยหนึ่ง มีปัญหาทางการคำนวณที่คอมพิวเตอร์ไม่สามารถแก้ไขได้—ตลอดไป ปัญหาที่ไม่มีอัลกอริทึมสำหรับแก้ไขนั้นเรียกว่า ไม่สามารถคำนวณได้ (uncomputable) หรือ ไม่สามารถตัดสินได้ (undecidable) 3

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

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