ในทฤษฎีความสามารถในการคำนวณระบบของกฎการจัดการข้อมูล (เช่นแบบจำลองการคำนวณชุดคำสั่งของคอมพิวเตอร์ภาษาโปรแกรมหรือออโตมาตาเซลลูลาร์ ) เรียกว่าสมบูรณ์แบบทัวริงหรือเป็นสากลในการคำนวณหากสามารถใช้จำลองเครื่องจักรทัวริง ใดๆ ได้ ^{[ 1 ] [ 2 ]} (คิดค้นโดยนักคณิตศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์ชาวอังกฤษอลัน ทัวริง ) ซึ่งหมายความว่าระบบนี้สามารถรับรู้หรือถอดรหัสชุดกฎการจัดการข้อมูลอื่นๆ ได้ ความสมบูรณ์แบบทัวริงถูกใช้เป็นวิธีในการแสดงพลังของชุดกฎการจัดการข้อมูลดังกล่าว ภาษาโปรแกรมเกือบทั้งหมดในปัจจุบันสมบูรณ์แบบทัวริง^{[ a ]}

แนวคิดที่เกี่ยวข้องคือความสมมูลของทัวริง  – คอมพิวเตอร์สองเครื่อง P และ Q เรียกว่าสมมูลกันหาก P สามารถจำลอง Q ได้ และ Q สามารถจำลอง P ได้^{[ 4 ]} วิทยานิพนธ์ ของChurch–Turingตั้งสมมติฐานว่าฟังก์ชันใดๆ ที่สามารถคำนวณค่าได้ด้วยอัลกอริทึมก็สามารถคำนวณได้ด้วยเครื่องทัวริง ดังนั้น หากคอมพิวเตอร์ในโลกแห่งความเป็นจริงใดๆ สามารถจำลองเครื่องทัวริงได้ ก็จะถือว่าสมมูลกับเครื่องทัวริง เครื่องทัวริงสากลสามารถใช้จำลองเครื่องทัวริงใดๆ ก็ได้ และโดยนัยเดียวกันก็สามารถใช้จำลองด้านการคำนวณล้วนๆ ของคอมพิวเตอร์ในโลกแห่งความเป็นจริงใดๆ ก็ได้^{[ 5 ] [ 6 ]}

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

ใน การใช้งาน ทั่วไปคำว่า "สมบูรณ์ตามทฤษฎีของทัวริง" (Turing-complete) และ "เทียบเท่าตามทฤษฎีของทัวริง" (Turing-equivalent) หมายความว่า คอมพิวเตอร์หรือภาษาคอมพิวเตอร์อเนกประสงค์ในโลกแห่งความเป็นจริงใดๆ ก็ตาม สามารถจำลองลักษณะการคำนวณของคอมพิวเตอร์หรือภาษาคอมพิวเตอร์อเนกประสงค์ในโลกแห่งความเป็นจริงอื่นๆ ได้อย่างคร่าวๆ ในชีวิตจริง สิ่งนี้จึงนำไปสู่แนวคิดเชิงปฏิบัติของการจำลองเสมือน (virtualization ) และ การจำลองการทำงานของคอมพิวเตอร์ (emulation )

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

ในทฤษฎีความสามารถในการคำนวณมีคำศัพท์ที่เกี่ยวข้องกันหลายคำที่ใช้เพื่ออธิบายพลังการคำนวณของระบบคำนวณ (เช่นเครื่องจักรนามธรรมหรือภาษาโปรแกรม ):

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

ระบบคอมพิวเตอร์ที่สามารถคำนวณฟังก์ชันที่คำนวณ ได้ด้วยเครื่องจักรทัวริงทุกฟังก์ชัน เรียกว่า ระบบที่สมบูรณ์แบบทัวริง (หรือ ระบบทรงพลังทัวริง) หรืออีกนัยหนึ่ง ระบบดังกล่าวคือระบบที่สามารถจำลองเครื่องจักรทัวริงสากลได้

ความสมมูลของทัวริง

ระบบที่สมบูรณ์แบบตามทฤษฎีของทัวริง (Turing-complete system) เรียกว่า ระบบที่เทียบเท่ากับทัวริง (Turing-equivalent system) หากทุกฟังก์ชันที่ระบบนั้นสามารถคำนวณได้ ก็สามารถคำนวณได้ ด้วย เครื่องจักรทัวริง (Turing machine) เช่นกัน กล่าวคือ ระบบนั้นคำนวณฟังก์ชันในกลุ่มเดียวกันกับ ที่เครื่องจักรทัวริงคำนวณได้ หรืออีกนัยหนึ่ง ระบบที่เทียบเท่ากับทัวริง คือ ระบบที่สามารถจำลอง และถูกจำลองโดยเครื่องจักรทัวริงสากลได้ (ระบบที่สมบูรณ์แบบตามทฤษฎีของทัวริงที่สามารถนำไปใช้งานได้จริงทั้งหมด ล้วนเป็นระบบที่เทียบเท่ากับทัวริง ซึ่งเป็นการสนับสนุนทฤษฎีบทของเชิร์ช-ทัวริง )

ความเป็นสากล (เชิงคำนวณ)

ระบบหนึ่งๆ จะถูกเรียกว่าเป็นระบบสากล (universal) เมื่อเทียบกับระบบกลุ่มหนึ่งๆ หากระบบนั้นสามารถคำนวณฟังก์ชันทุกฟังก์ชันที่ระบบในกลุ่มนั้นสามารถคำนวณได้ (หรือสามารถจำลองระบบเหล่านั้นได้ทั้งหมด) โดยทั่วไปแล้ว คำว่า "ความเป็นสากล" มักถูกใช้โดยปริยายเมื่อเทียบกับระบบกลุ่มที่สมบูรณ์แบบตามทฤษฎีของทัวริง (Turing-complete) คำว่า "สากลแบบอ่อน" (weakly universal) บางครั้งใช้เพื่อแยกแยะระบบ (เช่นออโตมาตาเซลลูลาร์ ) ที่มีความเป็นสากลได้ก็ต่อเมื่อมีการปรับเปลี่ยนนิยามมาตรฐานของเครื่องจักรทัวริงเพื่อให้รวมกระแสข้อมูลเข้าที่มีเลข 1 จำนวนอนันต์เข้าไปด้วย

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

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

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

แนวคิดเรื่องการคำนวณที่แท้จริงได้รับการแยกออกมาในเวลาต่อมา โดยเริ่มต้นจากทฤษฎีบทความไม่สมบูรณ์ของเกอเดลทฤษฎีบทนี้แสดงให้เห็นว่าระบบสัจพจน์มีข้อจำกัดเมื่อให้เหตุผลเกี่ยวกับการคำนวณที่อนุมานทฤษฎีบทเหล่านั้น เชิร์ชและทัวริงได้แสดงให้เห็นโดยอิสระว่าปัญหาการตัดสินใจของฮิลเบิร์ต ( Entscheidungsproblem ) ไม่สามารถ แก้ไขได้ ^{[ 9 ]}จึงระบุแก่นหลักของการคำนวณของทฤษฎีบทความไม่สมบูรณ์ งานนี้ร่วมกับงานของเกอเดลเกี่ยวกับฟังก์ชันเรียกซ้ำทั่วไป ได้พิสูจน์ว่ามีชุดคำสั่งง่ายๆ ซึ่งเมื่อนำมารวมกันแล้วสามารถสร้างการคำนวณใดๆ ก็ได้ งานของเกอเดลแสดงให้เห็นว่าแนวคิดเรื่องการคำนวณนั้นมีเอกลักษณ์เฉพาะตัว

ในปี พ.ศ. 2484 Konrad Zuse ได้สร้างคอมพิวเตอร์ Z3เสร็จสมบูรณ์Zuse ยังไม่คุ้นเคยกับงานของ Turing เกี่ยวกับความสามารถในการคำนวณในขณะนั้น โดยเฉพาะอย่างยิ่ง Z3 ขาดสิ่งอำนวยความสะดวกเฉพาะสำหรับการกระโดดแบบมีเงื่อนไข ซึ่งทำให้ไม่สามารถเป็น Turing complete ได้ อย่างไรก็ตาม ในปี พ.ศ. 2541 Rojas ได้แสดงให้เห็นว่า Z3 สามารถจำลองการกระโดดแบบมีเงื่อนไขได้ และด้วยเหตุนี้จึงเป็น Turing complete ในทางทฤษฎี ในการทำเช่นนี้ โปรแกรมเทปของมันจะต้องยาวพอที่จะดำเนินการทุกเส้นทางที่เป็นไปได้ผ่านทั้งสองด้านของทุกสาขา^{[ 10 ]}

คอมพิวเตอร์เครื่องแรกที่สามารถทำการแยกสาขาแบบมีเงื่อนไขได้ในทางปฏิบัติ และด้วยเหตุนี้จึงสามารถคำนวณแบบทัวริงได้ในทางปฏิบัติ คือENIAC ในปี พ.ศ. 2489 คอมพิวเตอร์ Z4ของ Zuse สามารถใช้งานได้ในปี พ.ศ. 2488 แต่ไม่รองรับการแยกสาขาแบบมีเงื่อนไขจนกระทั่งปี พ.ศ. 2493 ^{[ 11 ]}

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

ตัวอย่างคลาสสิกคือปัญหาการหยุดทำงาน (halting problem) : สร้างอัลกอริทึมที่รับโปรแกรมในภาษาที่สมบูรณ์แบบตามทฤษฎีบททัวริง (Turing-complete language) และข้อมูลที่จะป้อนให้กับ โปรแกรม นั้น เป็น อินพุต และตรวจสอบว่าโปรแกรมนั้น เมื่อทำงานกับอินพุตแล้ว จะหยุดทำงานในที่สุดหรือจะทำงานต่อไปตลอดกาล การสร้างอัลกอริทึมที่สามารถทำเช่นนี้ได้สำหรับ อินพุต บางอย่างนั้น ทำได้ง่าย แต่เป็นไปไม่ได้ที่จะทำเช่นนี้ในกรณีทั่วไป สำหรับลักษณะใด ๆ ของผลลัพธ์สุดท้ายของโปรแกรมนั้น เป็นไปไม่ได้ที่จะตรวจสอบว่าลักษณะนั้นจะคงอยู่หรือไม่

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

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

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

กฎฟิสิกส์ที่รู้จักทั้งหมดมีผลลัพธ์ที่สามารถคำนวณได้ด้วยชุดการประมาณบนคอมพิวเตอร์ดิจิทัล สมมติฐานที่เรียกว่าฟิสิกส์ดิจิทัลระบุว่านี่ไม่ใช่เรื่องบังเอิญเพราะจักรวาลเองสามารถคำนวณได้บนเครื่องทัวริงสากล ซึ่งหมายความว่าไม่สามารถสร้างคอมพิวเตอร์ที่ทรงพลังกว่าเครื่องทัวริงสากลได้ในทางกายภาพ^{[ 12 ]}

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

• ทฤษฎีออโตมาตา
• ไวยากรณ์เชิงรูปธรรม (เครื่องมือสร้างภาษา)
• ภาษาทางการ (ตัวรับรู้ภาษา)
• แคลคูลัสแลมบ์ดา
• เครื่องจักรหลังทัวริง
• แคลคูลัสกระบวนการ

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

• ภาษาโปรแกรมทั่วไปที่ใช้กันอย่างแพร่หลายทั้งหมด
  • ภาษา การเขียนโปรแกรมเชิงขั้นตอนเช่นCและPascal
  • ภาษา โปรแกรมเชิงวัตถุเช่นJava , SmalltalkหรือC #
  • ภาษาโปรแกรมแบบหลายกระบวนทัศน์เช่นAda , C++ , Common Lisp , Fortran , JavaScript , Object Pascal , Perl , PythonและR
• ภาษาส่วนใหญ่ใช้รูปแบบไวยากรณ์ที่ไม่ค่อยพบเห็นทั่วไป:
  • ภาษาโปรแกรมเชิงฟังก์ชันเช่นLispและHaskell
  • ภาษาการ เขียนโปรแกรมเชิงตรรกะเช่นProlog
  • ตัว ประมวลผลมาโครอเนกประสงค์เช่นm4
  • ภาษา เชิงประกาศเช่นSQLและXSLT ^{[ 13 ] [ 14 ]}
  • VHDLและภาษาอื่นๆ ที่ใช้ในการอธิบายฮาร์ดแวร์
  • TeXคือระบบจัดพิมพ์เอกสาร
  • ภาษาโปรแกรมเชิงลึกลับคือรูปแบบหนึ่งของกิจกรรมทางคณิตศาสตร์ที่โปรแกรมเมอร์ใช้ในการค้นหาวิธีการสร้างโครงสร้างพื้นฐานของโปรแกรมในภาษาที่ยากมาก แต่มีคุณสมบัติเทียบเท่ากับเครื่องจักรทัวริงทางคณิตศาสตร์

ระบบการเขียนใหม่บาง ระบบ มีความสามารถเทียบเท่าเครื่องจักรทัวริง (Turing-complete)

ความสมบูรณ์แบบของทัวริงเป็นข้อความเชิงนามธรรมของความสามารถ มากกว่าจะเป็นข้อกำหนดของคุณลักษณะภาษาเฉพาะที่ใช้ในการนำความสามารถนั้นไปใช้ คุณลักษณะที่ใช้เพื่อให้บรรลุความสมบูรณ์แบบของทัวริงอาจแตกต่างกันมาก ระบบ Fortran จะใช้โครงสร้างลูปหรืออาจ ใช้คำสั่ง gotoเพื่อให้เกิดการทำซ้ำ ในขณะที่ Haskell และ Prolog ซึ่งแทบไม่มีลูปเลย จะใช้การเรียกซ้ำภาษาโปรแกรมส่วนใหญ่จะอธิบายการคำนวณบนสถาปัตยกรรม von Neumannซึ่งมีหน่วยความจำ (RAM และรีจิสเตอร์) และหน่วยควบคุม องค์ประกอบทั้งสองนี้ทำให้สถาปัตยกรรมนี้สมบูรณ์แบบของทัวริง แม้แต่ภาษาฟังก์ชัน บริสุทธิ์ก็ สมบูรณ์แบบของทัวริง^{[ 15 ] [ 16 ]}

ความสมบูรณ์แบบของทัวริงใน SQL แบบประกาศนั้นถูกนำไปใช้ผ่านนิพจน์ตารางทั่วไปแบบเรียกซ้ำ และไม่น่าแปลกใจที่ส่วนขยายเชิงกระบวนการของ SQL ( PLSQLเป็นต้น) ก็มีความสมบูรณ์แบบของทัวริงเช่นกัน นี่แสดงให้เห็นถึงเหตุผลหนึ่งว่าทำไมภาษาที่มีประสิทธิภาพค่อนข้างสูงแต่ไม่สมบูรณ์แบบของทัวริงจึงหายาก: ยิ่งภาษามีประสิทธิภาพมากเท่าใด งานที่นำไปใช้ก็จะยิ่งซับซ้อนมากขึ้นเท่านั้น และการขาดความสมบูรณ์แบบก็จะถูกมองว่าเป็นข้อเสียเร็วขึ้นเท่านั้น ซึ่งจะกระตุ้นให้มีการขยายภาษาจนกว่าจะสมบูรณ์แบบของทัวริง

แคลคูลัสแลมบ์ดาแบบไม่ระบุชนิดนั้นสมบูรณ์แบบทัวริง แต่แคลคูลัสแลมบ์ดาแบบระบุชนิดหลายตัว รวมถึงSystem Fนั้นไม่สมบูรณ์แบบทัวริง คุณค่าของระบบแบบระบุชนิดนั้นอยู่ที่ความสามารถในการแสดงโปรแกรมคอมพิวเตอร์ทั่วไปส่วนใหญ่พร้อมทั้งตรวจจับข้อผิดพลาดได้มากขึ้น

กฎข้อที่ 110และเกมชีวิตของคอนเวย์ซึ่งทั้งคู่เป็นออโตมาตาเซลลูลาร์ล้วนเป็นระบบที่สมบูรณ์แบบตามทฤษฎีบททัวริง

ซอฟต์แวร์และวิดีโอเกมบาง เกม มีความสมบูรณ์แบบตามทฤษฎีบททัวริงโดยบังเอิญ กล่าวคือ ไม่ได้เกิดจากการออกแบบ

ซอฟต์แวร์:

• ไมโครซอฟต์ เอ็กเซล^{[ 17 ]}
• JIRA ^{[ 18 ]}

เกม:

• บาบาคือคุณ^{[ 19 ]}
• ป้อมปราการคนแคระ^{[ 20 ]}
• เมือง: สกายไลน์^{[ 21 ]}
• โอปุส แม็กนัม^{[ 22 ]}
• เมจิก: เดอะ แกเธอริ่ง^{[ 23 ] [ 24 ]}
• Minecraft ^{[ 25 ]}
• เกม Minesweeperแบบตารางอนันต์^{[ 26 ]}
• เกมCivilization ของ Sid Meierบางเกม^{[ 27 ]}

สื่อสังคมออนไลน์:

• โรงแรมฮับโบ^{[ 28 ]}

ภาษาคอมพิวเตอร์:

• เทมเพลต C++ ^{[ 29 ]}
• printfรูปแบบสตริง^{[ 30 ]}
• ระบบประเภทของTypeScript ^{[ 31 ]}
• คำสั่ง MOV ของภาษาแอสเซมบลี x86 ^{[ 32 ] [ 33 ] [ 34 ]}
• ฟอนต์TrueType ^{[ 35 ]}

ชีววิทยา:

• เครือข่ายปฏิกิริยาเคมี^{[ 36 ] [ 37 ] [ 38 ] [ 39 ]}และคอมพิวเตอร์ DNA ที่ใช้เอนไซม์^{[ 40 ]}ได้รับการพิสูจน์แล้วว่าเทียบเท่ากับทัวริง

ระบบทางกายภาพ:

• บิลเลียด^{[ 41 ]}

มีภาษาคำนวณมากมายที่ไม่ใช่ภาษาที่สมบูรณ์แบบตามทฤษฎีบททัวริง (Turing-complete) ตัวอย่างหนึ่งคือเซตของภาษาปกติ (regular languages ) ซึ่งสร้างขึ้นจากนิพจน์ปกติ (regular expressions ) และได้รับการยอมรับจากออโตมาตาจำกัด (finite automata ) ส่วนขยายที่ทรงพลังกว่าแต่ก็ยังไม่ใช่ภาษาที่สมบูรณ์แบบตามทฤษฎีบททัวริงของออโตมาตาจำกัด คือ หมวดหมู่ของ ออโต มาตาแบบพุชดาวน์ (pushdown automata)และไวยากรณ์แบบไร้บริบท (context-free grammars)ซึ่งมักใช้ในการสร้างแผนผังการวิเคราะห์ (parse tree) ในขั้นตอนเริ่มต้นของการคอมไพล์ โปรแกรม ตัวอย่างเพิ่มเติม ได้แก่ ภาษาพิกเซลเชเดอร์เวอร์ชันแรกๆ บางเวอร์ชันที่ฝังอยู่ในส่วนขยาย Direct3DและOpenGL

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

แม้ว่า แคลคูลัสแลมบ์ดา (แบบไม่ระบุชนิด) จะสมบูรณ์แบบในเชิงทัวริง แต่แคลคูลัสแลมบ์ดาแบบระบุชนิดอย่างง่ายนั้นไม่สมบูรณ์แบบในเชิงทัวริง

• "สมบูรณ์แบบตามทฤษฎีของทัวริง" . wiki.c2.com .