เครื่องทัวริงแบบไม่กำหนด
ในเครื่องทัวริงแบบไม่กำหนดสำหรับทุกสถานะและสัญลักษณ์มีกลุ่มของการกระทำที่ TM สามารถมีได้ ดังนั้นที่นี่การเปลี่ยนไม่ได้ถูกกำหนด การคำนวณของเครื่องทัวริงที่ไม่ได้กำหนดเป็นโครงสร้างของการกำหนดค่าที่สามารถเข้าถึงได้จากการกำหนดค่าเริ่มต้น
อินพุตได้รับการยอมรับหากมีอย่างน้อยหนึ่งโหนดของทรีซึ่งเป็นคอนฟิกูเรชันยอมรับมิฉะนั้นจะไม่ถูกยอมรับ หากกิ่งก้านทั้งหมดของโครงสร้างคำนวณหยุดการป้อนข้อมูลทั้งหมดเครื่องทัวริงที่ไม่ได้กำหนดจะเรียกว่า aDecider และหากสำหรับอินพุตบางส่วนสาขาทั้งหมดถูกปฏิเสธอินพุตจะถูกปฏิเสธด้วยเช่นกัน
เครื่องทัวริงแบบไม่กำหนดสามารถกำหนดได้อย่างเป็นทางการเป็น 6-tuple (Q, X, ∑, δ, q 0 , B, F) โดยที่ -
Q เป็นชุดของรัฐที่ จำกัด
X คือตัวอักษรเทป
∑ คือตัวอักษรสำหรับป้อนข้อมูล
δ เป็นฟังก์ชันการเปลี่ยนแปลง
δ: Q × X → P (Q × X × {Left_shift, Right_shift})
q0 เป็นสถานะเริ่มต้น
B คือสัญลักษณ์ว่าง
F คือชุดของสถานะสุดท้าย