วิทยานิพนธ์เชิร์ช–ทัวริง

วิทยานิพนธ์เชิร์ช–ทัวริงยืนยันว่าทุกฟังก์ชันที่คำนวณได้ด้วยกระบวนการที่มีประสิทธิภาพใดๆ สามารถคำนวณได้ด้วยเครื่องจักรทัวริง ซึ่งเป็นการเทียบเคียงแนวคิดที่ไม่เป็นทางการของอัลกอริทึมกับแบบจำลองทางคณิตศาสตร์ที่แม่นยำ

Definition

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

Scope

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

Core questions

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

Key theories

การบรรจบกันของแบบจำลองการคำนวณ

เครื่องจักรทัวริง, แคลคูลัสแลมบ์ดาของเชิร์ช และฟังก์ชันเวียนเกิดของเกอเดลและเฮอร์แบรนด์ ได้รับการแสดงให้เห็นว่านิยามฟังก์ชันประเภทเดียวกันอย่างแท้จริง และข้อตกลงที่เป็นอิสระนี้เป็นหลักฐานสำคัญที่เสนอสำหรับวิทยานิพนธ์นี้

สถานะเป็นวิทยานิพนธ์ ไม่ใช่ทฤษฎีบท

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

Clinical relevance

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

History

ในปี 1936 เชิร์ชได้เสนอการระบุความสามารถในการคำนวณที่มีประสิทธิภาพด้วยการนิยามด้วยแลมบ์ดา และทัวริงได้ให้เหตุผลสำหรับแบบจำลองเครื่องจักรของเขาอย่างอิสระ หลังจากนั้น ทัวริง, คลีน และคนอื่นๆ ได้พิสูจน์ว่าสิ่งเหล่านี้และฟังก์ชันเวียนเกิดมีความเทียบเท่ากัน เกอเดลซึ่งเดิมทีไม่เชื่อ ได้มาพิจารณาการวิเคราะห์ของทัวริงว่าสรุปได้ และข้อกล่าวอ้างที่รวมกันนี้เป็นที่รู้จักกันในชื่อวิทยานิพนธ์เชิร์ช–ทัวริง

Debates

การคำนวณทางกายภาพสามารถก้าวข้ามขีดจำกัดของทัวริงได้หรือไม่?

วิทยานิพนธ์ดั้งเดิมเกี่ยวข้องกับกระบวนการที่มีประสิทธิภาพ แต่เวอร์ชันทางกายภาพที่แข็งแกร่งกว่าอ้างว่าไม่มีอุปกรณ์ที่สามารถสร้างขึ้นทางกายภาพใดๆ ที่สามารถคำนวณฟังก์ชันที่ไม่สามารถคำนวณได้ด้วยทัวริง ข้อเสนอสำหรับการคำนวณเกินขีดจำกัด (hypercomputation) และนัยยะของกลศาสตร์ควอนตัมทำให้ข้อกล่าวอ้างที่ขยายออกไปนี้ยังคงเป็นที่ถกเถียงกันอยู่ แม้ว่าวิทยานิพนธ์คลาสสิกจะยังคงไม่ถูกท้าทายโดยพื้นฐาน

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

เหตุใดจึงเรียกว่าวิทยานิพนธ์แทนที่จะเป็นทฤษฎีบท?

มันเชื่อมโยงแบบจำลองที่เป็นทางการเข้ากับแนวคิดที่ไม่เป็นทางการของกระบวนการที่มีประสิทธิภาพ และแนวคิดที่ไม่เป็นทางการนั้นไม่มีคำนิยามทางคณิตศาสตร์ที่จะพิสูจน์สิ่งต่างๆ ได้ หลักฐานที่แข็งแกร่งคือความพยายามที่เป็นอิสระทุกครั้งในการทำให้การคำนวณเป็นทางการได้ให้ผลลัพธ์เป็นฟังก์ชันประเภทเดียวกัน แต่การสนับสนุนนี้เป็นแนวคิดมากกว่าการพิสูจน์

คอมพิวเตอร์ควอนตัมหักล้างวิทยานิพนธ์เชิร์ช–ทัวริงหรือไม่?

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