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