Loops และ recursion เติมพลังให้กับอัลกอริทึม: loops ช่วยให้อัลกอริทึมประมวลผลอินพุตที่มีขนาดและความซับซ้อนได้ตามต้องการ หากไม่มี loops อัลกอริทึมจะรับมือได้เพียงกรณีเล็ก ๆ และเรียบง่ายเท่านั้น Loop ช่วยให้อัลกอริทึมเริ่มทำงานได้ เหมือนที่ปีกช่วยให้เครื่องบินบินได้—ถ้าไม่มีปีก เครื่องบินอาจยังเคลื่อนที่ได้ แต่ไม่สามารถใช้ศักยภาพในการขนส่งได้เต็มที่ ในทางเดียวกัน การคำนวณบางอย่างอาจอธิบายได้โดยอัลกอริทึมที่ไม่ใช้ loops แต่พลังการคำนวณอย่างเต็มรูปแบบจะเกิดขึ้นได้ก็ต่อเมื่อมี loops อย่างไรก็ตามพลังนี้ต้องถูกควบคุม ดังที่เรื่อง Groundhog Day แสดงให้เห็น โครงสร้างการควบคุมที่เราไม่อาจควบคุมไม่ได้เป็นพรแต่เป็นคำสาป บทกวีของ Goethe เรื่อง “The Sorcerer’s Apprentice” อาจผุดขึ้นในใจ (อาจรู้จักกันดีในสหรัฐฯ ผ่านฉากของ Mickey Mouse ในภาพยนตร์ Fantasia) กุญแจในการควบคุม loop คือการเข้าใจเงื่อนไขที่ตัดสินว่า loop จะสิ้นสุดเมื่อใด Phil Connors สุดท้ายจึงสามารถยุติ loop ที่เขาอยู่และได้ตอนจบที่มีความสุข แต่เหตุการณ์นี้เกิดขึ้นด้วยความบังเอิญมากกว่าจะเป็นตามแผน

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

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

Out of Control (ควบคุมไม่ได้)

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

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

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

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

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

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

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

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

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

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

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

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

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

Are We There Yet? (ถึงยัง?)

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

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

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

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

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

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

No End in Sight (ไม่มีวี่แววจะสิ้นสุด)

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

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

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

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

เพื่อเข้าใจว่าทำไมมันเป็นไปไม่ได้จริง ๆ ที่จะกำหนด Halts ให้เราสร้างอัลกอริทึมหนึ่งชื่อ Loop ขึ้นมาก่อน ซึ่งพฤติกรรมการยุติของมันชัดเจน (ดู figure 11.2) Loop รับตัวเลขเป็นพารามิเตอร์และกำหนดค่าตัวเลขนั้นให้กับตัวแปร x การเรียกใช้ Loop กับเลข 1—เขียนเป็น Loop(1)—ให้การคำนวณที่กำหนดค่า 1 ให้ตัวแปร x แล้วหยุด เพราะเงื่อนไขการยุติของ repeat loop เป็นจริง (ภาพกลางในรูป) ในทางกลับกัน สำหรับเลขอื่น ๆ มันจะวนกลับมาที่การกำหนดค่าให้ x ตัวอย่างเช่น 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 จะเป็นไปตามที่แสดงใน figure 11.3

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

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

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

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

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

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

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

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

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

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

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

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

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