creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
ทำไม่เสร็จหรือทำยังไม่เสร็จ?

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

ก่อนอื่นลองพิจารณาโค้ดนี้

float sin(float x)
{
   float res=0, num=x, den=1;
   int i=0;
   while(i<5)
   {
      res+=num/den;
      num*=x*x*(-1);
      den*=(2*(i+1))*(2*(i+1)+1);
      i++;
   }
   return res;
}


หลุดจาก while มั้ย? เราก็ดูว่า i<5 มีโอกาสเป็น false มั้ย ซึ่ง i++ ทิ่มตา ตอบได้เลยว่าหลุด โค้ดนี้จะ return ค่า res ซึ่งเท่ากับ sin(x) ที่ประมาณด้วยอนุกรมแม็คเคลารีนมาให้ โดยโปรแกรมจะวนลูป 5 ครั้ง (ผลรวมถึงพจน์ x11 ของอนุกรม) แต่ถ้าผมเกิดซน รู้ดีเชียวล่ะว่าอนุกรมกำลังเป็นอนุกรมอนันต์ ฉะนั้นแทนที่จะ while(i<5) ก็แก้เป็น while(true) หรือ while(1) คุณคิดว่าเกิดอะไรขึ้นครับ? หากมีใครสักคน call ฟังก์ชั่น sin โค้ดอันนี้ก็จะรันนิรันดร์ runs forever!

คราวนี้มองโค้ดของผมเป็น black box ที่ยอมให้คุณป้อน input คือ x (ในหน่วยเรเดียน และแน่นอนว่ามีค่าน้อย ๆ ใกล้ 0 ไม่ควรเกิน +/- 3 เพราะคุณรู้ว่าอนุกรมแม็คเคลารีนคืออนุกรมเทย์เลอร์ที่แทน a หรือจุดศูนย์กลางการกระจายเท่ากับ 0) แล้วมันจะให้ output คือ res ถ้าโค้ดของผมเป็นแบบ while(i<5) พอคุณป้อน x กล่องมันก็จะปล่อย res ออกมาในอึดใจหนึ่ง แต่ถ้าโค้ดนี้มีใครไปแก้เป็น while(i<50) อึดใจหนึ่งมันไม่ทันที่กล่องจะปล่อย res ถูกมั้ยครับ คุณอาจจะต้องรอถึงสิบอึดใจ เอาใหม่ เกิดมีใครไปแก้เป็น while(i<10000) คุณอาจต้องนั่นดื่มชารอ แบบโหดร้ายที่สุดคือ while(true) ตามทฤษฎีคุณต้องรอชั่วกัปชั่วกัลป์ อย่าลืมนะครับว่าตอนนี้มันเป็น black box คุณไม่รู้ว่า while(i<5), while(i<50), while(i<10000) หรือ while(true) คำถามที่เกิดขึ้นคือ ระหว่างที่คุณกำลังรออยู่นี่นะครับ คุณรู้ได้ยังไงว่ามันแค่เพียงยังทำงานไม่เสร็จไม่ใช่มันทำงานแบบไม่มีวันสำเร็จ! คุณสรุปไม่ได้ เพราะบางทีคุณอาจยังรอไม่นานพอ

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

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


และมีโปรแกรม H ที่สามารถบอกได้ว่าโปรแกรม P เมื่อรับ I แล้วจะทำสำเร็จ (ให้ค่า P(I)) หรือไม่สำเร็จ (รันนิรันดร์) ซึ่งเอ้าพุตของโปรแกรม H หรือ H(P,I) จะเท่ากับ true ถ้าโปรแกรม P ทำงานได้สำเร็จ และเท่ากับ false ถ้าโปรแกรม P รันนิรันดร์


ทีนี้ P เองแม้มันจะเป็นโปรแกรม ก็ไม่มีใครห้ามว่ามันเป็น input ของตัวมันเองไม่ได้ ขณะเดียวกันเราก็สร้าง K ซึ่งรับ H(P,P) เป็นอินพุต โดยที่ถ้า H(P,P) เป็น false เอ้าพุตของ K หรือ K(H) ก็จะเป็น true แต่ถ้า H(P,P) เป็น true เราจะเขียนโค้ดให้ K รันอนันดร์

boolean K(boolean H)
{
   if(H==false)
   {
      return true;
   } else {
      while(true);
   }
}





มอง HK รวมกันเป็นหนึ่งกล่องได้ใช่มั้ยครับ และในเมื่อ HK เองก็เป็นโปรแกรมไม่ต่างอะไรไปจาก P ลองเอา HK ป้อนเข้าไปแทน P ซิ เราจะพบว่า ถ้า H บอกว่า HK ทำสำเร็จ HK ก็จะติดลูป while(true) หรือทำไม่สำเร็จ แต่ถ้า H บอกว่า HK ติดลูป หรือทำไม่สำเร็จ HK ก็จะทำสำเร็จและให้ค่า K(H) = true เกิดข้อขัดแย้ง กลวิธีนี้บอกเราว่า ไม่มี H ที่จะทำงานได้ทุกกรณี ไม่มีโปรแกรมที่จะบอกได้ว่าโปรแกรมใดทำงานสำเร็จหรือไม่สำเร็จได้ทุกกรณี เราสามารถสร้าง input มาป้อนให้โปรแกรมนั้น fail ได้เสมอ


Create Date : 05 มีนาคม 2553
Last Update : 9 พฤษภาคม 2553 0:44:19 น. 0 comments
Counter : 1058 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.