วิทยานิพนธ์ของคริสตจักร-ทัวริงหมายถึงแนวคิดของวิธีการที่มีประสิทธิภาพ เป็นระบบ หรือเชิงกลไกในด้านตรรกศาสตร์ คณิตศาสตร์ และวิทยาการคอมพิวเตอร์ มันถูกจัดทำขึ้นเพื่อเป็นคำอธิบายของแนวคิดเชิงสัญชาตญาณของความสามารถในการคำนวณ และในความสัมพันธ์กับฟังก์ชันแบบเรียกซ้ำทั่วไป มักเรียกว่าวิทยานิพนธ์ของศาสนจักร นอกจากนี้ยังหมายถึงทฤษฎีของฟังก์ชันที่คอมพิวเตอร์คำนวณได้ วิทยานิพนธ์นี้ปรากฏในช่วงทศวรรษที่ 1930 เมื่อยังไม่มีคอมพิวเตอร์เอง ภายหลังได้รับการตั้งชื่อตามโบสถ์ Alonso Church นักคณิตศาสตร์ชาวอเมริกันและ Alan Turing เพื่อนร่วมงานชาวอังกฤษของเขา
ประสิทธิภาพของวิธีการเพื่อให้ได้ผลลัพธ์
อุปกรณ์แรกที่คล้ายกับคอมพิวเตอร์สมัยใหม่คือ Bombie เครื่องจักรที่สร้างโดย Alan Turing นักคณิตศาสตร์ชาวอังกฤษ ใช้เพื่อถอดรหัสข้อความภาษาเยอรมันในช่วงสงครามโลกครั้งที่สอง แต่สำหรับวิทยานิพนธ์ของเขาและการทำให้แนวคิดของอัลกอริธึมเป็นทางการนั้น เขาใช้เครื่องจักรที่เป็นนามธรรม ซึ่งต่อมาเรียกว่าเครื่องจักรทัวริง วิทยานิพนธ์นำเสนอความสนใจของทั้งนักคณิตศาสตร์และโปรแกรมเมอร์ เนื่องจากแนวคิดนี้เป็นแรงบันดาลใจให้ผู้สร้างคอมพิวเตอร์เครื่องแรก
ในทฤษฎีการคำนวณ วิทยานิพนธ์ของคริสตจักร-ทัวริงเรียกอีกอย่างว่าการคาดเดาเกี่ยวกับธรรมชาติของฟังก์ชันที่คำนวณได้ มันระบุว่าสำหรับฟังก์ชันใดๆ ที่คำนวณได้ด้วยอัลกอริธึมของตัวเลขธรรมชาติ จะมีเครื่องทัวริงที่สามารถคำนวณได้ หรือมีอัลกอริธึมที่เหมาะสมกับมัน ตัวอย่างที่รู้จักกันดีของประสิทธิผลของวิธีนี้คือการทดสอบตารางความจริงสำหรับการทดสอบความซ้ำซากจำเจ
วิธีที่จะบรรลุผลลัพธ์ที่ต้องการเรียกว่า "มีประสิทธิภาพ", "ระบบ" หรือ "กลไก" ถ้า:
- วิธีการนี้กำหนดเป็นคำสั่งจำนวนจำกัด แต่ละคำสั่งจะแสดงโดยใช้จำนวนอักขระที่จำกัด
- จะทำงานโดยไม่มีข้อผิดพลาดจะให้ผลลัพธ์ตามที่ต้องการในจำนวนขั้นตอนที่กำหนด
- มนุษย์สามารถทำได้โดยไม่ต้องใช้อุปกรณ์ใดๆ ยกเว้นกระดาษและดินสอ
- มันไม่ต้องการความเข้าใจ สัญชาตญาณ หรือความเฉลียวฉลาดจากผู้ดำเนินการ
ก่อนหน้านี้ในวิชาคณิตศาสตร์ คำศัพท์ทางการ "คำนวณได้อย่างมีประสิทธิภาพ" ใช้เพื่ออ้างถึงฟังก์ชันที่สามารถคำนวณได้ด้วยดินสอและกระดาษ แต่แนวคิดเรื่องความสามารถในการคำนวณด้วยอัลกอริธึมนั้นเข้าใจได้ง่ายกว่าอะไรที่เป็นรูปธรรม ตอนนี้มีคุณลักษณะโดยฟังก์ชันที่มีอาร์กิวเมนต์ตามธรรมชาติซึ่งมีอัลกอริธึมการคำนวณ ความสำเร็จอย่างหนึ่งของ Alan Turing คือการแสดงกริยาที่แน่นอนอย่างเป็นทางการด้วยความช่วยเหลือซึ่งจะสามารถแทนที่ภาคแสดงที่ไม่เป็นทางการได้หากใช้เงื่อนไขประสิทธิภาพของวิธีการ คริสตจักรค้นพบสิ่งเดียวกัน
แนวคิดพื้นฐานของฟังก์ชันแบบเรียกซ้ำ
การเปลี่ยนเพรดิเคตของทัวริงในแวบแรกดูแตกต่างไปจากที่เพื่อนร่วมงานของเขาเสนอ แต่ผลที่ได้กลับกลายเป็นว่าเท่ากัน ในแง่ที่ว่าแต่ละคนเลือกฟังก์ชันทางคณิตศาสตร์ชุดเดียวกัน วิทยานิพนธ์ของคริสตจักร-ทัวริงเป็นการยืนยันว่าชุดนี้ประกอบด้วยทุกหน้าที่ซึ่งค่าต่างๆ หาได้จากวิธีการที่ตรงตามเงื่อนไขของประสิทธิภาพ มีความแตกต่างอีกประการหนึ่งระหว่างการค้นพบทั้งสอง คริสตจักรพิจารณาเพียงตัวอย่างของจำนวนเต็มบวก ขณะที่ทัวริงอธิบายงานของเขาว่าครอบคลุมฟังก์ชันที่คำนวณได้ด้วยอินทิกรัลหรือตัวแปรจริง
ฟังก์ชั่นเรียกซ้ำทั่วไป
สูตรดั้งเดิมของคริสตจักรระบุว่าการคำนวณสามารถทำได้โดยใช้แคลคูลัส λ ซึ่งเทียบเท่ากับการใช้ฟังก์ชันเรียกซ้ำทั่วไป วิทยานิพนธ์ของคริสตจักร-ทัวริงครอบคลุมประเภทของการคำนวณมากกว่าที่คิดไว้ในตอนแรก ตัวอย่างเช่น ที่เกี่ยวข้องกับเซลลูลาร์ออโตมาตา, คอมบิเนเตอร์, เครื่องลงทะเบียน และระบบทดแทน ในปี 1933 นักคณิตศาสตร์ Kurt Gödel และ Jacques Herbrand ได้สร้างคำจำกัดความอย่างเป็นทางการของคลาสที่เรียกว่าฟังก์ชันเรียกซ้ำทั่วไป มันใช้ฟังก์ชันที่มีมากกว่าหนึ่งอาร์กิวเมนต์
สร้างวิธีการแคล-แคลคูลัส
ในปี ค.ศ. 1936 โบสถ์อลอนโซ่ได้สร้างวิธีการคำนวณที่เรียกว่า λ-แคลคูลัส เขามีความเกี่ยวข้องกับจำนวนธรรมชาติ ภายในแคลคูลัส λ นักวิทยาศาสตร์กำหนดการเข้ารหัส ด้วยเหตุนี้จึงเรียกว่าหมายเลขศาสนจักร ฟังก์ชันที่ยึดตามจำนวนธรรมชาติเรียกว่า λ-computable มีคำจำกัดความอื่น ฟังก์ชันจากวิทยานิพนธ์ของศาสนจักรเรียกว่า λ-คำนวณได้ภายใต้เงื่อนไขสองประการ อันแรกมีเสียงดังนี้: หากคำนวณจากองค์ประกอบของศาสนจักร และเงื่อนไขที่สองคือความเป็นไปได้ที่สมาชิกของแคลคูลัสจะเป็นตัวแทน
ในปี 1936 ก่อนศึกษางานของเพื่อนร่วมงาน ทัวริงได้สร้างแบบจำลองทางทฤษฎีสำหรับเครื่องนามธรรมซึ่งปัจจุบันตั้งชื่อตามเขา พวกเขาสามารถทำการคำนวณโดยจัดการกับอักขระบนเทป นอกจากนี้ยังใช้กับกิจกรรมทางคณิตศาสตร์อื่นๆ ที่พบในวิทยาการคอมพิวเตอร์เชิงทฤษฎี เช่น การคำนวณความน่าจะเป็นควอนตัม ฟังก์ชั่นจากวิทยานิพนธ์ของคริสตจักรได้รับการพิสูจน์ในภายหลังโดยใช้เครื่องทัวริงเท่านั้น ตอนแรกก็พึ่ง λ-แคลคูลัส
การคำนวณของฟังก์ชัน
เมื่อตัวเลขธรรมชาติถูกเข้ารหัสอย่างเหมาะสมเป็นลำดับอักขระ ฟังก์ชันของตัวเลขธรรมชาติจะเรียกว่าทัวริงคำนวณได้ หากเครื่องนามธรรมพบอัลกอริธึมที่ต้องการและพิมพ์ฟังก์ชันนี้ลงบนเทป อุปกรณ์ดังกล่าวซึ่งไม่มีอยู่ในทศวรรษที่ 1930 จะถือเป็นคอมพิวเตอร์ในอนาคต เครื่องทัวริงที่เป็นนามธรรมและวิทยานิพนธ์ของคริสตจักรได้ประกาศยุคแห่งการพัฒนาอุปกรณ์คอมพิวเตอร์ ได้รับการพิสูจน์แล้วว่าคลาสของฟังก์ชันที่กำหนดอย่างเป็นทางการโดยนักวิทยาศาสตร์ทั้งสองตรงกัน ดังนั้น ทั้งสองประโยคจึงถูกรวมเป็นหนึ่งเดียว ฟังก์ชันการคำนวณและวิทยานิพนธ์ของศาสนจักรมีอิทธิพลอย่างมากต่อแนวคิดเรื่องความสามารถในการคำนวณ พวกเขายังกลายเป็นเครื่องมือสำคัญสำหรับตรรกะทางคณิตศาสตร์และทฤษฎีการพิสูจน์
เหตุผลและปัญหาของวิธีการ
มีความคิดเห็นขัดแย้งในวิทยานิพนธ์ มีการรวบรวมหลักฐานจำนวนมากสำหรับ "สมมติฐานด้านการทำงาน" ที่เสนอโดย Church and Turing ในปี 1936 แต่วิธีการหรือการดำเนินการที่รู้จักทั้งหมดสำหรับการค้นหาฟังก์ชันที่คำนวณได้อย่างมีประสิทธิภาพใหม่จากฟังก์ชันที่กำหนดนั้นเชื่อมโยงกับวิธีการสร้างเครื่องจักรซึ่งไม่มีอยู่ในขณะนั้น ในการพิสูจน์วิทยานิพนธ์ของ Church-Turing เราเริ่มจากข้อเท็จจริงที่ว่าแบบจำลองการคำนวณที่เหมือนจริงทุกรูปแบบนั้นเทียบเท่ากัน
เนื่องจากการวิเคราะห์ต่างๆ ที่หลากหลาย โดยทั่วไปถือว่าเป็นข้อพิสูจน์ที่หนักแน่นเป็นพิเศษ ความพยายามทั้งหมดที่จะกำหนดแนวคิดเชิงสัญชาตญาณของฟังก์ชันที่คำนวณได้อย่างมีประสิทธิผลได้อย่างแม่นยำยิ่งขึ้นกลับกลายเป็นว่าเทียบเท่ากัน ทุกการวิเคราะห์ที่เสนอมานั้นได้พิสูจน์ให้เห็นถึงฟังก์ชันระดับเดียวกัน กล่าวคือการวิเคราะห์ที่คำนวณได้ด้วยเครื่องจักรทัวริง แต่โมเดลการคำนวณบางรุ่นกลับมีประสิทธิภาพมากกว่าในแง่ของเวลาและการใช้หน่วยความจำสำหรับงานที่แตกต่างกัน ต่อมามีการตั้งข้อสังเกตว่าแนวคิดพื้นฐานของฟังก์ชันแบบเรียกซ้ำและวิทยานิพนธ์ของศาสนจักรค่อนข้างเป็นเรื่องสมมุติ
วิทยานิพนธ์ M
สิ่งสำคัญคือต้องแยกความแตกต่างระหว่างวิทยานิพนธ์ของทัวริงกับการยืนยันว่าทุกสิ่งที่อุปกรณ์คอมพิวเตอร์คำนวณสามารถคำนวณได้ด้วยเครื่องของมัน ตัวเลือกที่สองมีคำจำกัดความของตัวเอง คานธีเรียกประโยคที่สองว่า "วิทยานิพนธ์ M" เป็นดังนี้: "สิ่งที่อุปกรณ์สามารถคำนวณได้สามารถคำนวณได้ด้วยเครื่องทัวริง" ในความหมายที่แคบของวิทยานิพนธ์ มันเป็นข้อเสนอเชิงประจักษ์ที่ไม่ทราบค่าความจริง วิทยานิพนธ์ของทัวริงและ "วิทยานิพนธ์ M" บางครั้งสับสน รุ่นที่สองไม่ถูกต้องในวงกว้าง มีการอธิบายเครื่องจักรตามเงื่อนไขต่างๆ ที่สามารถคำนวณฟังก์ชันที่ไม่สามารถคำนวณได้ของทัวริง สิ่งสำคัญคือต้องสังเกตว่า วิทยานิพนธ์แรกไม่ได้เกี่ยวข้องกับครั้งที่สอง แต่สอดคล้องกับความเท็จของวิทยานิพนธ์
ความหมายย้อนกลับของวิทยานิพนธ์
ในทฤษฎีการคำนวณ วิทยานิพนธ์ของคริสตจักรใช้เป็นคำอธิบายของแนวคิดเรื่องความสามารถในการคำนวณโดยคลาสของฟังก์ชันเรียกซ้ำทั่วไป American Stephen Kleene ให้สูตรทั่วไปมากขึ้น เขาเรียกว่าเรียกซ้ำบางส่วนว่าฟังก์ชันบางส่วนทั้งหมดที่คำนวณได้โดยอัลกอริทึม
ความหมายย้อนกลับมักเรียกว่าวิทยานิพนธ์ย้อนกลับของคริสตจักร มันอยู่ในความจริงที่ว่าทุกฟังก์ชันแบบเรียกซ้ำของจำนวนเต็มบวกได้รับการประเมินอย่างมีประสิทธิภาพ ในความหมายที่แคบ วิทยานิพนธ์เพียงแสดงถึงความเป็นไปได้ดังกล่าว และในความหมายที่กว้างกว่า มันสรุปจากคำถามที่ว่าเครื่องแบบมีเงื่อนไขนี้สามารถมีอยู่ในนั้นได้หรือไม่
คอมพิวเตอร์ควอนตัม
แนวคิดของฟังก์ชันที่คำนวณได้และวิทยานิพนธ์ของศาสนจักรกลายเป็นการค้นพบที่สำคัญสำหรับคณิตศาสตร์ ทฤษฎีเครื่อง และวิทยาศาสตร์อื่นๆ อีกมากมาย แต่เทคโนโลยีเปลี่ยนไปมากและปรับปรุงอย่างต่อเนื่อง สันนิษฐานว่าคอมพิวเตอร์ควอนตัมสามารถทำงานทั่วไปหลายอย่างโดยใช้เวลาน้อยกว่างานสมัยใหม่ แต่คำถามยังคงอยู่เช่นปัญหาการหยุด คอมพิวเตอร์ควอนตัมไม่สามารถตอบได้ และตามวิทยานิพนธ์ของคริสตจักร-ทัวริง ไม่มีอุปกรณ์คอมพิวเตอร์อื่นด้วย
