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

ทฤษฎีบทเวียนบังเกิดของคลีน (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.
ทฤษฎีการคำนวณ