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

**ทฤษฎีบทเวียนบังเกิดของคลีน** () ในทฤษฎีการคำนวณได้ เป็นทฤษฎีบทเกี่ยวกับการมีอยู่ของฟังก์ชันคำนวณได้ที่ใช้คำบรรยายตัวเองในการคำนวณผลลัพธ์ สตีเฟน คลีน เป็นผู้พิสูจน์ทฤษฎีบทนี้ในปี ค.ศ. 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.

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