ความบริบูรณ์ของทัวริง
ในทฤษฎีการคำนวณได้ ระบบของกฎเกณฑ์ในการจัดการข้อมูล (เช่น แบบจำลองการคำนวณ ชุดของคำสั่งเครื่อง ภาษาโปรแกรม หรือเซลลูลาร์ออโตมาตา) จะถูกเรียกว่ามีความบริบูรณ์ของทัวริง (อังกฤษ: Turing-complete) หรือมีความสมบูรณ์ทางการคำนวณ (อังกฤษ: computationally universal) หากระบบนั้นสามารถใช้จำลองการทำงานของเครื่องทัวริงใด ๆ ก็ได้[1][2] ซึ่งเครื่องทัวริงเป็นแบบจำลองเชิงนามธรรมที่คิดค้นโดย แอลัน ทัวริง นักคณิตศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์ชาวอังกฤษ คุณสมบัตินี้หมายความว่า ระบบดังกล่าวมีความสามารถในการจำลองการคำนวณของระบบการจัดการข้อมูลรูปแบบอื่น ๆ ได้ทั้งหมด ดังนั้น ความบริบูรณ์ของทัวริงจึงมักถูกใช้เป็นเกณฑ์ในการบ่งบอกถึงขีดความสามารถในการคำนวณของระบบนั้น ๆ โดยในปัจจุบัน ภาษาโปรแกรมเกือบทุกภาษาล้วนมีคุณสมบัตินี้
แนวคิดที่เกี่ยวเนื่องกันคือ ความเท่าเทียมกันแบบทัวริง (Turing equivalence) โดยคอมพิวเตอร์สองเครื่อง (สมมติว่าเป็น P และ Q) จะถูกเรียกว่ามีความเท่าเทียมกัน หาก P สามารถจำลองการทำงานของ Q ได้ และ Q ก็สามารถจำลองการทำงานของ P ได้เช่นกัน[3] ข้อปัญหาของเชิร์ช-ทัวริงเสนอว่า ฟังก์ชันใด ๆ ที่สามารถคำนวณได้ด้วยอัลกอริทึม ย่อมสามารถคำนวณได้ด้วยเครื่องทัวริงเสมอ ดังนั้น หากคอมพิวเตอร์เครื่องใดในโลกแห่งความเป็นจริงสามารถจำลองการทำงานของเครื่องทัวริงได้ คอมพิวเตอร์เครื่องนั้นก็จะถือว่ามีความเท่าเทียมกันแบบทัวริงกับเครื่องทัวริง นอกจากนี้ เครื่องทัวริงแบบสากลยังสามารถใช้จำลองการทำงานของเครื่องทัวริงใด ๆ ได้ รวมถึงการจำลองความสามารถด้านการคำนวณเชิงนามธรรมของคอมพิวเตอร์ทุกชนิดที่เป็นไปได้ในโลกแห่งความเป็นจริง[4][5]
ในการแสดงให้เห็นว่าระบบใดระบบหนึ่งมีความบริบูรณ์ของทัวริง เพียงแสดงให้เห็นว่าระบบดังกล่าวสามารถใช้จำลองระบบอื่นที่มีความบริบูรณ์ของทัวริงอยู่แล้วได้ก็เพียงพอ แม้ว่าในทางปฏิบัติจะไม่มีระบบทางกายภาพใดที่มีหน่วยความจำไม่จำกัด แต่หากมองข้ามข้อจำกัดด้านหน่วยความจำ ภาษาโปรแกรมส่วนใหญ่ก็ถือว่ามีความบริบูรณ์ของทัวริงในแง่อื่น ๆ ครบถ้วน[6][7]
ดูเพิ่ม
[แก้]อ้างอิง
[แก้]- ↑ Tom Stuart (2013). Understanding Computation: From Simple Machines to Impossible Programs. O'Reilly Media, Inc. p. 209. ISBN 978-1-4493-3011-8. Extract of page 209
- ↑ Cristian S Calude (2024). To Halt Or Not To Halt? That Is The Question. World Scientific. p. 30. ISBN 978-981-12-3229-9. Extract of page 30
- ↑ Göktürk Üçoluk; Sinan Kalkan (2012). Introduction to Programming Concepts with Case Studies in Python (illustrated ed.). Springer Science & Business Media. p. 13. ISBN 978-3-7091-1343-1. Extract of page 13
- ↑ Ben Goertzel (2013). The Structure of Intelligence: A New Mathematical Model of Mind (illustrated ed.). Springer Science & Business Media. p. 13. ISBN 978-1-4612-4336-6. Extract of page 13
- ↑ Alan Garnham (2017). Artificial Intelligence: An Introduction. Routledge. p. 164. ISBN 978-1-351-33786-1. Extract of page 164
- ↑ Torben Ægidius Mogensen (2022). Programming Language Design and Implementation. Springer Nature. p. 6. ISBN 978-3-031-11806-7. Extract of page 6
- ↑ John R. Woodward (2003). "Modularity in Genetic Programming". ใน Conor Ryan (บ.ก.). Genetic Programming: 6th European Conference, EuroGP 2003, Essex, UK, April 14-16, 2003. Proceedings, Volume 6 (illustrated ed.). Springer Science & Business Media. p. 258. doi:10.1007/3-540-36599-0_23. ISBN 978-3-540-00971-9. Extract of page 258