ทฤษฎีบทเวียนบังเกิดของคลีน

จากวิกิพีเดีย สารานุกรมเสรี

ทฤษฎีบทเวียนบังเกิดของคลีน (อังกฤษ: Kleene's recursion theorem) ในทฤษฎีการคำนวณได้ เป็นทฤษฎีบทเกี่ยวกับการมีอยู่ของฟังก์ชันคำนวณได้ที่ใช้คำบรรยายตัวเองในการคำนวณผลลัพธ์ สตีเฟน คลีน เป็นผู้พิสูจน์ทฤษฎีบทนี้ในปี ค.ศ. 1938 โดยมีเนื้อหาดังต่อไปนี้

ให้ t: \Sigma^* \times \Sigma^* \rightarrow \Sigma^* เป็นฟังก์ชันคำนวณได้ใดๆ แล้ว จะมีเครื่องจักรทัวริง R\, ที่เมื่อรับ w\, เป็นข้อมูลเข้า แล้วจะคำนวณ t(\langle R \rangle, w) เมื่อ \langle R \rangle คือคำบรรยายของ R\, เอง

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

การพิสูจน์[แก้]

เราเริ่มต้นโดยการพิสูจน์บทตั้งต่อไปนี้

มีฟังก็ชันคำนวณได้ q: \Sigma^* \times \Sigma^* \rightarrow \Sigma^* ที่ สำหรับสายอักษร w \, ใดๆ q(w) \, เป็นคำบรรยายเครื่องจักรทัวริง P_w \, ที่รับข้อมูลเข้า x \, และพิมพ์ผลลัพธ์ (w,x) \,

โดยแสดงเครื่องจักรทัวริงที่คำนวณ q เครื่องจักรทัวริงนั้นอาจนิยามได้ดังต่อไปนี้

Q = "เมื่อได้รับข้อมูลเข้า w
    1. สร้างเครื่องจักรทัวริง P_w ดังต่อไปนี้
       P_w = "เมื่อได้รับข้อมูลเข้า x
            1. เลื่อน x ให้มีช่องว่างจากต้นเทปพอที่จะเขียน w และเครื่องหมาย "เว้นวรรค"
            2. พิมพ์ w ลงบนเทป
            3. หยุดการทำงาน"
    2. พิมพ์ \langle P_w \rangle"

สำหรับการสร้างเครื่องจักรทัวริง R ในทฤษฎีบทนั้น เราแบ่ง R ออกเป็นเครื่องจักรทัวริงย่อยๆ สามเครื่อง ได้แก่ A, B, และ T โดยที่ T เป็นเครื่องจักรทัวริงหนึ่งที่คำนวณ t โดยเครื่องจักรทั้งสามเครื่องมีลำดับการทำงานคือ A ทำงานจนเสร็จสิ้นแล้ว B จึงเริ่มทำงาน และเมื่อ B ทำงานเสร็จสิ้นแล้ว T จึงเริ่มทำงาน

เครื่องจักร B มีนิยามดังต่อไปนี้

B = "เมื่อได้รับข้อมูลเข้า (\langle M \rangle,x) เมื่อ \langle M \rangle เป็นคำอธิบายเครื่องจักรทัวริง M
    1. คำนวณ q(\langle M \rangle) โดยใช้บทตั้งข้างต้น
    2. ต่อเติมคำอธิบายเครื่องจักร M ให้เป็นเครื่องจักร N ที่ใช้ q(\langle M \rangle) ทำงานก่อน
       แล้วจึงใช้ M ทำงานตาม
    3. พิมพ์ (N,x) ลงบนเทป"

ส่วนเครื่องจักร A คือเครื่องจักรที่ได้จากการคำนวณ q(\langle BT \rangle) เมื่อ \langle BT \rangle คือคำบรรยายเครื่องจักรที่ใช้ B ทำงานก่อนตามด้วย T

สังเกตว่าเครื่องจักร R ตามที่ได้นิยามข้างต้นเป็นเครื่องจักรทัวริงที่สอดคล้องกับทฤษฎีบท กล่าวคือ A = P_{\langle BT \rangle} เป็นเครื่องจักรที่พิมพ์คำบรรยายของ BT ดังนั้นเมื่อนำคำบรรยายนี้ไปผนวกกับ q(\langle BT \rangle) = A ก็จะใช้เครื่องจักร ABT ซึ่งก็คือตัว R นั่นเอง ฉะนั้นผลลัพธ์ของ B คือ ( \langle R \rangle, x) และ T ก็จะคำนวณ t(\langle R \rangle, x) ตามที่เราต้องการ

ประโยชน์[แก้]

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

สมมติเพื่อข้อขัดแย้งว่ามีเครื่องจักรทัวริง H ที่แก้ปัญหาการหยุดทำงาน พิจารณาเครื่องจักร M ดังต่อไปนี้

M = "เมื่อได้รับอินพุต x
    1. หาค่า \langle M \rangle โดยใช้ทฤษฎีบทเวียนบังเกิดของคลีน
    2. ให้ H ทำงานบนข้อมูลเข้า (\langle M \rangle, x)
    3. ถ้า H บอกว่า "หยุดทำงาน" ให้เข้าลูปอนันต์
       ถ้า H บอกว่า "ไม่หยุดทำงาน" ให้หยุดทำงาน

เนื่องจาก M ทำงานตรงกันข้ามกับการวินิจฉัยของ H เราจึงได้ข้อขัดแย้งและสรุปได้ว่า H ไม่มีอยู่จริง

ข้อความอื่นๆ ที่สามารถพิสูจน์ได้ด้วยทฤษฎีบทเวียนบังเกิดของคลีน เช่น

  • ฟังก์ชันบีเวอร์คนขยันไม่ใช่ฟังก์ชันคำนวณได้
  • ไม่มีเครื่องจักรทัวริงใดทีสามารถ่คำนวณเครื่องจักรทัวริงที่มีขนาดของคำบรรยายสั้นที่สุดที่ำสมมูลกับเครื่องจักรทัวริงที่ให้เป็นข้อมูลเข้าได้
  • สำหรับฟังก์ชันคำนวณได้ t: \Sigma^* \rightarrow \Sigma^* ใดๆ ที่ทำการ "ดัดแปลง" เครื่องจักรทัวริงที่ได้รับเป็นข้อมูลเข้า จะมีเครื่องจักรทัวริง F ที่ t(\langle F \rangle) สมมูลกับ F

อ้างอิง[แก้]

  • Kleene, Stephen, "On notation for ordinal numbers," The Journal of Symbolic Logic, 3 (1938), 150-155.
  • Sipser, Michael. Introduction to the Theory of Computation. Boston: PWS, 1997.