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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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

ส่วนเครื่องจักร $A$ คือเครื่องจักรที่ได้จากการคำนวณ $q(\langle BT \rangle)$ เมื่อ $\langle BT \rangle$ คือคำบรรยายเครื่องจักรที่ใ้ช้ $B$ ทำงานก่อนตามด้วย $T$

สังเกตว่าเครื่องจักร $R$ ตามที่ได้นิยามข้างต้นเป็นเครื่องจักรทัวริงที่สอดคล้องกับทฤษฎีบท กล่าวคือ $A = P_{\langle BT \rangle}$ เป็นเครื่องจักรที่พิมพ์คำบรรยายของ $B T$ ดังนั้นเมื่อนำคำบรรยายนี้ไปผนวกกับ $q(\langle BT \rangle) = A$ ก็จะใช้เครื่องจักร $A B T$ ซึ่งก็คือตัว $R$ นั่นเอง ฉะนั้นผลลัพธ์ของ $B$ คือ $( \langle R \rangle, x)$ และ $T$ ก็จะคำนวณ $t(\langle R \rangle, x)$ ตามที่เราต้องการ

[แก้] ประโยชน์

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

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

 $M$  = "เมื่อได้รับอินพุต  $x$ 
    1. หาค่า  โดยใช้ทฤษฎีบทเวียนบังเกิดของคลีน
    2. ให้  $H$  ทำงานบนข้อมูลเข้า 
    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.

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%97/%E0%B8%A4/%E0%B8%A9/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%9A%E0%B8%97%E0%B9%80%E0%B8%A7%E0%B8%B5%E0%B8%A2%E0%B8%99%E0%B8%9A%E0%B8%B1%E0%B8%87%E0%B9%80%E0%B8%81%E0%B8%B4%E0%B8%94%E0%B8%82%E0%B8%AD%E0%B8%87%E0%B8%84%E0%B8%A5%E0%B8%B5%E0%B8%99.html".

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

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

จากวิกิพีเดีย สารานุกรมเสรี

[แก้] การพิสูจน์

[แก้] ประโยชน์

[แก้] อ้างอิง

Views

ป้ายบอกทาง

ค้นหา

ภาษาอื่น