ความบริบูรณ์ของทัวริง

ในทฤษฎีการคำนวณได้ ระบบของกฎเกณฑ์ในการจัดการข้อมูล (เช่น แบบจำลองการคำนวณ ชุดของคำสั่งเครื่อง ภาษาโปรแกรม หรือเซลลูลาร์ออโตมาตา) จะถูกเรียกว่ามีความบริบูรณ์ของทัวริง () หรือมีความสมบูรณ์ทางการคำนวณ () หากระบบนั้นสามารถใช้จำลองการทำงานของเครื่องทัวริงใด ๆ ก็ได้ Extract of page 209 Extract of page 30 ซึ่งเครื่องทัวริงเป็นแบบจำลองเชิงนามธรรมที่คิดค้นโดย แอลัน ทัวริง นักคณิตศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์ชาวอังกฤษ คุณสมบัตินี้หมายความว่า ระบบดังกล่าวมีความสามารถในการจำลองการคำนวณของระบบการจัดการข้อมูลรูปแบบอื่น ๆ ได้ทั้งหมด ดังนั้น ความบริบูรณ์ของทัวริงจึงมักถูกใช้เป็นเกณฑ์ในการบ่งบอกถึงขีดความสามารถในการคำนวณของระบบนั้น ๆ โดยในปัจจุบัน ภาษาโปรแกรมเกือบทุกภาษาล้วนมีคุณสมบัตินี้

แนวคิดที่เกี่ยวเนื่องกันคือ ความเท่าเทียมกันแบบทัวริง (Turing equivalence) โดยคอมพิวเตอร์สองเครื่อง (สมมติว่าเป็น P และ Q) จะถูกเรียกว่ามีความเท่าเทียมกัน หาก P สามารถจำลองการทำงานของ Q ได้ และ Q ก็สามารถจำลองการทำงานของ P ได้เช่นกัน Extract of page 13 ข้อปัญหาของเชิร์ช-ทัวริงเสนอว่า ฟังก์ชันใด ๆ ที่สามารถคำนวณได้ด้วยอัลกอริทึม ย่อมสามารถคำนวณได้ด้วยเครื่องทัวริงเสมอ ดังนั้น หากคอมพิวเตอร์เครื่องใดในโลกแห่งความเป็นจริงสามารถจำลองการทำงานของเครื่องทัวริงได้ คอมพิวเตอร์เครื่องนั้นก็จะถือว่ามีความเท่าเทียมกันแบบทัวริงกับเครื่องทัวริง นอกจากนี้ เครื่องทัวริงแบบสากลยังสามารถใช้จำลองการทำงานของเครื่องทัวริงใด ๆ ได้ รวมถึงการจำลองความสามารถด้านการคำนวณเชิงนามธรรมของคอมพิวเตอร์ทุกชนิดที่เป็นไปได้ในโลกแห่งความเป็นจริง Extract of page 13 Extract of page 164

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

 ดูเพิ่ม 
 การจำลองเสมือน

 อ้างอิง 

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