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

ทฤษฎีบทเวียนบังเกิดของคลีน  ในทฤษฎีการคำนวณได้ เป็นทฤษฎีบทเกี่ยวกับการมีอยู่ของฟังก์ชันคำนวณได้ที่ใช้คำบรรยายตัวเองในการคำนวณผลลัพธ์ สตีเฟน คลีน เป็นผู้พิสูจน์ทฤษฎีบทนี้ในปี ค.ศ. 1938 โดยมีเนื้อหาดังต่อไปนี้
ให้ <math>t: \Sigma^* \times \Sigma^* \rightarrow \Sigma^*</math> เป็นฟังก์ชันคำนวณได้ใด ๆ แล้ว จะมีเครื่องจักรทัวริง <math>R\,</math> ที่เมื่อรับ <math>w\,</math> เป็นข้อมูลเข้า แล้วจะคำนวณ <math>t(\langle R \rangle, w)</math> เมื่อ <math>\langle R \rangle</math> คือคำบรรยายของ <math>R\,</math> เอง
กล่าวคือ สำหรับฟังก์ชันคำนวณได้ที่มีข้อมูลเข้าสองตัวใด ๆ จะมีฟังก์ชันคำนวณได้อีกฟังก์ชันหนึ่งที่ใช้ตัวเองเป็นข้อมูลเข้าตัวแรกโดยไม่ต้องอ่านข้อมูลจากภายนอก ตัวอย่างเช่น ถ้า <math>t(x,y) = x</math> เครื่องจักรทัวริง <math>R</math> ให้คำบรรยายตัวเองออกมาเป็นผลลัพธ์ โปรแกรมคอมพิวเตอร์ที่ทำงานเหมือนกับ <math>R</math> จะพิมพ์ซอร์สโค้ดของตัวเองออกมา เราเรียกโปรแกรมประเภทนี้ว่าไควน์
การพิสูจน์.
เราเริ่มต้นโดยการพิสูจน์บทตั้งต่อไปนี้
มีฟังก็ชันคำนวณได้ <math>q: \Sigma^* \times \Sigma^* \rightarrow \Sigma^*</math> ที่ สำหรับสายอักษร <math>w \,</math> ใด ๆ <math>q(w) \,</math> เป็นคำบรรยายเครื่องจักรทัวริง <math>P_w \,</math> ที่รับข้อมูลเข้า <math>x \,</math> และพิมพ์ผลลัพธ์ <math>(w,x) \,</math>
โดยแสดงเครื่องจักรทัวริงที่คำนวณ <math>q</math> เครื่องจักรทัวริงนั้นอาจนิยามได้ดังต่อไปนี้
 <math>Q</math> = "เมื่อได้รับข้อมูลเข้า <math>w</math>
 1. สร้างเครื่องจักรทัวริง <math>P_w</math> ดังต่อไปนี้
 <math>P_w</math> = "เมื่อได้รับข้อมูลเข้า <math>x</math>
 1. เลื่อน <math>x</math> ให้มีช่องว่างจากต้นเทปพอที่จะเขียน <math>w</math> และเครื่องหมาย "เว้นวรรค"
 2. พิมพ์ <math>w</math> ลงบนเทป
 3. หยุดการทำงาน"
 2. พิมพ์ <math>\langle P_w \rangle</math>"
สำหรับการสร้างเครื่องจักรทัวริง <math>R</math> ในทฤษฎีบทนั้น เราแบ่ง <math>R</math> ออกเป็นเครื่องจักรทัวริงย่อย ๆ สามเครื่อง ได้แก่ <math>A</math>, <math>B</math>, และ <math>T</math> โดยที่ <math>T</math> เป็นเครื่องจักรทัวริงหนึ่งที่คำนวณ <math>t</math> โดยเครื่องจักรทั้งสามเครื่องมีลำดับการทำงานคือ <math>A</math> ทำงานจนเสร็จสิ้นแล้ว <math>B</math> จึงเริ่มทำงาน และเมื่อ <math>B</math> ทำงานเสร็จสิ้นแล้ว <math>T</math> จึงเริ่มทำงาน
เครื่องจักร <math>B</math> มีนิยามดังต่อไปนี้
 <math>B</math> = "เมื่อได้รับข้อมูลเข้า <math>(\langle M \rangle,x)</math> เมื่อ <math>\langle M \rangle</math> เป็นคำอธิบายเครื่องจักรทัวริง <math>M</math>
 1. คำนวณ <math>q(\langle M \rangle)</math> โดยใช้บทตั้งข้างต้น
 2. ต่อเติมคำอธิบายเครื่องจักร <math>M</math> ให้เป็นเครื่องจักร <math>N</math> ที่ใช้ <math>q(\langle M \rangle)</math> ทำงานก่อน
 แล้วจึงใช้ <math>M</math> ทำงานตาม
 3. พิมพ์ <math>(N,x)</math> ลงบนเทป"
ส่วนเครื่องจักร <math>A</math> คือเครื่องจักรที่ได้จากการคำนวณ <math>q(\langle BT \rangle)</math> เมื่อ <math>\langle BT \rangle</math> คือคำบรรยายเครื่องจักรที่ใช้ <math>B</math> ทำงานก่อนตามด้วย <math>T</math>
สังเกตว่าเครื่องจักร <math>R</math> ตามที่ได้นิยามข้างต้นเป็นเครื่องจักรทัวริงที่สอดคล้องกับทฤษฎีบท กล่าวคือ <math>A = P_{\langle BT \rangle}</math> เป็นเครื่องจักรที่พิมพ์คำบรรยายของ <math>BT</math> ดังนั้นเมื่อนำคำบรรยายนี้ไปผนวกกับ <math>q(\langle BT \rangle) = A</math> ก็จะใช้เครื่องจักร <math>ABT</math> ซึ่งก็คือตัว <math>R</math> นั่นเอง ฉะนั้นผลลัพธ์ของ <math>B</math> คือ <math>(\langle R \rangle, x)</math> และ <math>T</math> ก็จะคำนวณ <math>t(\langle R \rangle, x)</math> ตามที่เราต้องการ
ประโยชน์.
เราสามารถใช้ทฤษฎีบทเวียนบังเกิดของคลีนในการพิสูจน์ข้อความทางทฤษฎีการคำนวณได้หลาย ๆ ข้อความอย่างกระชับและเป็นธรรมชาติ ยกตัวอย่างเช่น ปัญหาการหยุดทำงาน ซึ่งสามารถพิสูจน์ได้ดังต่อไปนี้ 
สมมติเพื่อข้อขัดแย้งว่ามีเครื่องจักรทัวริง <math>H</math> ที่แก้ปัญหาการหยุดทำงาน พิจารณาเครื่องจักร <math>M</math> ดังต่อไปนี้
 <math>M</math> = "เมื่อได้รับอินพุต <math>x</math>
 1. หาค่า <math>\langle M \rangle</math> โดยใช้ทฤษฎีบทเวียนบังเกิดของคลีน
 2. ให้ <math>H</math> ทำงานบนข้อมูลเข้า <math>(\langle M \rangle, x)</math>
 3. ถ้า <math>H</math> บอกว่า "หยุดทำงาน" ให้เข้าลูปอนันต์
 ถ้า <math>H</math> บอกว่า "ไม่หยุดทำงาน" ให้หยุดทำงาน
เนื่องจาก <math>M</math> ทำงานตรงกันข้ามกับการวินิจฉัยของ <math>H</math> เราจึงได้ข้อขัดแย้งและสรุปได้ว่า <math>H</math> ไม่มีอยู่จริง
ข้อความอื่น ๆ ที่สามารถพิสูจน์ได้ด้วยทฤษฎีบทเวียนบังเกิดของคลีน เช่น