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

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

ให้  เป็นฟังก์ชันคำนวณได้ใด ๆ แล้ว จะมีเครื่องจักรทัวริง  ที่เมื่อรับ  เป็นข้อมูลเข้า แล้วจะคำนวณ  เมื่อ  คือคำบรรยายของ  เอง

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

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

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

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

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

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

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

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

ส่วนเครื่องจักร  คือเครื่องจักรที่ได้จากการคำนวณ  เมื่อ  คือคำบรรยายเครื่องจักรที่ใช้  ทำงานก่อนตามด้วย 

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

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

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

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

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

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

 อ้างอิง 

 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.

หมวดหมู่:ทฤษฎีการคำนวณ