creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
Smullyan อธิบาย incompleteness theorem ฉบับสำหรับชาวบ้าน

ตัวอย่างหนึ่งที่ปู่เรย์ใช้อธิบายให้ชาวบ้านทั่วไปให้พอได้อารมณ์ของ incompleteness theorem ทฤษฎีบทแรกของเกอเดล เป็นแบบนี้ครับ

สมมติมีเครื่องจักรหนึ่งซึ่งจะพิมพ์ข้อความที่สร้างจากสัญลักษณ์ P N R *

เราจะเรียกข้อความที่เครื่องจักรสามารถพิมพ์ออกมาได้ว่าเป็นข้อความที่สามารถพิมพ์ได้ และถือว่าเครื่องจักรถูกโปรแกรมให้พิมพ์ข้อความทั้งหมดที่มันสามารถพิมพ์ได้ไม่ช้าก็เร็ว

ประโยคหมายถึงข้อความในรูปแบบใดรูปแบบหนึ่งต่อไปนี้ เมื่อ X แทนข้อความใด ๆ

(1) P*X
(2) NP*X
(3) PR*X
(4) NPR*X

ประโยค P*X จะถูกตีความว่า "สามารถพิมพ์ X ได้" และประโยคนี้จะเป็นจริงก็ต่อเมื่อ X เป็นข้อความที่สามารถพิมพ์ได้, ประโยค NP*X จะถูกตีความว่า "ไม่สามารถพิมพ์ X ได้" และประโยคนี้จะเป็นจริงก็ต่อเมื่อ X เป็นข้อความที่ไม่สามารถพิมพ์ได้, ประโยค PR*X จะถูกตีความว่า "สามารถตีพิมพ์ XX ได้" และมันเป็นจริงก็ต่อเมื่อ XX เป็นข้อความที่สามารถพิมพ์ได้, สุดท้าย NPR*X เป็นจริงก็ต่อเมื่อ XX เป็นข้อความที่ไม่สามารถพิมพ์ได้

เรารู้ว่าเครื่องจักรเครื่องนี้แม่นยำมาก และทุกประโยคที่พิมพ์ออกมา เป็นจริง ตัวอย่างเช่น ถ้า PR*X เป็นข้อความที่สามารถพิมพ์ได้ ย่อมหมายความว่าข้อความนี้เป็นจริง และนั่นหมายความว่า ข้อความ XX จะต้องถูกพิมพ์ออกมาไม่ช้าก็เร็ว

ทีนี้ ถ้ากำหนดว่า X เป็นข้อความที่สามารถพิมพ์ได้ เราจะบอกได้มั้ยว่า P*X ก็เป็นข้อความที่สามารถพิมพ์ได้ด้วย

คำตอบคือ ไม่จำเป็นครับ การที่ X เป็นข้อความที่สามารถพิมพ์ได้ ทำให้ประโยค P*X เป็นจริง แต่ไม่ได้หมายความว่า P*X จะเป็นข้อความที่สามารถพิมพ์ได้ สิ่งที่ปู่เรย์บอกตอนเริ่มต้นนั้นมีแค่ว่า ประโยคที่พิมพ์ได้ทั้งหมดเป็นจริง แต่ไม่ได้บอกว่า ประโยคทั้งหมดที่เป็นจริง พิมพ์ได้ และในความเป็นจริงแล้ว มันมีประโยคที่เป็นจริงที่เครื่องจักรไม่สามารถพิมพ์ได้ ถ้าสนใจลองหาประโยคนั้นเองก่อน ก็อย่าเพิ่งอ่านย่อหน้าต่อไป

สำหรับข้อความ X ใด ๆ ประโยค NPR*X เป็นจริงก็ต่อเมื่อข้อความ XX ไม่สามารถพิมพ์ได้ ถ้าให้ X คือ NPR* ล่ะ ฉะนั้น NPR*NPR* เป็นจริงก็ต่อเมื่อ NPR*NPR* ไม่สามารถพิมพ์ได้ ทำให้เกิดความเป็นไปได้แบบใดแบบหนึ่งในสองแบบนี้ คือ ก. NPR*NPR* เป็นจริงและไม่สามารถพิมพ์ได้ หรือ ข. NPR*NPR* ไม่เป็นจริงแต่มันสามารถถูกพิมพ์ได้ (เผื่อใครกำลังงง A iff B เป็นจริง ได้ 2 กรณีคือ ก. A และ B เป็นจริงทั้งคู่ กับ ข. A และ B เป็นเท็จทั้งคู่) แต่เรารู้ว่ากรณี ข. เกิดขึ้นไม่ได้ เพราะเครื่องจักรไม่พิมพ์ข้อความที่ไม่จริง ฉะนั้น NPR*NPR* คือข้อความที่เป็นจริงที่เครื่องจักรไม่สามารถพิมพ์ได้

ยังมีอะไรบางอย่างที่น่าสนใจเกี่ยวกับเครื่องจักรนี้ นั่นคือ เป็นไปได้ที่เราจะสร้างประโยค X กับ Y ที่มีประโยคหนึ่งในสองประโยคเป็นจริงแต่ไม่สามารถพิมพ์ได้ แต่ไม่มีทางที่จะรู้ได้ว่าประโยคดังกล่าวคือประโยคไหน ไอเดียคือสร้าง X ที่บอกว่า P*Y และสร้าง Y ที่บอกว่า NP*X เพราะ ถ้า X จริง นั่นคือ Y จริง และไม่สามารถพิมพ์ X ได้ ฉะนั้น ถ้า X จริง X ก็จะเป็นประโยคที่เป็นจริงที่ไม่สามารถพิมพ์ได้ แต่ถ้า X เท็จ แปลว่า ไม่สามารถพิมพ์ Y ได้ และข้อความที่ว่า NP*X ก็เป็นจริง เพราะเครื่องจักรไม่สามารถพิมพ์ข้อความที่เป็นเท็จได้ ฉะนั้น ถ้า X เท็จ Y ก็จะเป็นประโยคที่เป็นจริงที่ไม่สามารถพิมพ์ได้ ตัวอย่างคู่ข้อความดังกล่าวคือ X เท่ากับ P*NPR*P*NPR* และ Y เท่ากับ NPR*P*NPR* เห็นว่า X บอก P*Y ส่วน Y บอกไม่สามารถพิมพ์ P*NPR* ที่ซ้ำกันสองที (ซึ่งก็คือ X) ได้


Create Date : 19 กรกฎาคม 2558
Last Update : 19 กรกฎาคม 2558 18:59:35 น. 1 comments
Counter : 586 Pageviews.

 
สวัสดีนะจ้ะ เราแวะมาเยี่ยมนะจ้ะ ^____^ สักคิ้ว 6 มิติ ลบรอยสักคิ้วด้วยเลเซอร์ ลบรอยสักคิ้ว Eyebrow Tattoo Removal เพ้นท์คิ้วลายเส้น เพ้นท์คิ้ว 3 มิติ
ให้ใจหายใจ สุขภาพ วิธีลดความอ้วน การดูแลสุขภาพ อาหารเพื่อสุขภาพ ออกกำลังกาย สุขภาพผู้หญิง สุขภาพผู้ชาย สุขภาพจิต โรคและการป้องกัน สมุนไพรไทย ผู้หญิง ศัลยกรรม ความสวยความงาม แม่ตั้งครรภ์ สุขภาพแม่ตั้งครรภ์ พัฒนาการตั้งครรภ์ 40 สัปดาห์ อาหารสำหรับแม่ตั้งครรภ์ โรคขณะตั้งครรภ์ การคลอด หลังคลอด การออกกำลังกาย ทารกแรกเกิด สุขภาพทารกแรกเกิด ผิวทารกแรกเกิด การพัฒนาการของเด็กแรกเกิด การดูแลทารกแรกเกิด โรคและวัคซีนสำหรับเด็กแรกเกิด เลี้ยงลูกด้วยนมแม่ อาหารสำหรับทารก เด็กโต สุขภาพเด็ก ผิวเด็ก การพัฒนาการเด็ก การดูแลเด็ก โรคและวัคซีนเด็ก อาหารสำหรับเด็ก การเล่นและการเรียนรู้ ครอบครัว ชีวิตครอบครัว ปัญหาภายในครอบครัว ความเชื่อ คนโบราณ


โดย: peepoobakub วันที่: 14 มีนาคม 2560 เวลา:12:20:24 น.  

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.