Saturday, February 10, 2007
:: Halting Problem for Love ::
"โปรดอย่าถาม ว่าฉันจะรักเธอนานเท่าใด ฉันตอบไม่ได้ว่าฉันจะรักชั่วกาลนิรันดร์ ..." [เพลงจงรัก ของสุนทราภรณ์]

เพลงนี้หลายคนคงเคยได้ยิน

ผู้แต่งเพลงได้ให้เหตุผลไว้ว่า "เพราะชีวิตฉันคงไม่ยืนยาวไปถึงป่านนั้น"

แต่แท้จริงแล้วมีคำอธิบายในอีกแง่หนึ่ง ที่สามารถอธิบายเหตุผลว่าทำไม "ฉันตอบไม่ได้.." โดยไม่ต้องตั้งอยู่บนสมมติฐานที่ว่ามนุษย์มีอายุขัยจำกัด

ลองมองดูว่า "ความรัก" ก็เปรียบเสมือนกับโปรแกรม และตัวเรา (หรือใจเรา) ก็เป็นเสมือนผู้ดำเนินการตามโปรแกรมนั้น พูดในอีกแง่หนึ่ง เราเองก็เปรียบเสมือนกับ Turing Machine และความรักก็คือ โปรแกรม (transition rules) ของ Turing Machine ส่วนคนรักนั้นก็คือ input และความทรงจำในช่วงต่างๆ ของชีวิต ก็คือ infinite memory tape (บางคนอาจเถียงว่าความทรงจำของเรามีจำกัด แต่อย่าลืมว่าเราสามารถจดความทรงจำใส่ไดอะรี่ได้เสมอ)

ข้อสังเกตข้อหนึ่งคือ Turing Machine นี้ ไม่จำเป็นต้อง deterministic (โดยเฉพาะสำหรับผู้หญิง(บางคน) .. ฮาๆๆๆ)

เป็นที่รู้กันดีว่า halting problem สำหรับ Turing machine นั้นเป็นปัญหาที่ undecidable

นั่นหมายความว่าไม่มี algorithm ใดที่รับอินพุตเป็น Turing machine M และ string w แล้วจะสามารถตอบได้ (ภายในเวลาจำกัด) เสมอว่าเมื่อ M รันบน input w แล้ว M จะเสร็จสิ้นการทำงาน (terminate) หรือไม่

ฉันใดก็ฉันนั้น เมื่อความรักและตัวเราเป็นดั่ง Turing machine และคนรักเป็นดั่ง input จึงไม่มีใครสามารถตอบได้ว่าความรักจะจบลงหรือไม่ หรือจะจบลงเมื่อใด แม้ว่าเราจะมีชีวิตอยู่ชั่วกาลนิรันดร์ก็ตาม


หมายเหตุทางเทคนิค:
  • บทความนี้เขียนในแง่อุปมาอุปมัย ไม่ได้ตั้งใจให้เป็นบทพิสูจน์ที่ถูกต้องรัดกุม ซึ่งความจริงแล้วการจะพิสูจน์ว่า halting problem for love (HPL) is undecidable นั้น จะต้อง define love ให้ดีเสียก่อน (ซึ่งผมไม่ได้ define) และจะต้องพยายาม reduce ปัญหาจาก halting problem for Turing machine (HPTM) มาเป็น HPL ให้ได้ ... ซึ่งอาจจะดูงงๆ
  • แม้ว่า HPL จะ undecidable จริงๆ ก็ไม่ได้หมายความว่าปัญหานี้จะไม่มีทางได้รับคำตอบไปเสียทุกกรณี
    • ยกตัวอย่างเช่น เราอาจจะพบกับ Turing machine (TM) เครื่องหนึ่งซึ่งเมื่อได้รับอินพุตแบบบหนึ่ง จะกระโดดเข้าสู่ infinite loop อย่างเห็นได้ชัด ในกรณีนี้ แม้ HPTM จะ undedicable แต่เราก็สามารถตอบได้ว่า TM เครื่องนี้จะไม่ terminate บนอินพุตนี้
    • ฉันใดก็ฉันนั้น เราอาจจะได้พบใครคนหนึ่ง และค้นใจตัวเองจนพบว่า คนคนนี้ทำให้เรากระโดดเข้าสู่ infinite loop เราก็จะตอบได้ชัดเจนว่า เราจะรักคนคนนั้นตลอดไป
    • ...หรือคนบางคนอาจมีอะไรบางอย่างที่ทำให้เราต้องกระโดดเข้าสู่คำสั่ง exit(0); -- หรือบางทีก็ exit (-1); -- นั่นก็อีกเรื่องหนึ่ง :P
  • เนื่องจาก HPTM บน blank tape (TM with no input) ก็ undecidable เช่นเดียวกัน เราอาจจะขยายผลได้ว่า HPL with no lover ก็คงจะ undecidable เหมือนกัน ... หรือพูดอีกอย่างหนึ่ง: คนที่เป็นโสดอาจจะตอบไม่ได้ว่าตัวเองจะต้องเป็นโสดไปอีกตลอดไปหรือไม่
  • เวรกรรม! -__-
[link to last-year valentine's article]

This page is powered by Blogger. Isn't yours?